nyoj 677 碟战(最大流最小割定理)
生活随笔
收集整理的這篇文章主要介紹了
nyoj 677 碟战(最大流最小割定理)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
碟戰(zhàn)
時間限制：2000?ms ?|? 內(nèi)存限制：65535?KB 難度：4 描述知己知彼，百戰(zhàn)不殆！在戰(zhàn)爭中如果被敵人掌握了自己的機(jī)密，失敗是必然的。K國在一場戰(zhàn)爭中屢屢失敗，就想到自己的某些城市可能會有敵方的間諜。
在仔細(xì)調(diào)查后，終于得知在哪些城市存在間諜。當(dāng)然這個消息也被敵方間諜得知，所以間諜們開始撤離，試圖到達(dá)K國唯一機(jī)場，然后搶奪飛機(jī)回國。由于城市內(nèi)部比較復(fù)雜，K國領(lǐng)導(dǎo)人決定封鎖道路，阻止所有間諜到達(dá)機(jī)場。城市編號為1~N，兩個城市有不超過1條雙向道路相連。機(jī)場在N號城市，不會有間碟。
由于要節(jié)約兵力，至少要封鎖多少條道路才能阻止所有間諜到達(dá)機(jī)場？
輸入接下來每組測試數(shù)據(jù)第一行包含三個整數(shù)n,m,p（2<= n <= 200,1< m < 20000,1 <= p < n),分別表示城市數(shù)量，道路數(shù)量，存在間諜的城市的數(shù)量。
接下來的一行包含p個整數(shù)x（1 <= x < n),表示存在間諜城市的編號。
接下來的m行，每行包含兩個整數(shù)i,j，表示城市i與城市j有道路相通。
解題思路：簡單的最大流最小割定理，設(shè)置一個超級源點(diǎn)，與所有有間諜的城市連一條邊，容量為無窮大，表示不會去割這條邊，然后其它邊不變，容量為1，注意要連雙向邊，匯點(diǎn)為N號節(jié)點(diǎn)。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 1000; const int INF = 0x3f3f3f3f; struct Edge {int to,next,flow; }edge[160005]; int n,m,p; int head[maxn],level[maxn],cnt;void addedge(int u,int v,int flow) { edge[cnt].to = v; edge[cnt].flow = flow; edge[cnt].next = head[u]; head[u] = cnt++; swap(u,v); edge[cnt].to = v; edge[cnt].flow = 0; edge[cnt].next = head[u]; head[u] = cnt++; } int BFS(int src,int des){ queue<int>q; memset(level,0,sizeof(level)); level[src]=1; q.push(src); while(!q.empty()){ int u = q.front(); q.pop(); if(u==des) return 1; for(int k = head[u];k!=-1;k=edge[k].next){ int v = edge[k].to,w=edge[k].flow; if(level[v]==0&&w!=0){ level[v]=level[u]+1; q.push(v); } } } return -1; } int dfs(int u,int des,int increaseRoad){ if(u==des) return increaseRoad; int ret=0; for(int k=head[u];k!=-1;k=edge[k].next){ int v = edge[k].to,w=edge[k].flow; if(level[v]==level[u]+1&&w!=0){ int MIN = min(increaseRoad-ret,w); w = dfs(v,des,MIN); if(w > 0) { edge[k].flow -= w; edge[k^1].flow += w; ret+=w; if(ret==increaseRoad) return ret; } else level[v] = -1; } } return ret; } int Dinic(int src,int des){ int ans = 0; while(BFS(src,des)!=-1) ans+=dfs(src,des,INF); return ans; } int main() {int t,u,v,cas = 1;scanf("%d",&t);while(t--){cnt = 0;memset(head,-1,sizeof(head));scanf("%d %d %d",&n,&m,&p);for(int i = 1; i <= p; i++){scanf("%d",&u);addedge(0,u,INF);}for(int i = 1; i <= m; i++){scanf("%d %d",&u,&v);addedge(u,v,1);addedge(v,u,1);}printf("Case #%d: %d\n",cas++,Dinic(0,n));}return 0; }總結(jié)
以上是生活随笔為你收集整理的nyoj 677 碟战(最大流最小割定理)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Eclipse 常用快捷键，实战经典
- 下一篇： nyoj 1261 音痴又音痴的LT(离