問題描述?
隨著資本的擴大，藏寶海灣貿易親王在卡利姆多和東部王國大陸各建立了N/2 個港口。大災變發生以后，這些港口之間失去了聯系，相繼脫離了藏寶海灣貿易親王的管轄，各自為政。利益的驅動使得每個港口都想和對岸大陸的另一個港口建立貿易合作關系，由于地理位置因素，只有存在直接到達的航線的兩個港口才能建立合作，而且每個港口只與對岸一個港口建立合作，因此并不是所有的港口都能找到合作伙伴。?
?
血帆海盜得知這一消息以后，決定對其中一條航線進行干擾性的掠奪。經過分析，血帆海盜計算出最多能有W 對港口合作。如果兩個港口之間只有一條航線，而且這條航線恰好是血帆海盜要掠奪的航線，這兩個港口將不能建立合作關系。血帆海盜指揮官菲爾拉倫想知道他們有幾種選擇，可以讓地精們無法建立W 對港口。?

?

輸入格式
第1行，兩個整數N,M，表示一共的港口個數和航線條數。?
接下來M行，每行兩個整數A,B，表示卡利姆多的港口A與東部王國的港口B之間有一條航線直接連接，其中1<=A<=N/2，N/2+1<=B<=N。

輸出格式
一個整數，表示血帆海盜可以選擇掠奪的航線條數。?
?
解釋：如果掠奪一條航線以后，地精依然可以建立起最多的W個合作關系（可以有多種），
那么這條航線是不值得掠奪的，否則就是掠奪方案之一。

樣例輸入?
8 5?
1 5?
1 6?
2 7?
3 7?
4 8

樣例輸出?
1

樣例說明?
地精做多能建立起合作關系的數量為3，掠奪(4,8)這條航線后，最多能建立的合作關系的
數量減少為2。

數據規模?
40%的數據滿足2<=N<=200，1<=M<=1000?
100%的數據滿足2<=N<=100000，1<=M<=100000，保證N為偶數

?

by ? BYVoid

?

【題解】

? ? 網絡流第一道比較有難度的題，毀半下午一晚上，不過收獲還不錯。網絡流當然沒有什么好說的，明顯點和邊都給出來了，建一個原點一個匯點即可。關鍵是怎樣在網絡流的基礎上找出能“破壞”最大流的關鍵邊。

? ? 一開始的想法是在dinic的板子里直接做變動，記錄那些滿載邊(類似最小瓶頸生成樹？)。但是首先，改板子這個事本來就不靠譜(比如KMP的動物園那個題)，其次一個邊沒有被改動過不能代表它不重要，這道題的邊權只代表存在與否，所以全是01滿載也沒有意義。然后就開始在剩余圖上做文章，想用并查集標記一下最大流里的邊兩端是否仍連通。發現這樣一來只要有一個還連著整個圖就和合一氣了，明顯不靠譜。然后開始艱辛的dfs，從源點搜反圖從匯點搜正圖，后來還是搜得很凌亂，調出樣例交一下一個點都沒有A。

? ? 最后還是非常虛地看了學長代碼(這題網上根本沒有題解啊摔，果然還是我太弱？)。發現用tarjan縮一下點好像問題就解決了？開開心心地繼續去順著tarjan的思路想。最近tarjan打得很多，不用板子就背下來了可喜可賀可喜可賀。但是為什么成立呢……調出來當時講課的ppt看了很多回強連通分量的定義，每兩個點之間都有路徑可達，不管是環還是別的什么滿足條件的圖都可以，用的最多的還是環吧。因為網絡流里正邊載重反邊就會連通，如果這條線路是可以替換的話正好和源點或匯點一起連成一個強連通分量，不可替換的邊則兩端會分屬不同的強連通分量。一遍tarjan縮點之后枚舉給出的每一條邊，如果一個被使用的邊(表現為邊權為0)兩端在一個強連通分量里，它沒有“打擊的意義”，把答案從最大流的基礎上-1。所以說，我打了大半個晚上煞費苦心地在tarjan里區分正邊反邊，再在枚舉時刨掉一大堆特殊情況，都是為了什么呀……果然還是dfs時留下的思維定式太深，在后面對tarjan的理解就不夠透徹。

