【模板】有源汇上下界最大流

东方文花帖|【模板】有源汇上下界最大流

说是模板，其实题意也不是那么简单易懂。

认真阅读题目后，建出下面的图

做完这个题可以更加理解 有源汇上下界最大流

源点全是出边，汇点全是入边会更好理解。

此时加的addEdge(t,s,inf) 的反向边的流量就是基础流量，然后去掉再跑最大流，两个流加起来。

左边的是 1-n 天， 右边是 1-m 个美少女

问题就是求 s 到 t 的有源汇上下界最大流

注意美少女的编号从 0 开始

/*
 * @Author: zhl
 * @Date: 2020-10-20 11:09:59
 */
#include<bits/stdc++.h>
 //#define int long long
using namespace std;

const int N = 2e6 + 10, M = 2e6 + 10, inf = 1e9;
int n, m, s, t, tot, head[N];
int ans, dis[N], cur[N];

struct Edge {
	int to, next, flow;
}E[M << 1];

void addEdge(int from, int to, int w) {
	E[tot] = Edge{ to,head[from],w };
	head[from] = tot++;
	E[tot] = Edge{ from,head[to],0 };
	head[to] = tot++;
}

int bfs() {
	for (int i = 0; i <= n + m + 3; i++) dis[i] = -1;
	queue<int>Q;
	Q.push(s);
	dis[s] = 0;
	cur[s] = head[s];

	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int i = head[u]; ~i; i = E[i].next) {
			int v = E[i].to;
			if (E[i].flow && dis[v] == -1) {
				Q.push(v);
				dis[v] = dis[u] + 1;
				cur[v] = head[v];
				if (v == t)return 1; //分层成功
			}
		}
	}
	return 0;
}

int dfs(int x, int sum) {
	if (x == t)return sum;
	int k, res = 0;
	for (int i = cur[x]; ~i && res < sum; i = E[i].next) {
		cur[x] = i;
		int v = E[i].to;
		if (E[i].flow > 0 && (dis[v] == dis[x] + 1)) {
			k = dfs(v, min(sum, E[i].flow));
			if (k == 0) dis[v] = -1; //不可用
			E[i].flow -= k; E[i ^ 1].flow += k;
			res += k; sum -= k;
		}
	}
	return res;
}

int Dinic() {
	int ans = 0;
	while (bfs()) {
		ans += dfs(s, inf);
	}
	return ans;
}

int val[N];
int minF[N];
signed main() {
	while(~scanf("%d%d",&n,&m)){
		memset(head,-1,sizeof(int)*(n+m+10));
		memset(val,0,sizeof(int)*(n+m+10));
		tot = 0;
		for(int i = 1;i <= m;i++){
			int x;scanf("%d",&x);
			addEdge(n+i,n+m+1,inf-x);
			val[n+i]-=x;
			val[n+m+1]+=x;
		}
		
		for(int i = 1;i <= n;i++){
			int c,d;
			scanf("%d%d",&c,&d);
			addEdge(0,i,d);
			val[0] -= 0;
			val[i] += 0;
			for(int j = 1;j <= c;j++){
				int u,l,r;
				scanf("%d%d%d",&u,&l,&r);
				addEdge(i,u+n+1,r-l);
				val[i] -= l;
				val[u+n+1] += l;
			}
		}
		
		s = n + m + 2;t = n + m + 3;
		int sum = 0;
		for(int i = 0;i <= n + m + 1;i++){
			if(val[i] > 0){
				addEdge(s,i,val[i]);
				sum += val[i];
			}
			if(val[i] < 0)addEdge(i,t,-val[i]);
		}
		addEdge(n+m+1,0,inf);
        int dd = Dinic();
		//cout << dd << endl;
        //cout << sum << endl;
		if(dd == sum){
			int res = E[tot-1].flow;
			E[tot-1].flow = E[tot-2].flow = 0;
            s = 0;t = n + m + 1;
			printf("%d
",res + Dinic());
		}
		else printf("-1
");
        puts("");
    }
}