二分+SPFA找负环
11090 - Going in Cycle!! Time limit: 3.000 seconds |
| 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
2 1
1 2 1
2 2
1 2 2
2 1 3 |
Case #1: No cycle found.
Case #2: 2.50 |
| |
| Problemsetter: Mohammad Tavakoli Ghinani Alternate Solution: Cho |
#include
#include
#include
#include
#include
using namespace std; const double INF=1000000000.; struct Edge { int to,next; double w; }edge[110000]; int Adj[100],Size=0,n,m; void init() { Size=0; memset(Adj,-1,sizeof(Adj)); } void Add_Edge(int u,int v,double w) { edge[Size].to=v; edge[Size].next=Adj[u]; edge[Size].w=w; Adj[u]=Size++; } double dist[110]; int cq[110]; bool inq[110]; bool spfa(double mid) { queue
q; for(int i=1;i<=n;i++) { q.push(i); dist[i]=INF; cq[i]=0; inq[i]=false; } while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=false; for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(dist[v]>dist[u]+edge[i].w-mid) { dist[v]=dist[u]+edge[i].w-mid; if(!inq[v]) { inq[v]=true; cq[v]++; if(cq[v]>=n) return false; q.push(v); } } } } return true; } int main() { int T_T,cas=1; scanf("%d",&T_T); while(T_T--) { scanf("%d%d",&n,&m); init(); double ans=INF; double low=0,high=0,mid; for(int i=0;i
1e-3) { mid=(high+low)/2.; if(spfa(mid)==false) { ans=min(ans,mid); high=mid; } else low=mid; } printf("%.2lf\n",ans); } return 0; }