题意:现在的网络有一个源点s和汇点t,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制.

思路:要满足每一个点的流量守恒,我们可以尝试像无源汇上下界可行流一样,跑一次dinic先构造出这样一个的可行流。在保证他可行的情况下,利用残余流量

从s到t再跑一次dinic即可;  这个时候跑的dinic 在上一次跑的时候,从t到s就有了一定的流量,所以他的反向边,也就是s到t在跑第二次dinic的时候,就已经保存了

上一次跑dinic的值,所以这一次跑,会将剩下的参与流量尽可能的流向t 来求出最大流。

那为什么这样子可行呢?

我们在第一次跑的时候,就已经保证了从超级源点到超级汇点的值(也就是S,T)是不变的了;

也就是在保证可行流的情况下,再进行操作,保证最大而已。

  1 #include<cstdio>
  2 #include<string.h>
  3 #include<algorithm>
  4 #include<math.h>
  5 #include<queue>
  6 using namespace std;
  7 const int maxn=11000;
  8 const int inf=0x3f3f3f3f;
  9 int head[maxn],level[maxn];   //前者为邻接表必要数据,后者为dinic的层 数据
 10 int limit[maxn];  //limit为该点的流量   小于0的时候是流出多
 11 int num;  //邻接表
 12 int cur[maxn];
 13 void init()
 14 {
 15     num=-1  ;
 16     memset(head,-1,sizeof(head));
 17 }
 18 struct node
 19 {
 20     int v,w,next;
 21 }G[400000];
 22 int bfs(int s,int t)
 23 {
 24     queue<int>q;
 25     q.push(s);
 26     memset(level,-1,sizeof(level));
 27     level[s]=0;
 28     while(!q.empty()){
 29         int u=q.front();
 30         q.pop();
 31         for(int i=head[u];i!=-1;i=G[i].next){
 32             int v=G[i].v;
 33             if(G[i].w>0&&level[v]==-1){
 34                 level[v]=level[u]+1;
 35                 q.push(v);
 36             }
 37         }
 38     }
 39    return level[t];
 40 }
 41 int dfs(int s,int t,int f)
 42 {
 43     if(s==t) return f;
 44     int ans=0;
 45     for(int i=cur[s];i!=-1;i=G[i].next){
 46         cur[s]=i;  //当前弧优化;
 47         int v=G[i].v;
 48         if(G[i].w>0&&level[s]+1==level[v]){
 49             int d=dfs(v,t,min(G[i].w,f-ans));
 50             if(d>0){
 51                 G[i].w-=d;
 52                 G[i^1].w+=d;
 53                 ans+=d;
 54                 if(ans==f) return ans;
 55             }
 56         }
 57     }
 58     if(ans==0) level[s]=0;
 59     return ans;
 60 }
 61 int dinic(int s,int t)
 62 {
 63     int ans=0;
 64     while(1){
 65         int temp=bfs(s,t);
 66         if(temp==-1) break;
 67         memcpy(cur,head,sizeof(cur));
 68         ans+=dfs(s,t,inf);
 69     }
 70     return ans;
 71 }
 72 void build(int u,int v,int w)
 73 {
 74     num++;
 75     G[num].v=v;
 76     G[num].w=w;
 77     G[num].next=head[u];
 78     head[u]=num;
 79
 80     num++;
 81     G[num].v=u;
 82     G[num].w=0;
 83     G[num].next=head[v];
 84     head[v]=num;
 85 }
 86 int main()
 87 {
 88     init();
 89     int n,m,s,t;
 90     scanf("%d%d%d%d",&n,&m,&s,&t);
 91     for(int i=1;i<=m;i++){
 92         int u,v,w1,w2;
 93         scanf("%d%d%d%d",&u,&v,&w1,&w2);
 94         limit[u]-=w1;
 95         limit[v]+=w1;
 96         build(u,v,w2-w1);
 97     }
 98     build(t,s,inf);
 99     //其实这里应该有上面的limit的变化 只是因为这里的w1为0,所以省略不写。
100     int S=0;int T=n+1;
101     int sum=0;
102     for(int i=1;i<=n;i++){
103         if(limit[i]<0) build(i,T,-limit[i]);
104         if(limit[i]>0) build(S,i,limit[i]),sum+=limit[i];
105     }
106     if(dinic(S,T)!=sum) printf("please go home to sleep\n");
107     else printf("%d\n",dinic(s,t));
108     return 0;
109 }
01-13 04:13