题解
这个题啊，做法很套路。 二分答案 \(mid\) ，将图中所有边的边权 \(-mid\) ，用 \(SPFA\) 判断是否有负环。 若有负环，则存在更小的答案，\(r=mid\) 否则 \(l=mid\)
\(SPFA\) 判负环有两个小技巧：
用
\(dfs\) 版的效率更高
\(d[]\) 一开始都设为0 （可以证明， 负环上存在一个点，满足从它开始走一圈，边权和恒为负数）
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define eps 1e-9
using namespace std;
const int N = 3005;
typedef double db;
struct node{
int v;
db len;
node *next;
}pool[N*4],*h[N];
int cnt;
void addedge(int u,int v,db len){
node *p=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p;p->len=len;
}
int n,m;
int vis[N];
db d[N];
bool find(int u){
int v;
vis[u]=1;
for(node *p=h[u];p;p=p->next)
if(d[v=p->v]>d[u]+p->len){
d[v]=d[u]+p->len;
if(vis[v] || find(v)) return true;
}
vis[u]=0;
return false;
}
bool check(db x){
int ret=0;
for(int i=1;i<=n;i++){
for(node *p=h[i];p;p=p->next) p->len-=x;
d[i]=0.0; vis[i]=0;
}
for(int i=1;i<=n;i++)
if(find(i)) { ret=1; break; }
for(int i=1;i<=n;i++)
for(node *p=h[i];p;p=p->next) p->len+=x;
return ret;
}
int main()
{
int x,y;
db z;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d%d%lf",&x,&y,&z),addedge(x,y,z);
db l=-1e7,r=1e7,mid;
while(fabs(r-l)>=eps){
mid=(l+r)/2.0;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.8lf\n",l);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/9846223.html
相关资源：数据结构—成绩单生成器
