题目链接

一开始不理解为什么不能直接用\(Tarjan\)跑出换直接求出最小值，然后想到了“简单环”，恍然大悟。

二分答案，把所有边都减去\(mid\)，判是否存在负环，存在就\(r=mid\)。

别的题都卡dfs，这题卡bfs

#include <cstdio>

#include <queue>

#define INF 2147483647

using namespace std;

const int MAXN = 30010;

const int MAXM = 100010;

const double eps = 1e-10;

struct Edge{

	int next, to;

	double dis;

}e[MAXM];

int num, head[MAXN];

inline void Add(int from, int to, double dis){

	e[++num] = (Edge){ head[from], to, dis }; head[from] = num;

}

int a[MAXM], b[MAXN], T, n, m, v[MAXN], now;

double dis[MAXN], c[MAXN];

queue <int> q;

/*int bfs(int x){

	while(q.size()) q.pop();

	q.push(x); cnt[x] = 1; v[x] = 1; dis[x] = 0;

	while(q.size()){

		now = q.front(); q.pop(); v[now] = 0;

		for(int i = head[now]; i; i = e[i].next)

		   if(dis[e[i].to] > dis[now] + e[i].dis){

		   	 dis[e[i].to] = dis[now] + e[i].dis;

		   	 if(!v[e[i].to]){

		   	 	if(++cnt[e[i].to] >= n) return 1;

		   	 	v[e[i].to] = 1;

		   	 	q.push(e[i].to);

		   	 }

		   }

	}

	return 0;

}*/

int dfs(int u){

	v[u] = 1;

	for(int i = head[u]; i; i = e[i].next)

	   if(dis[e[i].to] > dis[u] + e[i].dis){

	   	 dis[e[i].to] = dis[u] + e[i].dis;

	   	 if(v[e[i].to]) return 1;

	   	 if(dfs(e[i].to)) return 1;

	   }

	v[u] = 0;

	return 0;

}

int check(){

	for(int i = 1; i <= n; ++i)

	   if(dfs(i))

	     return 1;

	return 0;

}

double l = -1e7, r = 1e7, mid;

int main(){

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= m; ++i)

	   scanf("%d%d%lf", &a[i], &b[i], &c[i]);

	while(r - l > eps){

		mid = (l + r) / 2;

		for(int i = 1; i <= m; ++i)

		   Add(a[i], b[i], c[i] - mid);

		if(check()) r = mid;

		else l = mid;

		for(int i = 1; i <= n; ++i)

		   head[i] = v[i] = dis[i] = 0;

		num = 0;

	}

	printf("%.8lf\n", l);

	return 0;

}