E4-D CYCLES

题目描述

题目描述

在这循环往复的季节里，
对你的倾诉仍未说出口。
「我，任何改变都没有吗？」

给定 n 个点 m 条边的带权有向图 G。G 上的点依次标号 1,2,…,n1,2,…,n。第 ii 条边$ u_i→v_i$ 的起点为 uiu_i，终点为 viv_i，边权为 wiw_i。

对于 G 上的环$ p_1→p_2→⋯→p_k→p_1$，定义环的权值为环上所有边的边权平均值。

请你求出 G 上环的权值的最小值。如果 G 上没有环，则认为答案为 0。

输入

本题测试点包含多组数据。

第一行，一个正整数 T（1≤T≤10）T（1≤T≤10），表示数据组数。

对于每组数据：

第一行，两个正整数$ n,m（1≤n≤10^3，1≤m≤10^3）$，表示 G 的点数与边数。

接下来 m 行，每行三个正整数 ui,vi,wi（1≤ui≤n，1≤vi≤n，1≤wi≤106，ui≠vi）u_i,v_i,w_i（1≤u_i≤n，1≤v_i≤n，1≤w_i≤10^6，u_i≠v_i），表示有向边的起点、终点与边权。

输出

对于每组数据：

输出一行，一个实数，表示答案。答案保留小数点后 4 位。

输入样例

1
2
3
4
5
6
7
8
9
10
11
2
3 5
1 2 3
2 3 1
3 2 1
2 1 2
3 1 4
3 3
1 2 1
2 3 2
1 3 3

输出样例

1
2
1.0000
0.0000

题目分析

假设存在一个环S(V,E)S(V,E)，VV为换上点的集合，EE为换上边的集合。设每条边的边权为e[i].diste[i].dist，每个点的点权为1，则题目要求：

∑i=1te[i].dist∑i=1t1<=ans\frac{\sum_{i=1}^{t}e[i].dist}{\sum_{i=1}^{t}1}<=ans

化简可得：

∑i=1te[i].dist−ans∗∑i=1t1<=0∑i=1t(e[i].dist−ans)<=0\sum_{i=1}^{t}e[i].dist-ans *\sum_{i=1}^{t}1<=0 \\ \sum_{i=1}^{t}({e[i].dist-ans})<=0

这里将边权看作e[i].dist−ans{e[i].dist-ans}，就得到ansans为使得新图中存在负权环的最小值。

我们可以通过二分查找结合BellmanFordBellmanFord算法，来求得这个ansans。

示例代码

二分查找

1
2
3
4
5
6
7
8
9
while (R - L > 1e-6)
{
	db m = (L + R) / 2;
	if (check(m))
		R = m;
	else
		L = m;
}
printf("%.4lf\n", R);

判断m是否可以让新图中存在负权环

1
2
3
4
5
6
7
8
9
10
bool check(db x)
{
    int i;
    for (i = 0; i < B.edges.size(); ++i)
        B.edges[i].dist -= x;
    bool f = B.negativeCycle();
    for (i = 0; i < B.edges.size(); ++i)
        B.edges[i].dist += x;
    return f;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool negativeCycle()
{  
	queue<int> Q;
 	memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
    {
        d[i] = 0;
        inq[0] = 1;
        Q.push(i);
    }
    while (!Q.empty())
    {
        int u = Q.front();
    	Q.pop();
        inq[u] = 0;
        for (int i = 0; i < G[u].size(); ++i)
        {
            Edge e = edges[G[u][i]];
            if (d[e.to] > d[u] + e.dist)
            {
                d[e.to] = d[u] + e.dist;
                p[e.to] = G[u][i];
                if (!inq[e.to])
                {
                    Q.push(e.to);
                    inq[e.to] = 1;
                    if (++cnt[e.to] > n)
                        return true;
                }
            }
        }
    }
        return false;
}