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=INFs–an–>a1 a2–an–>t –bn–>b1 b2–bn–>t看是否满流即可但是有个问题，a1的流量可能流到b2，同时b1的到a2 于是，交换b1和b2的位置，再做一遍最大流看是否满流，满流则可行为什么呢？linkct讲课说，两个流f1和f2可行，|f1+f2|/2也可行(平均都小于每一个)证明具体忘了，自己又想了一下，不一定对考虑前后两次流，第一次：f1a1–>a2 an-xb1–>b2 an-xa1–>b2 xa2–>b1 x第二次：f2a1–>a2 an-xb2–>b1 an-xa1–>b1 xb2–>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=,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; 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<<];
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=;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[v];h[v]=cnt;
}
int q[N],head,tail,vis[N],d[N];
bool bfs(){
memset(vis,,sizeof(vis));
memset(d,,sizeof(d));
head=tail=;
q[tail++]=s;d[s]=;vis[s]=;
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]=;
d[v]=d[u]+;
if(v==t) return true;
q[tail++]=v;
}
}
}
return false;
}int cur[N];
int dfs(int u,int a){
if(u==t||a==) return a;
int flow=,f;
for(int &i=cur[u];i;i=e[i].ne){
int v=e[i].v;
if(d[v]==d[u]+&&(f=dfs(v,min(a,e[i].c-e[i].f)))>){
flow+=f;
e[i].f+=f;
e[((i-)^)+].f-=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int dinic(){
int flow=;
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=;t=n+;
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=;memset(h,,sizeof(h));
for(int i=;i<=n;i++)
for(int j=i+;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()+;a2=read()+;an=read()*;
b1=read()+;b2=read()+;bn=read()*;
cnt=;memset(h,,sizeof(h));
for(int i=;i<=n;i++){
scanf("%s",ss+);
for(int j=i+;j<=n;j++){
if(ss[j]=='O') ins(i,j,),g[i][j]=;
else if(ss[j]=='N') ins(i,j,INF),g[i][j]=INF;
else g[i][j]=;
}
}
if(solve()) puts("Yes");
else puts("No");
}
}
