P4662 [BalticOI 2008]黑手党（最小割）

刺骨的言语ヽ痛彻心扉 2021-09-29 14:56 219阅读 0赞

经典的割点模型。  
考虑裂点操作，一个点i变成两个点 i i i和 i + n i+n i\+n，两点中间连边的权为原来点的权。因为起始点和终点可以被割，所以 S = s S=s S=s， T = t + n T=t+n T=t\+n  
输出方案时，直接在残余网络dfs（只走流量有剩余的边），最后遍历，如果一个点的入点被访问到了，但出点没有被访问到，就说明这个点被割了。最后排序输出就行了。

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    const int maxn = 400+100;
    const int maxm = 1e5+100;
    const int inf = 0x7f7f7f7f;
    
    int vis[maxn];
    typedef struct Dinic
    { 
    	typedef struct Edge
    	{ 
    		int u,v,w,nxt;	
    	} Edge;
    	int head[maxn],hcnt;
    	int dep[maxn];
    	int cur[maxn];
    	Edge e[maxm];
    	int S,T,N;
    	void init()
    	{ 
    		memset(head,-1,sizeof head);
    		hcnt = 2;
    		S = T = N = 0;
    	}
    	void adde(int u,int v,int w)
    	{ 
    		e[hcnt].u = u,e[hcnt].v = v,e[hcnt].w = w;
    		e[hcnt].nxt = head[u];head[u] = hcnt++;
    		e[hcnt].u = v,e[hcnt].v = u,e[hcnt].w = 0;
    		e[hcnt].nxt = head[v];head[v] = hcnt++;
    	}
    	int  bfs()
    	{ 
    		rep(i,0,N)
    		{ 
    			dep[i] = inf;
    		}
    		queue<int> q;
    		q.push(S); dep[S] = 0;
    		while(!q.empty())
    		{ 
    			int u = q.front();q.pop();
    			for(int i = head[u];~i;i = e[i].nxt)
    			{ 
    				int v = e[i].v,w = e[i].w;
    				if(w > 0 && dep[u] + 1 < dep[v])
    				{ 
    					dep[v] = dep[u] + 1;
    					if(v == T)
    					{ 
    						return 1;
    					}
    					q.emplace(v);
    				}
    			}
    		}
    		return dep[T] != inf;
    	}
    	int dfs(int s,int mw)
    	{ 
    		if(s == T) return mw;
    		for(int i = cur[s];~i;i=e[i].nxt)
    		{ 
    			cur[s] = i;
    			int v = e[i].v,w=e[i].w;
    			if(w <= 0 || dep[v] != dep[s] + 1)
    			{ 
    				continue;
    			}
    			int cw = dfs(v,min(w,mw));
    			if(cw <= 0)
    				continue;
    			e[i].w -= cw;
    			e[i^1].w += cw;
    			return cw;				
    		}
    		return 0;
    	}
    	ll dinic()
    	{ 
    		ll res = 0;
    		while(bfs())
    		{ 
    			rep(i,0,N)
    			{ 
    				cur[i] = head[i];
    			}
    			while(int d = dfs(S,inf))
    			{ 
    				res += 1ll * d;
    			}
    		}
    		return res;
    	}
    	void dfs1(int u)
    	{ 
    		vis[u] = 1;
    		for(int i = head[u];~i;i = e[i].nxt)
    		{ 
    			int v = e[i].v;
    			if(e[i].w && !vis[v])
    				dfs1(v);
    		}	
    	}
    
    	void solve()
    	{ 
    		VI ans;
    		for(int i = 2;i<=hcnt;i+=2)
    		{ 
    			int u = e[i^1].v,v = e[i].v;
    			if(vis[u] && !vis[v])
    				ans.pb(u);
    		}
    
    		//cout << ans.size() << endl;
    		rep(i,0,ans.size())
    		{ 
    			if(i == 0)
    			printf("%d",ans[i]);
    			else
    			{ 
    				printf(" %d",ans[i]);
    			}
    		}
    		printf("\n");
    	}
    } Dinic;
    
    int n,m,s,t;
    
    
    int main(int argc, char const *argv[])
    { 
    	while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
    	{ 
    		Dinic din;din.init();
    		memset(vis,0,sizeof vis);
    		int w;
    		rep(i,1,n+1)
    		{ 
    			scanf("%d",&w);
    			din.adde(i,i+n,w);
    		}
    		int x,y;
    		rep(i,1,m+1)
    		{ 
    			scanf("%d%d",&x,&y);
    			din.adde(x+n,y,inf);
    			din.adde(y+n,x,inf);
    		}
    		din.S = s,din.T = t+n;
    		din.N = 2*n+3;
    		din.dinic();
    		//cout << din.dinic() << endl;
    		din.dfs1(s);
    		din.solve();
    	}
    
    	return 0;
    }