自动搬运

查看原文

来自洛谷，原作者为

	Dream_poetry 锁阁自此隽长永，孤影凭梦绘常恒。 || 孤举敬卿花间酒，盼君余载尽欢春 || 一别复还阻且漫，云念君瞳拨青岚 || 缕缕幽籁余音浅，明灭烛星殿前欢

搬运于2025-08-24 23:11:02，当前版本为作者最后更新于2025-03-09 19:40:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

一眼网络流，但是需要一些神奇的建边方式。

我们考虑建立超级源点和超级汇点，并把每个点拆分为 $x1,x2$，分别表示两种情况。

我们让超级源点像每个 $x1$ 建一条容量为 $A_x$ 的单向边，反边正常建为 $0$ 就行。

随后，我们从 $x1$ 向 $x2$ 建一条容量为 $B_x$ 的单向边，反边正常建为 $0$。

考虑对于每一条限制，让 $x_2$ 向 $y_1$ 建边，边权正无穷，以表明约束关系。反边照旧。

最后，我们考虑让 $q_2$ 直接连向汇点，边权设为正无穷。

不难发现，我们这种建边方式满足了我们需要达成的限制，通过观察和模拟，也不难发现我们要求的答案就是最小割。

按最大流最小割定理，把最大流一求，输出即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int Maxn=1e12; 

struct node{
	int nex,to,val;
}e[1000005];
int tot=1;
int he[1000005];

inline void add(int x,int y,int w){
	e[++tot].nex=he[x];
	e[tot].to=y;
	e[tot].val=w;
	he[x]=tot;
}

int a[1000005];
int p[1000005];

int q;



int ans;

int dis[1000005];
int now[1000005];
int s,t;


inline int bfs(){
	for (int i=1;i<=2*n+2;i++){
		dis[i]=Maxn;
	}
	queue<int>q;
	q.push(s);
	dis[s]=0;
	now[s]=he[s];
	while(q.size()){
		int x=q.front();
		q.pop();
		for (int i=he[x];i;i=e[i].nex){
			int v=e[i].to;
			if (e[i].val>0 && dis[v]==Maxn){
				q.push(v);
				now[v]=he[v];
				dis[v]=dis[x]+1;
				if (v==t){
					return 1;
				}
			}
		}
	} 
	return 0;
}

inline int dfs(int x,int sum){
	if (x==t){
		return sum;
	}
	int res=0;
	for (int i=now[x];i && sum;i=e[i].nex){
		now[x]=i;
		int v=e[i].to;
		if (e[i].val>0 && (dis[v]==dis[x]+1)){
			int k=dfs(v,min(sum,e[i].val));
			if (k==0){
				dis[v]=Maxn;
			}
			e[i].val-=k;
			e[i^1].val+=k; 
			res+=k;
			sum-=k;
		}
	}
	return res;
}



int x[1000005];
int y[1000005];

signed main(){
	cin>>n>>m;
	s=2*n+2;
	t=2*n+1;
	for (int i=1;i<=m;i++){
		cin>>x[i]>>y[i];
	}
	for (int i=1;i<=n;i++){
		cin>>a[i];
	} 
	for (int j=1;j<=n;j++){
		cin>>p[j];
	}
	
	for (int i=1;i<=n;i++){
		add(s,i,a[i]);
		add(i,s,0);
	}
	for (int i=1;i<=n;i++){
		add(i,i+n,p[i]);
		add(i+n,i,0);
	}
	
	for (int i=1;i<=m;i++){
		add(x[i]+n,y[i],Maxn);
		add(y[i],x[i]+n,0);
	}
	cin>>q;
	add(q+n,t,Maxn);
	add(t,q+n,0);
	while(bfs()){
		ans+=dfs(s,Maxn);
	} 
	
	cout<<ans;
	
	return 0;
}