无源汇有上下界可行流

int main()
{
	cin >> n >> m;
	S = 0; T = n + 1;
	for (int i = 1; i <= m; ++i)
	{
		x = read(); y = read(); L[i] = read(); r = read();
		ADD(x, y, r - L[i]);
		A[x] -= L[i]; A[y] += L[i];
		c[i] = tot;
	}
	for (int i = 1; i <= n; ++i)
		if (A[i] > 0)ADD(S, i, A[i]), sum += A[i];
		else if (A[i])ADD(i, T, -A[i]);
	while (bfs(S, T))
		while (flow = dinic(S, inf))ans += flow;
	if (ans != sum)return puts("NO") == 23333;
	puts("YES");
	for (int i = 1; i <= m; ++i)Write(L[i] + e[c[i]].cap, 1), putchar('\n');
	return 0;
}

有源汇有上下界最大流

int main()
{
	cin >> n >> m >> S >> T;
	SS = 0; TT = n + 1;
	for (int i = 1; i <= m; ++i)
	{
		x = read(); y = read(); l = read(); r = read();
		ADD(x, y, r - l);
		A[x] -= l; A[y] += l;
	}
	for (int i = 1; i <= n; ++i)
		if (A[i] > 0) {ADD(SS, i, A[i]); sum += A[i];}
		else if (A[i])ADD(i, TT, -A[i]);
	ADD(T, S, inf);
	while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
	if (ans != sum)return puts("please go home to sleep") == 23333;
	ans = 0;
	while (bfs(S, T))while (flow = dinic(S, inf, T))ans += flow;
	cout << ans;
	return 0;
}

有源汇有上下界最小流

int main()
{
	cin >> n >> m >> S >> T;
	SS = 0; TT = n + 1;
	for (int i = 1; i <= m; ++i)
	{
		x = read(); y = read(); l = read(); r = read();
		ADD(x, y, r - l);
		A[x] -= l; A[y] += l;
	}
	for (int i = 1; i <= n; ++i)
		if (A[i] > 0) {ADD(SS, i, A[i]); sum += A[i];}
		else if (A[i])ADD(i, TT, -A[i]);
	while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
	ADD(T, S, inf);
	while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
	if (ans != sum)return puts("please go home to sleep") == 23333;
	cout << e[tot].cap;
	return 0;
}

上边仨loj上有原题（名没变）

有上下界费用流的建图方法

判断是否有源汇，若有，则从汇点向源点连容量为inf，费用为0的边。

建立超级源汇SS和TT。

对于原图x->y，下界为low，上界为high，连SS->y，容量为low，费用为原费用；同时x->y边容量变为high-low，费用不变。

对于每个点x，从连x->TT，容量为所有原图中x连向其它点的所有边的下界low之和（即出度），费用为0。

跑费用流即可。

--GXZlegend

关于主席树

if(pos<=mid)rson[k]=rson[pre],Insert(lson[pre],lson[k],l,mid,pos);
else lson[k]=lson[pre],Insert(rson[pre],rson[k],mid+1,r,pos);

---> rson[k]=rson[pre] lson[k]=lson[pre]死了不知道多少次了

透彻.jpg

https://www.luogu.com.cn/blog/zombie462/mosiyuan