无源汇有上下界可行流

我们先强行给每条边把底线塞满，但是这必然导致出入流不等，现在我们要寻找一种流法将这差值补满。

新建源点和汇点，原图上连r−lr-l的流量，每个点多出或少的流量从源点接入或接出到汇点。再从源点到汇点跑网络流最大流，如果能做到出流等于入流，那么说明可以构造出一种流法补全原来出入流不对等的方案。

有源汇有上下界可行流

区别仅是出点和入点这两个点不用满足出入流平衡，那么从汇点连无线流量到源点（不是上面定义的超级源汇点），即可。

有源汇有上下界最大流

首先跑一遍有源汇有上下界可行流，然后关注残余网络，s->t图中剩下的流量是我们可以人为安排的，所以再从原来的源点到汇点来一次的最大流即是答案。

由于S没有入边，而T没有出边，因此增广路不会经过S,T也就不会导致约束条件失效（即始终满足流量平衡）。

（最后答案由两部分构成，之前的可行流flow1，和之后的增广流flow2的和。注意到第一次求可行流时，已经有了一条s->t的流量为flow1的边，所以直接再自从s->t跑一次最大流就是flow1+flow2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
inline int getint(){
	int summ=0,f=1;char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-')f=-1,ch=getchar();
	for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
	return summ*f;
}

const int M=3e5;
int n,m,cnt,tot=1,s,t,S,T,sum;
int nex[M],go[M],G[M],To[M],F[M],L[M],R[M],head[M],w[M],dep[2000],C[M],D[M],W[M],cur[M];


inline void Pre(){
	memset(head,0,sizeof(head));cnt=0;tot=1;sum=0;
	memset(W,0,sizeof(W));
}
inline void Add(int u,int v,int val){
	nex[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=val;
	swap(u,v);
	nex[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=0;
}

inline bool bfs(int ss,int tt){
	queue<int> q;memset(dep,-1,sizeof(dep));
	q.push(ss);dep[ss]=1;
	for(int i=1;i<=n+m+4;i++) cur[i]=head[i];
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=nex[i]){
			int v=go[i];
			if(w[i]&&dep[v]==-1){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[tt]!=-1;
}
int dfs(int u,int tt,int flow){
	if(u==tt) return flow;
	int res=0;
	for(int i=cur[u];i;i=nex[i]){
		cur[u]=i;
		int v=go[i];
		if(w[i]&&dep[v]==dep[u]+1){
			int sum=dfs(v,tt,min(w[i],flow-res));
			if(sum){
				w[i]-=sum;w[i^1]+=sum;res+=sum;
			}
			else dep[v]=-1;
			if(flow==res) return res;
		}
	}
	return res;
}

inline int calc(){
	for(int i=1;i<=cnt;i++){
		Add(F[i],To[i],R[i]-L[i]);
		W[F[i]]-=L[i];W[To[i]]+=L[i];
	}
	for(int i=1;i<=n+m+4;i++){
		if(W[i]>0) Add(S,i,W[i]),sum+=W[i];
		else if(W[i]<0)Add(i,T,-W[i]);
	}
	Add(t,s,1e9);
	int res=0;
	while(bfs(S,T)) res+=dfs(S,T,1e9);
	if(res!=sum) return -1;
	int ans=0;
	while(bfs(s,t)) ans+=dfs(s,t,1e9);
	return ans;
}

inline void Solve(){
	Pre();
	s=n+m+1,t=n+m+2;S=n+m+3;T=n+m+4;
	for(int i=1;i<=m;i++){
		G[i]=getint();
		F[++cnt]=n+i;To[cnt]=t;L[cnt]=G[i];R[cnt]=1e9;
	}
	for(int i=1;i<=n;i++){
		C[i]=getint();D[i]=getint();
		for(int j=1;j<=C[i];j++){
			F[++cnt]=i;To[cnt]=getint()+1+n;L[cnt]=getint();R[cnt]=getint();//day->people
		}
		F[++cnt]=s;To[cnt]=i;L[cnt]=0;R[cnt]=D[i];
	}
	cout<<calc()<<"\n\n";
}

int main(){
	while(cin>>n>>m) Solve();
	return 0;	
}

无源汇有上下界费用流

同样先建边平衡流量（同时统计必要的边的流量），然后从超级源点到超级会点跑最大流最小费用即可。

有源汇有上下界费用流

把初始汇点到初始源点加一条流量无限的边即可。