首页 > 代码库 > UVA11090 Going in Cycle!! (二分+SPFA判断有无负权)
UVA11090 Going in Cycle!! (二分+SPFA判断有无负权)
I I U P C 2 0 0 6 | |
Problem G: Going in Cycle!! | |
Input: standard input Output: standard output | |
| |
You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has a weight, which equals to sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to find a cycle with the minimum mean.
| |
Input | |
The first line of input gives the number of cases, N. N test cases follow. Each one starts with two numbers n and m. m lines follow, each has three positive number a, b, c which means there is an edge from vertex a to b with weight of c.
| |
Output | |
For each test case output one line containing “Case #x: ” followed by a number that is the lowest mean cycle in graph with 2 digits after decimal place, if there is a cycle. Otherwise print “No cycle found.”.
| |
Constraints | |
- n ≤ 50 - a, b ≤ n - c ≤ 10000000
| |
Sample Input | Output for Sample Input |
2 | Case #1: No cycle found. |
| |
Problemsetter: Mohammad Tavakoli Ghinani Alternate Solution: Cho |
题意:
在一个有向图中找一个平均距离最小的环。
思路:
二分枚举平均最小距离,每次每条边减去这个距离,然后spfa(或者bellmanFord找负环)如果找到,说明平均最小距离比这个值要小,如果没找到,则说明平均最小距离比这个值大。
注意可能是不连通图~
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define INF 0x3f3f3f3f #define eps 1e-6 #define maxn 55 #define MAXN 10005 using namespace std; int n,m,ans,cnt,sx; double le,ri,mid,res; bool vis[maxn]; double dist[maxn]; int head[maxn],num[maxn]; struct Node { int v,next; double w; }edge[MAXN]; void addedge(int u,int v,double w) { cnt++; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt; } bool SPFA(int k) { int i,j,nx,v; memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); for(i=1;i<=n;i++) dist[i]=INF; sx=k; queue<int>q; dist[sx]=0; vis[sx]=num[sx]=1; q.push(sx); while(!q.empty()) { nx=q.front(); vis[nx]=0; q.pop(); for(i=head[nx];i;i=edge[i].next) { v=edge[i].v; if(dist[v]>dist[nx]+edge[i].w-mid) { dist[v]=dist[nx]+edge[i].w-mid; if(!vis[v]) { num[v]++; if(num[v]>n) return true ; vis[v]=1; q.push(v); } } } } return false ; } int main() { int i,j,u,v,t,test=0; double w; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); cnt=0; memset(head,0,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d%lf",&u,&v,&w); addedge(u,v,w); } le=0; ri=10000005; int flag; while(ri-le>eps) { mid=(le+ri)/2.0; flag=0; for(i=1;i<=n;i++) { if(SPFA(i)) { flag=1; break ; } } if(flag) ri=mid; else le=mid; } res=le; if(res<=10000001) printf("Case #%d: %.2f\n",++test,res); else printf("Case #%d: No cycle found.\n",++test); } return 0; }