网络流/最大流

---

　　比较裸的最大流= =

　　无向图上走来回其实就等价与走两遍>_>

　　如果路径有相交其实不影响答案的

　　比较恶心的是两个人路过同一座桥，但走的方向不同互相抵消流量了……

　　其实只要在第一遍跑网络流以后如果为Yes，就将其中一人的起点终点交换，再跑一遍就可以了

 

UPD：其实N=55就可以了，不需要像我代码里那样开到3000……因为只有n个点= =不是$n^2$的

1 /**************************************************************  2     Problem: 3504  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:44 ms  7     Memory:2500 kb  8 ****************************************************************/  9   10 //BZOJ 3504 11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 #include
          
            16 #include
           
             17 #define rep(i,n) for(int i=0;i
            
             =n;--i) 20 #define pb push_back 21 using namespace std; 22 inline int getint(){ 23 int v=0,sign=1; char ch=getchar(); 24 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();} 25 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();} 26 return v*sign; 27 } 28 const int N=3010,M=1e5+10,INF=~0u>>2; 29 typedef long long LL; 30 /******************tamplate*********************/ 31 int n,m,tot,ans,a1,a2,an,b1,b2,bn; 32 char mp[55][55]; 33 struct edge{ int to,v;}; 34 struct Net{ 35 edge E[M]; 36 int head[N],next[M],cnt; 37 void ins(int x,int y,int v){ 38 E[++cnt]=(edge){y,v}; 39 next[cnt]=head[x]; head[x]=cnt; 40 } 41 void add(int x,int y,int v){ 42 ins(x,y,v); ins(y,x,0); 43 } 44 int s,t,cur[N],d[N],Q[N]; 45 bool mklevel(){ 46 memset(d,-1,sizeof d); 47 d[s]=0; 48 int l=0,r=-1; 49 Q[++r]=s; 50 while(l<=r){ 51 int x=Q[l++]; 52 for(int i=head[x];i;i=next[i]) 53 if (d[E[i].to]==-1 && E[i].v){ 54 d[E[i].to]=d[x]+1; 55 Q[++r]=E[i].to; 56 } 57 } 58 return d[t]!=-1; 59 } 60 int dfs(int x,int a){ 61 if (x==t) return a; 62 int flow=0; 63 for(int &i=cur[x];i && flow
            
           
          
         
        
       
      

3504: [Cqoi2014]危桥

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 588  Solved: 313

[][][]

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

HINT

Source

[ ][ ][ ]