bzoj 3504 [Cqoi2014] 危橋

 

 

3504: [Cqoi2014]危橋

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 89 Solved: 65
[Submit][Status]

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

 

【分析】因為是兩個人一起走，我們可以發現不能一個一個做網絡流，而是應該一起做。設超級源點0和超級匯點N，如果最大流量是，就表示正確的。----->>>>>但是這樣會有問題：比如從a1萬一到不了a2,然而最終流到了b2，這樣顯然是不可行的。那麼我們可以把b1和b2反一下再做一遍，如果還是滿流就可以了。

【代碼】

 

#include
#include
#include
using namespace std;
const int N=101;
const int INF=2100000000;
int q[N],f[N],map[N][N],temp[N][N];
int n,s1,e1,s2,e2,q1,q2,i,j,flow,tt;
char c,enter;
bool flag;
bool bfs()
{
  memset(q,0,sizeof(q));
  memset(f,-1,sizeof(f));
  int h=0,t=1;f[0]=1;
  while (h