P2944 [USACO09MAR]地震损失2Earthquake Damage 2

逃离我推掉我的手 2021-09-29 15:16 339阅读 0赞

题意：确定几个点不割，问最少割几个点使确定的点不能到达T  
拆点，每个点 i i i分成 i i i和 i + n i+n i\+n

*  对于确定不能拆的点， i i i连向 i + n i+n i\+n的边权为 i n f inf inf，同理，其他点 i i i连向 i + n i+n i\+n的边权为 1 1 1
 *  设置超级源点S，S连向所有确定的点，边权为 i n f inf inf，这里要注意S不能连向所有的点，因为题意是说这几个确定的点最后不能到T，而不是所有的点不能到T

#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 = 1e4+100;
    const int maxm = 1e5+100;
    const int inf = 0x7f7f7f7f;
    
    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 = 0;
    		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;
    	}
    }  Dinic;
    
    int n,m,s;
    
    int vis[maxn];
    int main(int argc, char const *argv[])
    { 
    	while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    	{ 
    		memset(vis,0,sizeof vis);
    		Dinic din; din.init();
    		din.S = 0,din.T = 1,din.N = 2*n+10;
    		int x,y;
    		rep(i,0,m)
    		{ 
    			scanf("%d%d",&x,&y);
    			din.adde(x+n,y,inf);
    			din.adde(y+n,x,inf);
    		}
    
    		rep(i,0,s)
    		{ 
    			scanf("%d",&x);
    			vis[x] = 1;
    			din.adde(x,x+n,inf);
    			din.adde(0,x,inf);
    		}
    
    		rep(i,1,n+1)
    		{ 
    			//din.adde(i+n,2*n+1,inf);
    			if(vis[i] == 0)
    			din.adde(i,i+n,1);
    		}
    
    		printf("%lld\n",din.dinic());
    
    	}
    	return 0;
    }