Description
考虑带权的有向图$G=(V,E)$以及$w:E\rightarrow R$,每条边$e=(i,j)(i\neq j,i\in V,j\in V)$的权值定义为$w_{i,j}$，令$n=|V|$。$c=(c_1,c_2,\cdots,c_k)(c_i\in V)$是$G$中的一个圈当且仅当$(c_i,c_{i+1})(1\le i<k)$和$(c_k,c_1)$都在$E$中，这时称$k$为圈$c$的长度同时令$c_{k+1}=c_1$，并定义圈$c=(c_1,c_2,\cdots,c_k)$的平均值为$\mu(c)=\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}/k$，即$c$上所有边的权值的平均值。令$\mu'(c)=Min(\mu(c))$为$G$中所有圈$c$的平均值的最小值。现在的目标是：在给定了一个图$G=(V,E)$以及$w:E\rightarrow R$之后，请求出$G$中所有圈$c$的平均值的最小值$\mu'(c)=Min(\mu(c))$
Input
第一行2个正整数，分别为$n$和$m$，并用一个空格隔开，只用$n=|V|,m=|E|$分别表示图中有$n$个点$m$条边。 接下来m行，每行3个数$i,j,w_{i,j}$，表示有一条边$(i,j)$且该边的权值为$w_{i,j}$。输入数据保证图$G=(V,E)$连通，存在圈且有一个点能到达其他所有点。
Output
请输出一个实数$\mu'(c)=Min(\mu(c))$，要求输出到小数点后8位。
Sample Input
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
Sample Output
3.66666667
HINT
对于100%的数据，$n\le 3000,m\le 10000,|w_{i,j}| \le 10^7$
题解
最小化平均值($01$分数规划)。
使用二分求解。对于一个猜测的$mid$,只需判断是否存在平均值小于$mid$的回路。
如何判断?
假设存在一个包含$k$条边的回路,回路上各边权值为$w_1$ ,$w_2$ ,$...$,$w_k$ ,那么平均值小于$midv$意味着:
$$w_1 +w_2 +...+w_k <k×mid$$
即:
$$(w_1 -mid)+(w_2 -mid)+...+(w_k -mid)<0$$
换句话说,只要把边$(a,b)$的权$w(a,b)$改成$w(a,b)-mid$,再判断新图中是否有负环即可。
存在负环,那么之前的不等式满足,即存在着更小的平均值,$r=mid$;不存在,$l=mid$。
//It is made by Awson on 2017.10.9
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define sqr(x) ((x)*(x))
using namespace std;
const double eps = 1e-;
const int N = ;
const int M = ; int n, m, u, v, c;
bool vis[N+];
double dist[N+];
struct tt {
int to, next;
double cost;
}edge[M+];
int path[N+], top; void add(int u, int v, double c) {
edge[++top].to = v;
edge[top].next = path[u];
edge[top].cost = c;
path[u] = top;
}
bool dfs(int u, double dec) {
vis[u] = ;
for (int i = path[u]; i; i = edge[i].next)
if (dist[edge[i].to] > dist[u]+edge[i].cost-dec) {
if (vis[edge[i].to]) {vis[u] = ; return true;}
dist[edge[i].to] = dist[u]+(double)edge[i].cost-dec;
if (dfs(edge[i].to, dec)) {vis[u] = ; return true;}
}
vis[u] = ;
return false;
}
bool judge(double dec) {
memset(dist, , sizeof(dist));
for (int i = ; i <= n; i++)
if (dfs(i, dec)) return true;
return false;
}
void work() {
scanf("%d%d", &n, &m);
double L = , R = ;
for (int i = ; i <= m; i++) {
scanf("%d%d%d", &u, &v, &c);
add(u, v, c);
R = max(R, (double)c);
}
while (R-L >= eps) {
double mid = (L+R)/.;
if (judge(mid)) R = mid;
else L =mid;
}
printf("%.8lf\n", (L+R)/.);
}
int main() {
work();
return ;
}