2023.1.12 有源汇上下界最大流简笔

警示

2023.1.12

[模板]有源汇上下界最大流

错误点：

　　1.建边方法简便：靠近于用u,v,w建边，不要冗杂多余（9-17行）

　　2.算法注意点：首先抽出每条边的下界(每条边边权 = 上界 - 下界)，建立虚拟源汇点进行dinic,答案得出后虚拟源点到汇点的流则为可行流，若虚拟源点的流出边有一个没有满流，则无解

　　　　　　　　　其次在原图上进行dinic直到没有增广路为止，二答案相加则为最大流答案。

  1 #include<bits/stdc++.h>
  2 #define int long long
  3 using namespace std;
  4 const int N = 1e5 + 5,inf = 0x7fffffff;
  5 struct Edge{
  6     int l,r,w,v,u,next;
  7 }e[N * 2];
  8 int head[N],n,m,g[N],c,p,ans = 0,tot = 1,d[N],vis[N],nw[N],st = 1,ed = n + m + 2,in[N],out[N];
  9 inline void add(int x,int y,int w)
 10 {
 11     ++tot;
 12     e[tot].u = x;
 13     e[tot].w = w;
 14     e[tot].v = y;
 15     e[tot].next = head[x];
 16     head[x] = tot;
 17 }
 18 inline void init()
 19 {
 20     for(int i=1;i<=tot;i++)
 21     {
 22         if(e[i].l == 0 && e[i].r == 0) continue;
 23         e[i].w = e[i].r - e[i].l;
 24     }
 25     for(int i=1;i<=n + m + 2;i++)
 26     {
 27         if(in[i] > out[i])
 28         {
 29             add(n + m + 3,i,in[i] - out[i]);
 30             e[tot].w = in[i] - out[i];
 31             add(i,n + m + 3,0);
 32         }
 33         if(out[i] > in[i])
 34         {
 35             add(i,n + m + 4,out[i] - in[i]);
 36             e[tot].w = out[i] - in[i];
 37             add(n + m + 4,i,0);
 38         }
 39     }
 40 }
 41 inline bool bfs()
 42 {
 43     for(int i=1;i<=n + m + 4;i++) d[i] = 0x7fffffff;
 44     queue <int> q;
 45     while(!q.empty()) q.pop();
 46     q.push(st);
 47     d[st] = 1;
 48     nw[st] = head[st];
 49     while(!q.empty())
 50     {
 51         int now = q.front();
 52         q.pop();
 53         for(int i = head[now];i;i = e[i].next)
 54         {
 55             int to = e[i].v;
 56             if(e[i].w <= 0 || d[to] < 0x7fffffff) continue;
 57             nw[to] = head[to];
 58             d[to] = d[now] + 1;
 59             q.push(to);
 60         }
 61     }
 62     if(d[ed] < 0x7fffffff) return 1;
 63     return 0;
 64 }
 65 inline int dinic(int x,int flow)
 66 {
 67     if(x == ed) return flow;
 68     int rest = flow;
 69     for(int i = nw[x];i && rest;i = e[i].next)
 70     {
 71         nw[x] = i;
 72         int to = e[i].v;
 73         if(d[to] != d[x] + 1 || e[i].w <= 0) continue;
 74         int k = dinic(to,min(rest,e[i].w));
 75         if(!k) d[to] = inf;
 76         rest -= k;
 77         e[i].w -= k;
 78         e[i ^ 1].w += k;
 79     }
 80     return flow - rest;    
 81 }
 82 signed main()
 83 {    
 84     while(cin>>n>>m)
 85     {
 86         memset(in,0,sizeof(in));
 87         memset(out,0,sizeof(out));
 88         tot = 1;
 89         memset(head,0,sizeof(head));
 90         memset(nw,0,sizeof(nw));
 91         ans = 0;
 92         int t,l,r;
 93         for(int i=1;i<=m;i++) 
 94         {
 95             cin>>g[i];
 96         }
 97         for(int i=1;i<=n;i++)
 98         {
 99             cin>>c>>p;
100             for(int j=1;j<=c;j++)
101             {
102                 cin>>t>>l>>r;
103                 t++;
104                 add(i + 1,n + t + 1,r - l);
105                 add(n + t + 1,i + 1,0);
106                 out[i + 1] += l;
107                 in[n + t + 1] += l;
108             }
109             add(1,i + 1,p);
110             add(i + 1,1,0);
111         }
112         for(int i=1;i<=m;i++)
113         {
114             add(i + n + 1,n + m + 2,inf - g[i]);
115             add(n + m + 2,i + n + 1,0);
116             out[i + n + 1] += g[i];
117             in[n + m + 2] += g[i];
118         }
119         st = n + m + 3;ed = n + m + 4;
120         init();
121         add(n + m + 2,1,inf);
122         add(1,n + m + 2,0);
123         int flow = 0;
124         while(bfs())
125             while(flow = dinic(st,inf)) 
126                 flow = 0;
127         int flag = 1;
128         ans += (inf - e[tot - 1].w);
129         for(int i = head[st];i;i = e[i].next)
130             if(e[i].w > 0) 
131                 flag = 0;
132         if(flag == 0) 
133         {
134             cout<<-1<<endl<<endl;
135             continue;
136         }
137         e[tot].w = 0;
138         e[tot - 1].w = 0;
139         st = 1;
140         ed = n + m + 2;
141         flow = 0;
142         while(bfs())
143             while(flow = dinic(st,inf))
144                 ans += flow;
145         cout<<ans<<endl<<endl;
146     }
147     return 0;
148 }