Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2086 Solved: 1072
Description
Alice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双
向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？
本题有多组测试数据。
每组数据第一行包含7个空格隔开的整数，分别为N、al、a2、an、bl、b2、bn。
接下来是一个N行N列的对称矩阵，由大写字母组成。矩阵的i行j列描述编号i一1和j-l的岛屿间的连接情况，若为“O”则表示有危桥相连：为“N”表示有普通的桥相连：为“X”表示没有桥相连。
|
对于每组测试数据输出一行，如果他们都能完成愿望输出“Yes”，否则输出“No”。
4 0 1 1 2 3 1
XOXX
OXOX
XOXO
XXOX
4 0 2 1 1 3 2
XNXO
NXOX
XOXO
OXOX
Yes
No
数据范围
4<=N<50
O<=a1, a2, b1, b2<=N-1
1 <=an. b<=50
/**************************************************************
Problem: 3504
User: ictsing
Language: C++
Result: Accepted
Time:28 ms
Memory:1572 kb
****************************************************************/
//3504: [Cqoi2014]危桥
/*有N座岛屿，某些岛屿之间有桥相连，桥上的道路是双向的，
但一次只能供一人通行。其中一些桥是危桥。Alice希望在岛屿al和a2之间往返an次
（从al到a2再从a2 到al算一次往返）。
同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，
其余的桥可以无限次通行。判断两人能否达成愿望。
我们可以把无向图转化为有向图，因为按原路返回即可。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n,s,t,a1,a2,an,b1,b2,bn;
const int mt = 100+5;
int a[mt][mt];
char ss[mt];
const int mm = 10000+5;
int to[mm<<1],nxt[mm<<1],adj[mt],lev[mt],cap[mm<<1],cur[mt];
int ecnt;
const int inf = 0x3f3f3f3f;
queue<int>q;
void adde(int a,int b,int c)
{
ecnt++,to[ecnt]=b,nxt[ecnt]=adj[a],cap[ecnt]=c,adj[a]=ecnt;
//cout<<ecnt<<" "<<to[ecnt]<<" "<<cap[ecnt]<<" "<<nxt[ecnt]<<" "<<adj[ecnt]<<endl;
}
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
bool bfs()
{
while(!q.empty()) q.pop();
for(int i=s;i<=t;i++) lev[i]=-1,cur[i]=adj[i];
q.push(s),lev[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(lev[v]==-1&&cap[i]>0)
{
lev[v]=lev[u]+1;
q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dinic(int u,int flow)
{
if(u==t) return flow;
int delta,res=0;
for(int &i=cur[u];i;i=nxt[i])
{
int v=to[i];
if(lev[v]==lev[u]+1&&cap[i]>0)
{
delta=dinic(v,min(cap[i],flow-res));
if(delta)
{
cap[i]-=delta,cap[i^1]+=delta,res+=delta;
if(res==flow) break;
}
}
}
if(res!=flow) lev[u]=-1;
return res;
}
int maxflow()
{
int res=0;
while(bfs()) res+=dinic(s,inf);
return res;
}
bool build()
{
s=0,t=n+1,ecnt=1;
memset(adj,0,sizeof(adj));
adde(s,a1,an),adde(a1,s,0),adde(a2,t,an),adde(t,a2,0);
adde(s,b1,bn),adde(b1,s,0),adde(b2,t,bn),adde(t,b2,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]==1) adde(i,j,1),adde(j,i,0);
else if(a[i][j]==2) adde(i,j,inf),adde(j,i,0);
if(maxflow()==an+bn) return 1;
return 0;
}
int main()
{
while(~scanf("%d",&n))
{
a1=read(),a2=read(),an=read(),b1=read(),b2=read(),bn=read();
a1++,a2++,b1++,b2++;
for(int i=1;i<=n;i++)
{
scanf("%s",ss+1);
for(int j=1;j<=n;j++)
if(ss[j]=='O') a[i][j]=1;
else if(ss[j]=='N') a[i][j]=2;
else a[i][j]=0;
}
if(build())
{
swap(b1,b2);
if(build()) {puts("Yes");continue;}
}
puts("No");
}
return 0;
}
评论