P
r
o
b
l
e
m
\mathrm{Problem}
Problem
S
o
l
u
t
i
o
n
\mathrm{Solution}
Solution
只要对每一个经过的路径求最大的边权和就可以了，假设你已经知道的点集是什么。
然后用状态
f
[
S
]
[
i
]
f[S][i]
f[S][i] 表示经过的点集为
S
S
S，结尾的点为
i
i
i 的边权最大值。
答案为：
∑
x
∈
S
a
i
/
f
[
S
]
[
i
]
\sum_{x∈S}a_i/f[S][i]
x∈S∑ai/f[S][i]
C
o
d
e
\mathrm{Code}
Code
#include <bits/stdc++.h>
using namespace std
;
const int N
= 19;
int n
, m
;
int a
[N
], edge
[N
][N
], f
[1<<N
][N
];
int read(void)
{
int s
= 0, w
= 0; char c
= getchar();
while (!isdigit(c
)) w
|= c
== '-', c
= getchar();
while (isdigit(c
)) s
= s
*10+c
-48, c
= getchar();
return w
? -s
: s
;
}
int main(void)
{
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
n
= read(), m
= read();
for (int i
=1;i
<=n
;++i
) a
[i
] = read();
for (int i
=1;i
<=m
;++i
) {
int x
= read(), y
= read();
edge
[x
][y
] = max(edge
[x
][y
], read());
}
int S
= read(), T
= read();
double ans
= 1e9;
memset(f
, -30, sizeof f
);
f
[1<<S
-1][S
] = 0;
for (int S
=1;S
<1<<n
;++S
) {
for (int i
=1;i
<=n
;++i
) {
if (((S
>> i
-1) & 1) == 0) continue;
for (int j
=1;j
<=n
;++j
) {
if (i
== j
|| edge
[j
][i
] == 0) continue;
if (((S
>> j
-1) & 1) == 0) continue;
f
[S
][i
] = max(f
[S
][i
], f
[S
^(1<<i
-1)][j
] + edge
[j
][i
]);
}
}
int res
= 0;
for (int i
=1;i
<=n
;++i
)
if ((S
>> i
-1) & 1) res
+= a
[i
];
if (((S
>> T
-1) & 1) && f
[S
][T
] >= 0) ans
= min(ans
, 1.0 * res
/ f
[S
][T
]);
}
printf("%.3lf", ans
);
return 0;
}
