UVA 11090 浅谈SPFA判负环

世界真的很大 这道题其实挺难想的 想到二分但是check实在是。。。 老师讲了下就豁然开朗了 SPFA是个厉害东西 可以用入队次数判断负环 description

题目是英文的也不好翻译 大概意思是给出一张有向图，求其中环的平均权值最小是多少

input

多组数据 每组数据第一行包含2个整数n，m，表示点数和边数 之后m行，每行3个整数u，v，w，表示一条u到v的边，边权为w

output

每组数据输出Case #k: n n是最小的平均权值，k是数据组数 如果没有环就输出No cycle found.

求最小的平均权值的回路 所以想到二分这个权值，以求最小 二分平均值，给所有边减去这个值 如果出现某个环的权值和为负，即负环，说明这个环的权值平均权值小于当前二分的权值，继续二分直到没有负环为止 判负环可以用SPFA，统计每个点入队的次数，超过n就说明有负环 这也是SPFA较Dijkstra优的原因 顺便一说把所有边的边权减到负，如果没有负环就说明没有环 因为题目可能涉及到小数，我又不太会 所以考虑把w*1000，用long long 读入，避免精度问题 完整代码：

#include<stdio.h> #include<cstring> #include<queue> #include<algorithm> using namespace std; typedef long long dnt; struct edge { int v,last; dnt w; }ed[100010]; queue <int> state ; dnt dis[100010],INF=99999999999999LL,big=0; int head[100010],se[100010],book[100010],vis[100010]; int num=0,n,m; void init() { num=0,big=0; memset(head,0,sizeof(head)); } void add(int u,int v,dnt w) { num++; ed[num].v=v; ed[num].w=w; ed[num].last=head[u]; head[u]=num; } bool spfa(int S) { memset(book,0,sizeof(book)); for(int i=1;i<=n+1;i++) dis[i]=INF; while(!state.empty()) state.pop(); memset(se,0,sizeof(se)); state.push(S); se[S]=1; dis[S]=0; book[S]=1; while(!state.empty()) { int u=state.front(); state.pop(); se[u]=0;vis[u]=1; for(int i=head[u];i;i=ed[i].last) { int v=ed[i].v; if(dis[v]>dis[u]+ed[i].w) { dis[v]=dis[u]+ed[i].w; if(!se[v]) { state.push(v); se[v]=1; book[v]++; if(book[v]>n) return 1; } } } } return 0; } bool check(dnt x) { bool flag; memset(vis,0,sizeof(vis)); for(int i=1;i<=num;i++) ed[i].w-=x; for(int i=1;i<=n;i++) if(!vis[i]) { flag=spfa(i); if(flag) break; } for(int i=1;i<=num;i++) ed[i].w+=x; return flag; } int main() { int T,tt=1; scanf("%d",&T); while(T--) { init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v;dnt w; scanf("%d%d%lld",&u,&v,&w); add(u,v,w*1000); big=max(big,w*1000); } printf("Case #%d: ",tt++); if(!check(big+1)) { printf("No cycle found.\n"); continue; } dnt lf=0,rg=10000000005; while(lf<=rg) { dnt mid=(lf+rg)>>1; if(check(mid)) rg=mid-1; else lf=mid+1; } printf("%0.2lf\n",(double) (lf)/1000.0); } return 0; }

嗯，就是这样