@bzoj
@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
@solution@
【bzoj 的题面。。。我也不好吐槽什么。。。】
本题其实就是一个多源多汇且源汇之间的匹配固定的最大流。
可以比较容易地想到这样一个思路：建超级源点连 a1, b1，将 a2, b2 连向超级汇点，容量分别设为 2an 与 2bn；将危桥的容量设为 2、正常的桥容量设为 inf，连成双向边。
这样建图后跑最大流，如果最大流 = 2*(an + bn) 则有解。
因为所有边的容量都为偶数（可以把 inf 当作偶数），所以可以把容量全部除以 2，判断最大流是否等于 an + bn（即网上所说只需要把往返看作单次）。
但是可以发现如果 a1 -> b2 且 b1 -> a2，则最大流跑出来的 “有解” 不一定真的有解。
还有一点，危桥是限制往返的次数加起来 <= 1，但我们建出来的图相当于正方向与反方向分别 <= 1。
我们只需要将源点 s 连 a1, b2，将 a2, b1 连汇点 t，再跑一次最大流，判定是否合法即可。
至于证明。。。上面说的那篇博客讲得非常好所以我就直接粘过来了。
如果满流且仍然存在问题一那种情况呢？画个图。
假设第一次跑最大流， a1→b2 的流量为 x ，那么 b1→b2 的流量为 bn−x， b1→a2 的流量也是 x ， a1→a2 的流量是 an−x。
而第二次跑最大流，因为是无向图， a1→a2 和 b2→b1 的流量可以不变，还是 an−x,bn−x。那么 a1→b1 和 b2→a2 的流量（注：原博主这个地方是写错了，下面的评论区中有提到）也都还是 x 。
而这两次说明了什么呢， a1 可以流到 b1 x 流量，还可以流到 b2 x 流量，同时不影响 a1 与 a2， b1 与 b2 之间的流量。
因为是无向图，将 a1→b1 的流量反向，就可以得到 b1→b2 x 的流量。 b1,b2 之间的流就合法了。同理 a1,a2 之间的流也合法。
所以如果交换 b1, b2 后仍满流，一定不存在问题一那种情况。
对于问题二，假如 a1→a2 正向经过了一座危桥，而 b1→b2 反向经过了这座桥，那么交换 b1,b2，以 b2 为起点后， a1→a2,b2→b1 两条路径都是正向通过了这条边，就受到了流量的限制。
所以如果仍满流，不存在问题二。
@accepted code@
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 50;
const int MAXV = MAXN;
const int MAXE = 2*MAXV*MAXV;
const int INF = int(1E6);
struct FlowGraph{
struct edge{
int to, cap, flow;
edge *nxt, *rev;
}edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt;
int s, t, n;
void clear(int _n) {
n = _n; ecnt = &edges[0];
for(int i=0;i<=n;i++)
adj[i] = NULL;
}
void addedge(int u, int v, int c) {
edge *p = (++ecnt), *q = (++ecnt);
p->to = v, p->cap = c, p->flow = 0;
p->nxt = adj[u], adj[u] = p;
q->to = u, q->cap = 0, q->flow = 0;
q->nxt = adj[v], adj[v] = q;
p->rev = q, q->rev = p;
// printf("%d %d %lld
", u, v, c);
}
queue<int>que; int d[MAXV + 5];
bool relabel() {
for(int i=0;i<=n;i++)
cur[i] = adj[i], d[i] = n + 5;
while( !que.empty() ) que.pop();
d[t] = 0, que.push(t);
while( !que.empty() ) {
int f = que.front(); que.pop();
for(edge *p=adj[f];p;p=p->nxt)
if( d[f] + 1 < d[p->to] && p->rev->cap > p->rev->flow ) {
d[p->to] = d[f] + 1;
que.push(p->to);
if( p->to == s ) return true;
}
}
return !(d[s] == n + 5);
}
int aug(int x, int tot) {
if( x == t ) return tot;
int sum = 0;
for(edge *&p=cur[x];p;p=p->nxt) {
if( p->cap > p->flow && d[p->to] + 1 == d[x] ) {
int del = aug(p->to, min(p->cap - p->flow, tot - sum));
p->flow += del, p->rev->flow -= del, sum += del;
if( sum == tot ) break;
}
}
return sum;
}
int max_flow(int _s, int _t) {
s = _s, t = _t; int flow = 0;
while( relabel() )
flow += aug(s, INF);
return flow;
}
}G;
int N, a1, a2, an, b1, b2, bn;
char str[MAXN + 5][MAXN + 5];
int main() {
while( scanf("%d%d%d%d%d%d%d", &N, &a1, &a2, &an, &b1, &b2, &bn) == 7 ) {
bool flag = true;
for(int i=0;i<N;i++)
scanf("%s", str[i]);
G.s = N, G.t = N + 1;
G.clear(N + 2);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if( str[i][j] == 'O' ) G.addedge(i, j, 1);
else if( str[i][j] == 'N' ) G.addedge(i, j, INF);
G.addedge(G.s, a1, an), G.addedge(G.s, b1, bn);
G.addedge(a2, G.t, an), G.addedge(b2, G.t, bn);
flag &= (G.max_flow(G.s, G.t) == an + bn);
G.s = N, G.t = N + 1;
G.clear(N + 2);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if( str[i][j] == 'O' ) G.addedge(i, j, 1);
else if( str[i][j] == 'N' ) G.addedge(i, j, INF);
G.addedge(G.s, a1, an), G.addedge(G.s, b2, bn);
G.addedge(a2, G.t, an), G.addedge(b1, G.t, bn);
flag &= (G.max_flow(G.s, G.t) == an + bn);
if( flag ) puts("Yes");
else puts("No");
}
}
@details@
听说多源多汇且固定源汇的问题只能用线性规划解。大概是因为这道题非常特殊吧（2 源 2 汇）。
总感觉这个题的结论非常神仙，不是我们凡人可以接触的领域。听说是从topcoder上搬来的题。