网络流/最大流
比较裸的最大流= =
无向图上走来回其实就等价与走两遍>_>
如果路径有相交其实不影响答案的
比较恶心的是两个人路过同一座桥，但走的方向不同互相抵消流量了……
其实只要在第一遍跑网络流以后如果为Yes，就将其中一人的起点终点交换，再跑一遍就可以了
UPD：其实N=55就可以了，不需要像我代码里那样开到3000……因为只有n个点= =不是$n^2$的
/**************************************************************
Problem: 3504
User: Tunix
Language: C++
Result: Accepted
Time:44 ms
Memory:2500 kb
****************************************************************/ //BZOJ 3504
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=1e5+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,tot,ans,a1,a2,an,b1,b2,bn;
char mp[][];
struct edge{int to,v;};
struct Net{
edge E[M];
int head[N],next[M],cnt;
void ins(int x,int y,int v){
E[++cnt]=(edge){y,v};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int v){
ins(x,y,v); ins(y,x,);
}
int s,t,cur[N],d[N],Q[N];
bool mklevel(){
memset(d,-,sizeof d);
d[s]=;
int l=,r=-;
Q[++r]=s;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[t]!=-;
}
int dfs(int x,int a){
if (x==t) return a;
int flow=;
for(int &i=cur[x];i && flow<a;i=next[i])
if (E[i].v && d[E[i].to]==d[x]+){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()){
F(i,s,t) cur[i]=head[i];
ans+=dfs(s,INF);
}
}
void init(){
s=; t=n+; cnt=; ans=;
memset(head,,sizeof head);
F(i,,n){
scanf("%s",mp[i]+);
F(j,,n){
if (mp[i][j]=='N') add(i,j,INF);
else if (mp[i][j]=='O') add(i,j,);
}
}
add(s,a1+,an*); add(a2+,t,an*);
add(s,b1+,bn*); add(b2+,t,bn*);
Dinic();
if (ans==an*+bn*){
cnt=; memset(head,,sizeof head);
F(i,,n) F(j,,n){
if (mp[i][j]=='N') add(i,j,INF);
else if (mp[i][j]=='O') add(i,j,);
}
add(s,a1+,an*); add(a2+,t,an*);
add(s,b2+,bn*); add(b1+,t,bn*);
ans=; Dinic();
if (ans==an*+bn*) puts("Yes");
else puts("No");
}else puts("No");
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("3504.in","r",stdin);
freopen("3504.out","w",stdout);
#endif
while(scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF)
G1.init();
return ;
}
3504: [Cqoi2014]危桥
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 588 Solved: 313
[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
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
No
数据范围
4<=N<50
O<=a1, a2, b1, b2<=N-1
1 <=an. b<=50