AcWing 361. 观光奶牛 题解（spfa求正环）

AcWing 361. 观光奶牛

由图中公式可知，这道题让求的是有一个正环即可，所以要寻找的是最长路径，所以if中的判断句判断的是能否找到更长边值

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = 5210;

int h[N], ne[M], e[M], w[M], idx;
int n, m;
double dist[N];
int wf[N];
bool st[N];
int cnt[N];  //记录边数 

void add(int a, int b, int c){
    
	e[idx] = b;
	ne[idx] = h[a];
	w[idx] = c;
	h[a] = idx ++ ;
}

bool check(double mid){
    
	memset(dist, 0, sizeof dist);
	memset(st, 0, sizeof st);
	memset(cnt, 0, sizeof cnt);
	
	queue<int>q;
	for(int i = 1; i <= n; i ++ ){
    
		q.push(i);
		st[i] = true;
	} 
	
	while(q.size()){
    
		int t = q.front();
		q.pop();
		st[t] = false;
		
		for(int i = h[t]; ~i; i = ne[i]){
    
			int j = e[i];
			if(dist[j] < dist[t] + wf[t] - mid * w[i]){
      //要求的是正环，所以是最长路 
				dist[j] = dist[t] + wf[t] - mid * w[i];
				cnt[j] = cnt[t] + 1;
				if(cnt[j] >= n) return true;
				if(!st[j]){
    
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	return false;
}

int main()
{
    
	cin>>n>>m;
	
	for(int i = 1; i <= n; i ++ ) cin>>wf[i];
	
	memset(h, -1, sizeof h);
	for(int i = 0; i < m; i ++ ){
    
		int a, b, c;
		cin>>a>>b>>c;
		add(a, b, c);
	}
	
	double l = 0, r = 1e6;
	while(r - l > 1e-4){
    
		double mid = (l + r) / 2;
		if(check(mid)) l = mid;  //这个值可以，可以试图找更大值
		else r = mid;   //这个值不行，要找更小值
	}
	printf("%.2lf\n", r);
	return 0;
}