zoj3229 Shoot the Bullet (有源汇最大流)

题目大意：文文要给幻想乡的女♂孩子们拍照，一共n天，m个女♂孩子，每天文文至多拍D[i]张照片，每个女♂孩子总共要被文文至少拍G[i]次。在第i天，文文可以拍c[i]个女♂孩子，c[i]个女♂孩子中每个女♂孩子在当天被拍的次数是

然后就很容易想到一个网络流模型：

n天放左部，m个人放右部，源点向每天连边，容量D[i]，m个人向汇点连边，容量G[i]，左部向右部连边，容量是它们的

首先先做一个有源汇上下界可行流，然后再从残量网络上跑一个s到e的最大流就是答案。

题解

首先S向每天连[0,day]的边，每一天与拍照的妹子连[l,r]的边，每个女孩和汇连[g,oo]的边

对于有源和汇的上下界网络流，只要T到S连一条[0,inf]的边，那么原图成为一个无源点汇点的循环流图，那么新建SS和TT，向每个点连边（即每一点的入流为正则源向其连，否则向汇连），求SS到TT的最大流判断满流

判断有解之后求最大流再做一次S到T的最大流

同时要去掉原来T到S的[0,inf]的边

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #define inf 1000000000
  5 using namespace std;
  6 inline int read()
  7 {
  8     int x=0,f=1;char ch=getchar();
  9     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 10     while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
 11     return x*f;
 12 }
 13 int n,m,cnt,ans;
 14 int head[1505],cur[1505],h[1505],q[1505],in[1505];
 15 int day[505],low[100005];
 16 struct data{int to,next,v;}e[100005];
 17 void ins(int u,int v,int w)
 18 {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
 19 void insert(int u,int v,int w)
 20 {ins(u,v,w);ins(v,u,0);}
 21 bool bfs(int S,int T)
 22 {
 23      memset(h,-1,sizeof(h));
 24      int t=0,w=1;q[0]=S;h[S]=0;
 25      while(t!=w)
 26      {
 27           int now=q[t];t++;
 28           for(int i=head[now];i;i=e[i].next)
 29               if(e[i].v&&h[e[i].to]==-1)
 30               {
 31                    h[e[i].to]=h[now]+1;
 32                    q[w++]=e[i].to;
 33               }
 34      }
 35      if(h[T]==-1)return 0;
 36      return 1;
 37 }
 38 int dfs(int x,int f,int T)
 39 {
 40      if(x==T)return f;
 41      int w,used=0;
 42      for(int i=cur[x];i;i=e[i].next)
 43           if(h[e[i].to]==h[x]+1)
 44           {
 45                w=f-used;w=dfs(e[i].to,min(e[i].v,w),T);
 46                e[i].v-=w;if(e[i].v)cur[x]=i;e[i^1].v+=w;
 47                used+=w;if(used==f)return f;
 48           }
 49      if(!used)h[x]=1;
 50      return used;
 51 }
 52 void dinic(int S,int T)
 53 {while(bfs(S,T)){for(int i=0;i<=n+m+3;i++)cur[i]=head[i];dfs(S,inf,T);}}
 54 bool jud()
 55 {
 56      int SS=n+m+2,TT=n+m+3;
 57      for(int i=0;i<=n+m+1;i++)
 58      {
 59           if(in[i]>0)insert(SS,i,in[i]);
 60           if(in[i]<0)insert(i,TT,-in[i]);
 61      }
 62      dinic(SS,TT);
 63      for(int i=head[SS];i;i=e[i].next)
 64          if(e[i].v)return 0;
 65      return 1;
 66 }
 67 int main()
 68 {
 69      while(scanf("%d%d",&n,&m)!=EOF)
 70      {
 71           cnt=1;int S=0,T=n+m+1;
 72           ans=0;
 73           memset(head,0,sizeof(head));
 74           memset(in,0,sizeof(in));
 75           for(int i=1;i<=m;i++)
 76           {
 77                int g=read();
 78                in[T]+=g;
 79                in[i+n]-=g;
 80           }
 81           int ed=0;
 82           for(int i=1;i<=n;i++)
 83           {
 84                int x=read();day[i]=read();
 85                for(int j=1;j<=x;j++)
 86                {
 87                    int num=read();
 88                    low[++ed]=read();int r=read();
 89                    insert(i,n+num+1,r-low[ed]);
 90                    in[i]-=low[ed];
 91                    in[n+num+1]+=low[ed];
 92                }
 93           }
 94           for(int i=1;i<=n;i++)insert(S,i,day[i]);
 95           for(int i=1;i<=m;i++)insert(i+n,T,inf);
 96           insert(T,S,inf);
 97           if(jud())
 98           {
 99                dinic(S,T);insert(T,S,-inf);//掉原来T到S的[0,inf]的边
100                for(int i=head[S];i;i=e[i].next)
101                    ans+=e[i^1].v;
102                printf("%d
",ans);
103                for(int i=1;i<=ed;i++)
104                    printf("%d
",e[(i<<1)^1].v+low[i]);
105           }
106           else printf("-1
");
107           puts("");
108      }
109      return 0;
110 }

然后来建图：引入源点S汇点T，n天一天一点，m个少女每人一点。S到每一天连一条边，上界为Dt，下界为0。每个少女到汇点连一条边，上界为无穷大，下界为Gi。对每一天，连一条边到所有要拍照的少女，下界为L，上界为R。然后引入超级源点SS，超级汇点TT，像无源无汇上下界可行流那样建边，然后T到S连一条边，容量为无穷大。最后从源点S到汇点T跑一遍最大流就是答案，每条边容量的取法和无源无汇上下界可行流一样。

小证明：原图为什么是那样建的我就不解释了。

至于加入超级源点和超级汇点之后为什么要连一条边T→S呢，因为根据无源无汇上下界可行流的做法，原图无源无汇，是应该有一个环的，而现在没有……

之后再从S到T跑一遍，会不会影响之前的流量下界呢？满足下界是来自于点与超级源点和超级汇点之间的边，如果我们把这两个点删掉，边的容量就没法变了，也就不会影响到流量下界。而我没有删掉，是因为若求出可行解之后，超级源点和超级汇点关联的边都应该是满流量的，再跑最大流不可能经过这两个点。

那么跑可行流的时候，和跑最大流的时候，流量是分开算的，那为什么不用加上原来可行流的流量呢？因为原先我们连了一条边T→S，根据无源无汇图中，每个点的入流等于出流，跑可行流的流量已经存在了T→S这条边中，跑最大流就时候，T→S的反向边就有了可行流的容量。所以跑最大流的时候会加上可行流的容量，就不用再加一遍了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <queue>
  5 using namespace std;
  6 
  7 const int MAXN = 2010;
  8 const int MAXE = 1000010;
  9 const int INF = 0x3fff3fff;
 10 
 11 struct SAP {
 12     int head[MAXN], gap[MAXN], dis[MAXN], pre[MAXN], cur[MAXN];
 13     int to[MAXE], next[MAXE], flow[MAXE], cap[MAXE];
 14     int n, ecnt, st, ed;
 15 
 16     void init() {
 17         memset(head, 0, sizeof(head));
 18         ecnt = 2;
 19     }
 20 
 21     void add_edge(int u, int v, int c) {
 22         to[ecnt] = v; cap[ecnt] = c; flow[ecnt] = 0; next[ecnt] = head[u]; head[u] = ecnt++;
 23         to[ecnt] = u; cap[ecnt] = 0; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++;
 24         //printf("%d->%d %d
", u, v, c);
 25     }
 26 
 27     void bfs() {
 28         memset(dis, 0x3f, sizeof(dis));
 29         queue<int> que; que.push(ed);
 30         dis[ed] = 0;
 31         while(!que.empty()) {
 32             int u = que.front(); que.pop();
 33             ++gap[dis[u]];
 34             for(int p = head[u]; p; p = next[p]) {
 35                 int &v = to[p];
 36                 if(cap[p ^ 1] > flow[p ^ 1] && dis[v] > n) {
 37                     dis[v] = dis[u] + 1;
 38                     que.push(v);
 39                 }
 40             }
 41         }
 42     }
 43 
 44     int Max_flow(int ss, int tt, int nn) {
 45         st = ss, ed = tt, n = nn;
 46         int ans = 0, minFlow = INF, u;
 47         for(int i = 0; i <= n; ++i) {
 48             cur[i] = head[i];
 49             gap[i] = 0;
 50         }
 51         u = pre[st] = st;
 52         bfs();
 53         while(dis[st] < n) {
 54             bool flag = false;
 55             for(int &p = cur[u]; p; p = next[p]) {
 56                 int &v = to[p];
 57                 if(cap[p] > flow[p] && dis[u] == dis[v] + 1) {
 58                     flag = true;
 59                     minFlow = min(minFlow, cap[p] - flow[p]);
 60                     pre[v] = u;
 61                     u = v;
 62                     if(u == ed) {
 63                         ans += minFlow;
 64                         while(u != st) {
 65                             u = pre[u];
 66                             flow[cur[u]] += minFlow;
 67                             flow[cur[u] ^ 1] -= minFlow;
 68                         }
 69                         minFlow = INF;
 70                     }
 71                     break;
 72                 }
 73             }
 74             if(flag) continue;
 75             int minDis = n - 1;
 76             for(int p = head[u]; p; p = next[p]) {
 77                 int &v = to[p];
 78                 if(cap[p] > flow[p] && dis[v] < minDis) {
 79                     minDis = dis[v];
 80                     cur[u] = p;
 81                 }
 82             }
 83             if(--gap[dis[u]] == 0) break;
 84             ++gap[dis[u] = minDis + 1];
 85             u = pre[u];
 86         }
 87         return ans;
 88     }
 89 } G;
 90 
 91 int n, m, c, d, l, r, x;
 92 int f[MAXN], down[MAXE], id[MAXE];
 93 
 94 int main() {
 95     while(scanf("%d%d", &n, &m) != EOF) {
 96         G.init();
 97         memset(f, 0, sizeof(f));
 98         int s = n + m + 1, t = s + 1;
 99         int ss = t + 1, tt = ss + 1;
100         for(int i = 1; i <= m; ++i) {
101             scanf("%d", &x);
102             f[i] -= x;
103             f[t] += x;
104             G.add_edge(i, t, INF);
105         }
106         int cnt = 0;
107         for(int i = 1; i <= n; ++i) {
108             scanf("%d%d", &c, &d);
109             G.add_edge(s, i + m, d);
110             while(c--) {
111                 scanf("%d%d%d", &x, &l, &r);
112                 f[i + m] -= l;
113                 f[x + 1] += l;
114                 down[++cnt] = l; id[cnt] = G.ecnt;
115                 G.add_edge(i + m, x + 1, r - l);
116             }
117         }
118         int sum = 0;
119         for(int i = 1; i <= t; ++i) {
120             if(f[i] > 0) sum += f[i], G.add_edge(ss, i, f[i]);
121             else G.add_edge(i, tt, -f[i]);
122         }
123         G.add_edge(t, s, INF);
124         if(sum != G.Max_flow(ss, tt, tt)) puts("-1");
125         else {
126             printf("%d
", G.Max_flow(s, t, tt));
127             for(int i = 1; i <= cnt; ++i) printf("%d
", down[i] + G.flow[id[i]]);
128         }
129         puts("");
130     }
131 }