? ? 做了這個題之后最大的發現是可以在殘余網絡里面跑其他圖論板子(這什么鬼發現)，尤其能跑起來的是在只有01邊權的殘余網絡里跑tarjan，極其interesting。

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<stack> 6 using namespace std; 7 const int sj=100005; 8 int n,m,h[sj],e,a1,a2,mid,jg,dep[sj]; 9 int ge,dfn[sj],low[sj],cnt,c[sj]; 10 struct B 11 { 12 int ne,v,w,u; 13 }b[sj*4]; 14 bool r[sj]; 15 void add(int x,int y,int z) 16 { 17 b[e].v=y; 18 b[e].w=z; 19 b[e].u=x; 20 b[e].ne=h[x]; 21 h[x]=e++; 22 } 23 void init() 24 { 25 scanf("%d%d",&n,&m); 26 memset(h,-1,sizeof(h)); 27 mid=n>>1; 28 for(int i=1;i<=m;i++) 29 { 30 scanf("%d%d",&a1,&a2); 31 add(a1,a2,1); 32 add(a2,a1,0); 33 r[a1]=1; 34 r[a2]=1; 35 } 36 for(int i=1;i<=mid;i++) 37 if(r[i]) add(0,i,1),add(i,0,0); 38 for(int i=mid+1;i<=n;i++) 39 if(r[i]) add(i,n+1,1),add(n+1,i,0); 40 memset(r,0,sizeof(r)); 41 } 42 queue<int> q; 43 int bfs(int x) 44 { 45 memset(dep,0,sizeof(dep)); 46 dep[x]=1; 47 while(!q.empty()) q.pop(); 48 q.push(x); 49 while(!q.empty()) 50 { 51 x=q.front(); 52 q.pop(); 53 for(int i=h[x];i!=-1;i=b[i].ne) 54 if(!dep[b[i].v]&&b[i].w) 55 { 56 dep[b[i].v]=dep[x]+1; 57 if(b[i].v==n+1) return 1; 58 q.push(b[i].v); 59 } 60 } 61 return 0; 62 } 63 int bj(int x,int y) 64 { 65 return x<y?x:y; 66 } 67 int dfs(int u,int f) 68 { 69 int ans=0; 70 if(u==n+1) return f; 71 for(int i=h[u],d;i!=-1;i=b[i].ne) 72 if(b[i].w&&dep[b[i].v]>dep[u]) 73 { 74 d=dfs(b[i].v,bj(f,b[i].w)); 75 f-=d; 76 ans+=d; 77 b[i].w-=d; 78 b[i^1].w+=d; 79 } 80 if(!ans) dep[u]=-1; 81 return ans; 82 } 83 stack<int> p; 84 int tarjan(int x) 85 { 86 dfn[x]=low[x]=++cnt; 87 p.push(x); 88 r[x]=1; 89 for(int i=h[x];i!=-1;i=b[i].ne) 90 { 91 if(!b[i].w) continue; 92 if(!dfn[b[i].v]) 93 { 94 tarjan(b[i].v); 95 low[x]=bj(low[x],low[b[i].v]); 96 } 97 else if(r[b[i].v]) 98 low[x]=bj(low[x],dfn[b[i].v]); 99 } 100 if(dfn[x]==low[x]) 101 { 102 int ww; 103 ge++; 104 do 105 { 106 ww=p.top(); 107 p.pop(); 108 r[ww]=0; 109 c[ww]=ge; 110 }while(ww!=x); 111 } 112 } 113 int main() 114 { 115 init(); 116 while(bfs(0)) jg+=dfs(0,0x3fff); 117 memset(r,0,sizeof(r)); 118 for(int i=1;i<=n;i++) 119 if(!dfn[i]) tarjan(i); 120 for(int i=1;i<=mid;i++) 121 for(int j=h[i];j!=-1;j=b[j].ne) 122 if(!b[j].w&&b[j].v!=0&&c[b[j].u]==c[b[j].v]) 123 jg--; 124 printf("%d",jg); 125 return 0; 126 } bloodsail

?

轉載于:https://www.cnblogs.com/moyiii-/p/7257554.html

總結

以上是生活随笔為你收集整理的血帆海盗的全部內容，希望文章能夠幫你解決所遇到的問題。

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