论网络流 的反向流的合法性。。。（这道题 我想了一段时间 但是由于对网络流的反向流真正理解程度 不高 还是不能解出危桥这道题。。
这道题 两个人 来回通过一个 地方 显然的转换是 把来回当做两次直接跑。
先讨论一个人的情况 建图时有点迷 好像没说是单向边还是双向边 如果我直接建单向的话显然的是不行的，建双向边 ！ 那么我如何保证危桥被使用的次数呢 考虑一下这个问题一座桥的反向边在我们这个地方是不必要的，因为我们按照一个方向来跑也就是说另一个方向没有什么大用，反向流呢？我们正向流转换成反向流都够用了吧，，，这一点正确性还是比较显然的。
两个人呢？直接 放源汇点然后直接跑么？这也是我的疑问所在显然的是 如果这两条路是不同向的可能对于一个危桥正着第一次我跑了2条流 然后另一条流再跑 跑刚刚这条路的反向边 跑了4流。现在询问还是合法的么？这里就是反向流的含义了！。。
对于两相反流相撞的情况 经过更深层次的思考 其实这是另一条流流到了人家的出流点罢了。。如何保证不流到对方的位置呢？貌似好像很难。。
在说出解决方案之前我们要明确两条路的相对位置 显然 同向或者在局部范围内是反向的 。
有一种情况是局部反向 然后 再局部同向么？注意这里讨论的只是道路重合的部分对不不重合的部分没有上述的反流异常出现。
当然 这种情况是不可能的 因为 一个流不可能突然回头。。所以 我们只需 把他们变成同向流即可。但是我们并不知道到底哪种情况是同向的哪种情况的反向的，固定住第一个人 改变第二个人的源汇点 这样一定有一种情况是两条道路同时同向。
同向时的满流 意味着不可能有上述怪异的反流出现。合法 ，那么如何判断这两种情况呢 我们思考一下 如果相反道路 那么一些危桥的流量可以当做无限使用更容易满流。
综上 当 同向道路满流时 反向道路一定满流所以的出命题两种情况都满流时 为Yes。。
//#include<bits/stdc++.h> #include<iomanip> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<deque> #include<cmath> #include<ctime> #include<cstdlib> #include<stack> #include<algorithm> #include<vector> #include<cctype> #include<utility> #include<set> #include<bitset> #include<map> #define INF 1000000000 #define ll long long #define min(x,y) ((x)>(y)?(y):(x)) #define max(x,y) ((x)>(y)?(x):(y)) #define RI register ll #define db double #define x(i) t[i].x #define y(i) t[i].y #define z(i) t[i].z using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN=60*60; int n,S,T,t,h,maxflow,len; int a1,a2,an,b1,b2,bn; char a[60][60]; int q[MAXN],vis[MAXN]; int lin[MAXN],ver[MAXN*MAXN<<1],nex[MAXN*MAXN<<1],e[MAXN*MAXN<<1]; inline void add(int x,int y,int z) { ver[++len]=y;nex[len]=lin[x];lin[x]=len;e[len]=z; ver[++len]=x;nex[len]=lin[y];lin[y]=len;e[len]=z; } inline int bfs() { t=h=0; memset(vis,0,sizeof(vis)); q[++t]=S;vis[S]=1; while(h++<t) { int x=q[h]; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(!e[i]||vis[tn])continue; q[++t]=tn;vis[tn]=vis[x]+1; if(tn==T)return 1; } } return 0; } inline int dinic(int x,int flow) { if(x==T)return flow; int rest=flow,k; for(int i=lin[x];i&&rest;i=nex[i]) { int tn=ver[i]; if(vis[tn]==vis[x]+1&&e[i]) { k=dinic(tn,min(e[i],rest)); if(!k)vis[tn]=0; e[i]-=k;e[i^1]+=k; rest-=k; } } return flow-rest; } int main() { //freopen("1.in","r",stdin); while(scanf("%d",&n)==1) { len=1;memset(lin,0,sizeof(lin)); S=n+1;T=S+1; a1=read()+1;a2=read()+1;an=read()<<1; b1=read()+1;b2=read()+1;bn=read()<<1; for(int i=1;i<=n;++i)scanf("%s",a[i]+1); add(S,a1,an);add(a2,T,an); add(S,b1,bn);add(b2,T,bn); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) { if(a[i][j]=='X')continue; if(a[i][j]=='O')add(i,j,2); else add(i,j,INF); } int flow=0;maxflow=0; while(bfs())while((flow=dinic(S,INF)))maxflow+=flow; if(maxflow!=an+bn){puts("No");continue;} len=1;memset(lin,0,sizeof(lin)); add(S,a1,an);add(a2,T,an); add(S,b2,bn);add(b1,T,bn); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) { if(a[i][j]=='X')continue; if(a[i][j]=='O')add(i,j,2); else add(i,j,INF); } flow=0;maxflow=0; while(bfs())while((flow=dinic(S,INF)))maxflow+=flow; if(maxflow!=an+bn){puts("No");continue;} puts("Yes"); } }