P3199 最小圈

题面

题目描述

考虑带权的有向图$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))$

输入格式

第一行2个正整数，分别为$n$和$m$，并用一个空格隔开，只用$n=|V|,m=|E|$分别表示图中有$n$个点$m$条边。
接下来m行，每行3个数$i,j,w_{i,j}$，表示有一条边$(i,j)$且该边的权值为$w_{i,j}$。输入数据保证图$G=(V,E)$连通，存在圈且有一个点能到达其他所有点。

输出格式

请输出一个实数$\mu'(c)=Min(\mu(c))$，要求输出到小数点后8位。

样例 #1

样例输入 #1

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

样例输出 #1

3.66666667

样例 #2

样例输入 #2

2 2
1 2 -2.9
2 1 -3.1

样例输出 #2

-3.00000000

提示

对于100%的数据，$n\le 3000,m\le 10000,|w_{i,j}| \le 10^7$

思路

通过二分答案将问题转化为存在性问题。

如果 $\mu(c)<mid$，那么 $r=mid$，否则 $l=mid$。

那么如何判断 $\mu(c)<mid$ 呢？

展开看看：

$\mu(c) = \frac{\sum_{i=1}^{k} w_{c_i,c_{i+1}}}{k}<mid$

$\sum_{i=1}^{k} w_{c_i,c_{i+1}}-k\times{mid}<0$

$\sum_{i=1}^{k} w_{c_i,c_{i+1}}-mid<0$

那么 $\mu(c)<mid$ 成立，即边权都减去 $mid$ 的情况下有负环存在。

这里判断其负环使用 DFS 式 的 SPFA。

跑一遍最短路，按照边权更新的逻辑，假如成功松弛才继续递归，这个时候假如出现了环，那么一定是负环，因为这个环上的每一条边从起点走到终点都会使 $dist$ 值变短，而 $dist$ 初始值是 $0$，所以走过一遍就会使这个环的总 $dist$ 变成负数，也就是出现了负环。

但是这个环是一定经过起始点的一个环，所以我们要把每个点 DFS 一遍，直到找到负环。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3010, M = 10010, INF = 1e7;
const double EPS = 1e-10;

int n, m, cnt;
bool vis[N];
double dist[N];
int fir[N];
struct Edge
{
	int to, nxt;
	double val;
}e[M << 1];

void add(int u, int v, double w)
{
	e[++cnt].to = v;
	e[cnt].nxt = fir[u];
	e[cnt].val = w;
	fir[u] = cnt;
}
bool check(int u, double x)
{
	vis[u] = true;
	for (int i = fir[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(dist[v] > dist[u] + e[i].val - x)
		{
			dist[v] = dist[u] + e[i].val - x;
			if(vis[v] || check(v, x)) return true; // ��� 
		}
	}
	vis[u] = false;
	return false;
}
bool Check(double x) 
{
	memset(dist, 0.0, sizeof(dist));
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) if(check(i, x)) return true;
	return false;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		double w;
		scanf("%d%d%lf", &u, &v, &w);
		add(u, v, w);
	}
	double l = -INF, r = INF;
	while(r - l > EPS)
	{
		double mid = (l + r) / 2.0;
		if(Check(mid)) r = mid;
		else l = mid;
	}
	printf("%.8lf\n", l);
	return 0;
}