UVA

蓝书上的例题，题意是给定一个有向图，边带权，每次操作可以选择一个点，把以该点为终点的边权都-1，以该点为起点的边权都+1，要使得最小的边权最大，问最大值是多少

题解是转化成差分约束问题求解，但实际通过观察可发现，每个环的边权是固定的，因此相当于求平均值最小的环，二分+判负环即可

SPFA判负环的方法网传的有三种，第一种是判入队次数，T了；第二种是判松弛次数(实际是错的)，能A但是能被hack；第三种是记录最短路经过点的数量，如果超过n说明存在负环，终于A了

快被负环搞自闭了，每次碰上判负环的题都得被卡两下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=500+10,inf=20000;
 5 int n,m,hd[N],ne,inq[N],cnt[N],tim;
 6 int d[N];
 7 struct E {int v,c,nxt;} e[3000];
 8 void link(int u,int v,int c) {e[ne]= {v,c,hd[u]},hd[u]=ne++;}
 9 queue<int> q;
10 int spfa() {
11     while(q.size())q.pop();
12     for(int i=1; i<=n; ++i)q.push(i),d[i]=0,inq[i]=cnt[i]=1;
13     while(q.size()) {
14         int u=q.front();
15         q.pop(),inq[u]=0;
16         for(int i=hd[u]; ~i; i=e[i].nxt) {
17             int v=e[i].v,c=e[i].c,g=d[u]+c;
18             if(d[v]>g) {
19                 d[v]=g;
20                 if(!inq[v])q.push(v),inq[v]=1;
21                 if((cnt[v]=cnt[u]+1)>n)return 1;
22             }
23         }
24     }
25     return 0;
26 }
27 bool ok(int x) {
28     for(int i=0; i<ne; ++i)e[i].c-=x;
29     int ret=!spfa();
30     for(int i=0; i<ne; ++i)e[i].c+=x;
31     return ret;
32 }
33 int bi(int l,int r) {
34     int ret=0;
35     while(l<=r) {
36         int mid=(l+r)>>1;
37         if(ok(mid))ret=mid,l=mid+1;
38         else r=mid-1;
39     }
40     return ret;
41 }
42 int main() {
43     while(~scanf("%d%d",&n,&m)) {
44         memset(hd,-1,sizeof hd),ne=0;
45         while(m--) {
46             int u,v,c;
47             scanf("%d%d%d",&u,&v,&c);
48             link(u,v,c);
49         }
50         int ans=bi(0,inf);
51         if(ans==inf)puts("Infinite");
52         else if(ans==0)puts("No Solution");
53         else printf("%d
",ans);
54     }
55     return 0;
56 }