3504: [Cqoi2014]危橋

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?1407??Solved:?703
[Submit][Status][Discuss]

Description

Alice和Bob居住在一個由N座島嶼組成的國家，島嶼被編號為0到N-1。某些島嶼之間有橋相連，橋上的道路是雙
向的，但一次只能供一人通行。其中一些橋由于年久失修成為危橋，最多只能通行兩次。Alice希望在島嶼al和a2之間往返an次（從al到a2再從a2到al算一次往返）。同時，Bob希望在島嶼bl和b2之間往返bn次。這個過程中，所有危橋最多通行兩次，其余的橋可以無限次通行。請問Alice和Bob能完成他們的愿望嗎？

Input

本題有多組測試數據。
每組數據第一行包含7個空格隔開的整數，分別為N、al、a2、an、bl、b2、bn。
接下來是一個N行N列的對稱矩陣，由大寫字母組成。矩陣的i行j列描述編號i一1和j-l的島嶼間的連接情況，若為“O”則表示有危橋相連：為“N”表示有普通的橋相連：為“X”表示沒有橋相連。
|

Output

對于每組測試數據輸出一行，如果他們都能完成愿望輸出“Yes”，否則輸出“No”。

?

?

Sample Input

4 0 1 1 2 3 1
XOXX
OXOX
XOXO
XXOX
4 0 2 1 1 3 2
XNXO
NXOX
XOXO
OXOX

Sample Output

Yes
No
數據范圍
4<=N<50
O<=a1, a2, b1, b2<=N-1
1 <=an. b<=50

---

雙向圖，往返=走好幾次--流量 危橋c=2，普通c=INF s--an-->a1 ? a2--an-->t ? --bn-->b1 ?b2--bn-->t 看是否滿流即可 但是有個問題，a1的流量可能流到b2，同時b1的到a2 于是，交換b1和b2的位置，再做一遍最大流看是否滿流，滿流則可行 為什么呢？ linkct講課說，兩個流f1和f2可行，|f1+f2|/2也可行(平均都小于每一個) 證明具體忘了，自己又想了一下，不一定對 考慮前后兩次流， 第一次：f1 a1-->a2 ?an-x b1-->b2 ?an-x a1-->b2 x a2-->b1 x 第二次：f2 a1-->a2 ?an-x b2-->b1 ?an-x a1-->b1 ?x b2-->a2 ?x 相加|f1+f2|/2: ?f(a1,a2)=an-x ?f(b1,b2)=0 ?f(a1,a2)=x ?所以f(a1,a2)=an 實現上的問題： 1.老老實實的重構圖 2.老老實實的保存邊容量 g[i][j]=0!!! 3.雙向圖反向邊c=c就行了 4.+1 *2 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=55,INF=1e9; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}return x*f; } int n,a1,a2,an,b1,b2,bn,s,t; int g[N][N]; int tot; char ss[N]; struct edge{int v,ne,c,f; }e[N*N<<1]; int cnt,h[N]; inline void ins(int u,int v,int c){cnt++;e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt;cnt++;e[cnt].v=u;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt; } int q[N],head,tail,vis[N],d[N]; bool bfs(){memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));head=tail=1;q[tail++]=s;d[s]=0;vis[s]=1;while(head!=tail){int u=q[head++];for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(!vis[v]&&e[i].c>e[i].f){vis[v]=1;d[v]=d[u]+1;if(v==t) return true;q[tail++]=v;}}}return false; }int cur[N]; int dfs(int u,int a){if(u==t||a==0) return a;int flow=0,f;for(int &i=cur[u];i;i=e[i].ne){int v=e[i].v;if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){flow+=f;e[i].f+=f;e[((i-1)^1)+1].f-=f;a-=f;if(a==0) break;}}return flow; } int dinic(){int flow=0;while(bfs()){for(int i=s;i<=t;i++) cur[i]=h[i];flow+=dfs(s,INF);}return flow; } int th[N],tc; bool solve(){s=0;t=n+1;ins(s,a1,an);ins(s,b1,bn);ins(a2,t,an);ins(b2,t,bn);int ans=dinic();//printf("ans1 %d\n",ans);if(ans!=an+bn) return false;cnt=0;memset(h,0,sizeof(h));for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++) if(g[i][j]) ins(i,j,g[i][j]);ins(s,a1,an);ins(s,b2,bn);ins(a2,t,an);ins(b1,t,bn);ans=dinic();//printf("ans2 %d\n",ans);if(ans!=an+bn) return false;return true; } int main(){//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){a1=read()+1;a2=read()+1;an=read()*2;b1=read()+1;b2=read()+1;bn=read()*2;cnt=0;memset(h,0,sizeof(h));for(int i=1;i<=n;i++){scanf("%s",ss+1);for(int j=i+1;j<=n;j++){if(ss[j]=='O') ins(i,j,2),g[i][j]=2;else if(ss[j]=='N') ins(i,j,INF),g[i][j]=INF;else g[i][j]=0;}}if(solve()) puts("Yes");else puts("No");} }

?

轉載于:https://www.cnblogs.com/candy99/p/6241419.html

總結

以上是生活随笔為你收集整理的BZOJ 3504: [Cqoi2014]危桥 [最大流]的全部內容，希望文章能夠幫你解決所遇到的問題。

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