首先要证明的是奶牛最后选到一定是一个简单环,如下，
假设最优解不是简单环，则其中必定有一个重复点，设为c1，对于这个点隔开到也是两个环，我们设两个环中除了这个点其他点权值和分别为，c2,c3;边权值为 a1,s2;
由于它是最优解所以有 ： 1.(c1+c2+c3)/(a1+a2) > (c1+c2)/a1
                    2.(c1+c2+c3)/(a1+a2) > (c2+c3)/a2
由1有：a1*c3 > a2*(c1+c2)   由2有：a2*c1 > a1*(c2+c3)
     所以：a1*c3 > a2*c2+a1*(c2+c3) 
显然错误，至此可以有结论，最优解必定是简单环

基于这个结论在思考，发现如果判断某个解是否行，我们考虑的是简单环！！因为如果存在这样一个简单环则显然成立，不存在则必定不可行；所以我们可以把边权值变成， mid*t-F[to]，如果存在负权环则mid是可行解。

综上发现2分答案+判负环是正确解法，附代码
//By Lin
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define	maxn 1005
using namespace std; 

int		n,m,data[maxn],t[maxn],cnt;
bool	in_que[maxn];
double	d[maxn]; 
struct	Edge{
	int	to,w; 
	Edge *next; 
}*mat[maxn], edges[maxn*5]; 

void	link(int x ,int to ,int w )
{
	edges[cnt].to = to; 
	edges[cnt].w  = w; 
	edges[cnt].next = mat[x]; 
	mat[x] = &edges[cnt++];
}

bool	pan(double mid )
{
	queue<int> que; 
	while( !que.empty() ) que.pop();
	memset( d , 0 , sizeof(d) );
	memset(in_que,true,sizeof(in_que) );
	memset( t , 0 , sizeof(t) ); 
	for (int i = 1; i<=n; i++) que.push(i); 
	while ( !que.empty() )
	{
		int i = que.front(); 
		in_que[i] = false; 
		que.pop();
		for ( Edge *p = mat[i]; p ; p = p->next )
		{
			int to = p->to; 
			double w = data[to]-mid*p->w; 
			if ( w+d[i] > d[to] )
			{
				t[to]++; 
				if ( t[to] >= n ) return true; 
				d[to] = w+d[i]; 
				if ( !in_que[to] ) {
					in_que[to] = true; 
					que.push(to); 
				}

			}
		}
	}
	return false; 
	
}

int		main()
{
	int x,y,w;
	scanf("%d%d",&n,&m );
	for (int i = 1; i<=n; i++) scanf("%d", &data[i] );
	for (int i = 0; i<m ; i++)
	{
		scanf("%d%d%d", &x, &y ,&w ); 
		link( x ,y , w );
	}
	double	g = 0 , h = 10000.0, ans = -1;
	while ( fabs(g-h)>1e-4 ) 
	{
		double	mid = (g+h)/2;
		if ( pan(mid) )
		{
			ans = mid; 
			g = mid; 
		}
		else h = mid; 
	}
	if ( ans < 0 ) printf("0\n");
	else printf("%.2f\n" ,ans );
	return 0; 
}

• Re:题解（网上的题解上基本是人云亦云到留了个二分+判负环，我就写个完成版的把 ） (2184) sjh2021 2019-02-23 13:12:02