让我看到你们的双手 Going in Cycle!! Description
You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has aweight, which equals to sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to nd a cycle with the minimum mean.
Input
The rst line of input gives the number of cases, N. N test cases follow. Each one starts with twonumbers n and m. m lines follow, each has three positive number a; b; c which means there is an edgefrom 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 meancycle 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
2 2 1 1 2 1 2 2 1 2 2 2 1 3
Sample Output
Case #1: No cycle found. Case #2: 2.50
【解题报告】 题目大意是给定一个有向图，求平均值最小的回路。 二分答案w，然后每条边都减去w判断是否有负环。 （有谁能告诉我为什么我的代码那么慢。。。）
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<deque> using namespace std; #define N 60 #define inf 0x3f3f3f3f #define eps 1e-3 int head[N],vis[N],cnt_e[N]; double dis[N]; int t,n,m,cnt; struct Edge { int to,nxt; double w; }e[N*N]; void adde(int u,int v,double w) { e[++cnt].w=w; e[cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt; } bool SPFA(int s) { for(int i=0;i<=n;++i) dis[i]=inf*1.0; memset(vis,0,sizeof(vis)); memset(cnt_e,0,sizeof(cnt_e)); deque<int> q; dis[s]=0,vis[s]=1; q.push_back(s); while(!q.empty()) { int now=q.front();q.pop_front(); vis[now]=0; for(int i=head[now];~i;i=e[i].nxt) { int v=e[i].to; if(dis[v]>dis[now]+e[i].w) { dis[v]=dis[now]+e[i].w; if(!vis[v]) { vis[v]=1; if(!q.empty()) { if(dis[v]>dis[q.front()]) q.push_back(v); else q.push_front(v); } else q.push_back(v); if(++cnt_e[v]>=n) return 0; } } } } return 1; } bool check(double x) { bool flag=0; for(int i=1;i<=n;++i) for(int j=head[i];~j;j=e[j].nxt) e[j].w-=x; for(int i=1;i<=n;++i) if(!SPFA(i)) flag=1; for(int i=1;i<=n;++i) for(int j=head[i];~j;j=e[j].nxt) e[j].w+=x; return flag; } int main() { int cas=0; for(scanf("%d",&t);t;--t) { printf("Case #%d: ",++cas); double l=inf*1.0,r=0.0,mid=0.00; memset(head,-1,sizeof(head)); cnt=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int u,v;double w; scanf("%d%d%lf",&u,&v,&w); adde(u,v,w); l=min(l,w); r=max(r,w); } if(!check(r+1)) {printf("No cycle found.\n");continue;} while(r-l>eps) { mid=(r+l)/2.0; check(mid)?r=mid:l=mid; } printf("%.2lf\n",r); } return 0; }