bzoj1339[Baltic2008]Mafia

題意：

匪徒準備從一個車站轉移毒品到另一個車站，警方準備進行布控。對于每個車站進行布控都需要一定的代價，現在警方希望使用最小的代價控制一些車站,使得去掉這些車站后，匪徒無法從原定的初始點到達目標點。n≤200。

題解：

每個點拆成兩個點，邊權為點權，原圖中的邊邊權為正無窮，然后跑最小割。

代碼：

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 60010 7 #define INF 0x3fffffff 8 using namespace std; 9 10 inline int read(){ 11 char ch=getchar(); int f=1,x=0; 12 while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} 13 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 14 return f*x; 15 } 16 struct e{int t,c,n;}es[maxn*2]; int g[maxn],ess; 17 void pe(int f,int t,int c){ 18 es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess; 19 } 20 int h[maxn]; queue<int>q; 21 bool bfs(int s,int t){ 22 memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s); 23 while(!q.empty()){ 24 int x=q.front(); q.pop(); 25 for(int i=g[x];i;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t); 26 } 27 return h[t]!=-1; 28 } 29 int dfs(int x,int t,int f){ 30 if(x==t)return f; int u=0,w; 31 for(int i=g[x];i;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){ 32 w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(!f)return u; 33 } 34 if(!u)h[x]=-1; return u; 35 } 36 int dinic(int s,int t){int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;} 37 int n,m,s,t; 38 int main(){ 39 n=read(); m=read(); s=read(); t=n+read(); ess=1; inc(i,1,n){int x=read(); pe(i,n+i,x);} 40 inc(i,1,m){int x=read(),y=read(); pe(n+x,y,INF); pe(n+y,x,INF);} printf("%d",dinic(s,t)); return 0; 41 }

?

20161111

轉載于:https://www.cnblogs.com/YuanZiming/p/6055470.html

總結

以上是生活随笔為你收集整理的bzoj1339[Baltic2008]Mafia*的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。