Description
考虑带权的有向图$G=(V,E)$以及$w:E
ightarrow R$,每条边$e=(i,j)(i
eq j,iin V,jin V)$的权值定义为$w_{i,j}$，令$n=|V|$。$c=(c_1,c_2,cdots,c_k)(c_iin V)$是$G$中的一个圈当且仅当$(c_i,c_{i+1})(1le i<k)$和$(c_k,c_1)$都在$E$中，这时称$k$为圈$c$的长度同时令$c_{k+1}=c_1$，并定义圈$c=(c_1,c_2,cdots,c_k)$的平均值为$mu(c)=sumlimits_{i=1}^{k} w_{c_i,c_{i+1}}/k$，即$c$上所有边的权值的平均值。令$mu'(c)=Min(mu(c))$为$G$中所有圈$c$的平均值的最小值。现在的目标是：在给定了一个图$G=(V,E)$以及$w:E
ightarrow 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%的数据，$nle 3000,mle 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$。
1 //It is made by Awson on 2017.10.9 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <cmath> 7 #include <stack> 8 #include <queue> 9 #include <vector> 10 #include <string> 11 #include <cstdio> 12 #include <cstdlib> 13 #include <cstring> 14 #include <iostream> 15 #include <algorithm> 16 #define LL long long 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define Max(a, b) ((a) > (b) ? (a) : (b)) 19 #define sqr(x) ((x)*(x)) 20 using namespace std; 21 const double eps = 1e-9; 22 const int N = 3000; 23 const int M = 10000; 24 25 int n, m, u, v, c; 26 bool vis[N+5]; 27 double dist[N+5]; 28 struct tt { 29 int to, next; 30 double cost; 31 }edge[M+5]; 32 int path[N+5], top; 33 34 void add(int u, int v, double c) { 35 edge[++top].to = v; 36 edge[top].next = path[u]; 37 edge[top].cost = c; 38 path[u] = top; 39 } 40 bool dfs(int u, double dec) { 41 vis[u] = 1; 42 for (int i = path[u]; i; i = edge[i].next) 43 if (dist[edge[i].to] > dist[u]+edge[i].cost-dec) { 44 if (vis[edge[i].to]) {vis[u] = 0; return true;} 45 dist[edge[i].to] = dist[u]+(double)edge[i].cost-dec; 46 if (dfs(edge[i].to, dec)) {vis[u] = 0; return true;} 47 } 48 vis[u] = 0; 49 return false; 50 } 51 bool judge(double dec) { 52 memset(dist, 0, sizeof(dist)); 53 for (int i = 1; i <= n; i++) 54 if (dfs(i, dec)) return true; 55 return false; 56 } 57 void work() { 58 scanf("%d%d", &n, &m); 59 double L = 0, R = 0; 60 for (int i = 1; i <= m; i++) { 61 scanf("%d%d%d", &u, &v, &c); 62 add(u, v, c); 63 R = max(R, (double)c); 64 } 65 while (R-L >= eps) { 66 double mid = (L+R)/2.; 67 if (judge(mid)) R = mid; 68 else L =mid; 69 } 70 printf("%.8lf ", (L+R)/2.); 71 } 72 int main() { 73 work(); 74 return 0; 75 }