题解：P4662 [BalticOI 2008] 黑手党 (Day0)

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int maxn=1e3+5;
const int maxm=1e5+5;
const int INF=0x3f3f3f3f;
struct node {
	int v;
	int id;
};
int n,m;
int ss,tt;
int ans=0;
int pre[maxn],pre1[maxn];
int dep[maxn];
int a[maxn];
vector<node>g[maxn];
int tot=0;
int w[maxm];
bool vis[maxn];
void add (int u,int v,int ww) {
	g[u].push_back({v,tot});
	g[v].push_back({u,tot^1});
	w[tot]=ww;
	tot+=2;
}
bool bfs (int x) {
	memset(dep,0,sizeof(dep));
	memset(pre,0,sizeof(pre));
	memset(pre1,0,sizeof(pre1));
	queue<int>q;
	q.push(x);
	dep[x]=1;
	while (!q.empty()) {
		int u=q.front();
		q.pop();
		for (auto i:g[u]) {
			int v=i.v;
			int id=i.id;
			if (dep[v]==0&&w[id]>0) {
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[tt];
}
int dfs (int u,int f) {
	if (u==tt) return f;
	int res=0;
	for (auto i:g[u]) {
		int v=i.v;
		int id=i.id;
		if (dep[v]<=dep[u]) continue;
		if (w[id]==0) continue;
		int f2=dfs(v,min(f-res,w[id]));
		res+=f2;
		w[id]-=f2;
		w[id^1]+=f2;
		if (res==f) break;
	}
	return res;
}
void dinic () {
	while (bfs(ss)) ans+=dfs(ss,INF);
}
void getg (int u) {
	vis[u]=1;
	for (auto i:g[u]) {
		int v=i.v;
		int id=i.id;
		if (!vis[v]&&w[id]>0) getg(v);
	}
}

signed main () {
	cin>>n>>m>>ss>>tt; tt+=n;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=m;i++) {
		int x,y;
		cin>>x>>y;
		add(x+n,y,INF);
		add(y+n,x,INF);
	}
	for (int i=1;i<=n;i++) {
		if (i!=tt) add(i,i+n,a[i]);
	}
	dinic();
	getg(ss);
	for (int i=1;i<=n;i++) if (vis[i]^vis[i+n]) cout<<i<<' ';
	return 0;
}