调完样例后居然一次ac，感动啊...
这是一个模板题有两个点要注意
一是建图的时候要用+=而不能直接=，因为两个点之间的管道可能会多次叠加（特别是处理x和y的时候）
二是在最后算s的流出流量之和时要先把【t到s】和【s到t】的边删掉
像素好低啊。。
1 #include<iostream> 2 #include<cstring> 3 #include<deque> 4 #define INF 1000000000 5 using namespace std; 6 7 int n,G[250][250],G2[250][250],max_flow,T,sum; 8 9 int layer[250],vis[250]; 10 bool countlayer(int s){//还有没有增广路 11 memset(layer,0,sizeof(layer)); 12 deque<int> q; 13 q.push_back(s); layer[s]=1; 14 while(!q.empty()){ 15 int nd = q.front(); q.pop_front(); 16 if(nd==T) return true; 17 for(int i=1;i<=n+2;i++){ 18 if(G[nd][i] && layer[i]==0){ 19 layer[i]=layer[nd]+1; 20 q.push_back(i); 21 } 22 } 23 } 24 return false; 25 } 26 27 int dinic(int s){ 28 //cout<<"?"<<endl; 29 while( countlayer(s) ){ 30 // cout<<max_flow<<endl; 31 // cout<<"suc"<<endl; 32 memset(vis,0,sizeof(vis)); 33 deque<int> q; 34 q.push_back(s); vis[s]=1; 35 while(!q.empty()){ 36 int nd=q.back(); 37 if(nd==T){//找到一条增广路 38 int minflow=INF,u; 39 for(int i=0;i<q.size()-1;i++){//从上到下的最小管道 40 int from=q[i],to=q[i+1]; 41 if(G[from][to]<minflow){ 42 minflow=G[from][to]; 43 u=from; 44 } 45 } 46 //做增广 47 for(int i=0;i<q.size()-1;i++){ 48 int from=q[i],to=q[i+1]; 49 G[from][to]-=minflow; 50 G[to][from]+=minflow; 51 } 52 max_flow+=minflow; 53 //回溯 54 while(!q.empty() && q.back()!=u ){ 55 vis[q.back()]=0; 56 q.pop_back(); 57 } 58 } 59 else{//继续往下搜 60 int i; 61 for(i=1;i<=n+2;i++){ 62 if( layer[nd]+1==layer[i] && vis[i]==0 && G[nd][i] ){ 63 vis[i]=1; 64 q.push_back(i); 65 break; 66 } 67 } 68 if(i==n+3) q.pop_back(); 69 } 70 } 71 } 72 } 73 74 int main(){ 75 int m,s,t; cin>>n>>m>>s>>t; 76 //x在n+1 ; y在n+2 77 for(int i=1;i<=m;i++){ 78 int u,v,lower,upper; cin>>u>>v>>lower>>upper; 79 sum+=lower; 80 G[u][v]+=upper-lower;//非必要弧 81 G[u][n+1] += lower; 82 G[n+2][v] += lower;//必要弧 83 } 84 G[n+1][n+2] = G[t][s] = INF; 85 86 for(int i=1;i<=n+2;i++){ 87 for(int j=1;j<=n+2;j++) G2[i][j]=G[i][j]; 88 } 89 T=n+1; 90 dinic(n+2); 91 //cout<<max_flow<<" "<<sum<<endl; 92 if(max_flow!=sum) cout<<"please go home to sleep"; 93 else{ 94 int sum1=0; 95 //cout<<"!!! "<<G2[s][t]<<" "<<G[s][t]<<endl; 96 G[s][t] = G[t][s] = 0; 97 for(int i=1;i<=n+2;i++){ 98 // cout<<G2[s][i]<<" "<<G[s][i]<<endl; 99 sum1+=G2[s][i]-G[s][i]; 100 } 101 // cout<<sum1<<endl; 102 max_flow=0; 103 104 T=t; 105 dinic(s); 106 cout<<sum1+max_flow; 107 } 108 109 return 0; 110 }