题目：Going in Cycle!!
题意：给出一张边权为正整数的有向图，求一个平均权值最小的回路的平均权值。
思路：二分这个最小的平均权值p，再将所有的边权减去p，用spfa判负环。如果此时图中有负环，则说明存在比p更小的平均权值。
注意：这题本机过了提交却WA，看了很久才发现输出double时吧%lf写成了%llf……qwq
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 50
#define db doublestruct Pair {int x;db y;Pair(int xx=0,db yy=0) {x=xx,y=yy;}
};int n,m;vector<Pair> a[maxn+5];bool spfa() {queue<int> que;int cnt[maxn+5]= {0};db dist[maxn+5]= {0};bool u[maxn+5]= {0};for(int i=1; i<=n; i++) {que.push(i);dist[i]=0,u[i]=true;}while(!que.empty()) {int h=que.front();que.pop();u[h]=false;for(int i=0; i<a[h].size(); i++) {int x=a[h][i].x;db y=a[h][i].y;if(dist[x]>dist[h]+y) {dist[x]=dist[h]+y;if(!u[x]) {u[x]=true,que.push(x);if(++cnt[x]>n) return false;}}}}return true;
}bool judge(db x) {for(int i=1; i<=n; i++) {for(int j=0; j<a[i].size(); j++) {a[i][j].y-=x;}}bool ans=spfa();for(int i=1; i<=n; i++) {for(int j=0; j<a[i].size(); j++) {a[i][j].y+=x;}}return ans;
}db binsearch(db rr) {db l=0,r=rr;while(l+(1e-4)<r) {db mid=l+(r-l)/2;if(judge(mid)) l=mid;else r=mid;}return l;
}void init() {for(int i=0; i<=maxn; i++) a[i].clear();
}db readin() {db r=0;scanf("%d%d",&n,&m);for(int i=1; i<=m; i++) {int x,y;db z;scanf("%d%d%lf",&x,&y,&z);a[x].push_back(Pair(y,z));r=max(r,z);}return r;
}int main() {int T;scanf("%d",&T);for(int t=1; t<=T; t++) {init();db r=readin();if(judge(r+1)) printf("Case #%d: No cycle found.\n",t);else {db ans=binsearch(r);printf("Case #%d: %.2lf\n",t,ans);}}return 0;
}