这是一道最大流的题目
首先要引起注意的是,这类多个起点多个终点的问题一定要同时跑,不能分开来跑
由于是无向图,也就相当于从起点跑2*n次
好,不难想到s向两个起点连边,两终点想t连边,流量为2*an或2*bn
然后对于每条危桥,正向反向连边,流量都为2,然后做最大流判断是否满流
但是这样会出现两个问题,第一个如下的情况
6 0 1 1 3 2 1
XXXXOX
XXXXXO
XXXXOX
XXXXXO
OXOXXO
XOXOOX
不难发现中间有条边正向反向都被经过两次,而实际上是不允许的
第二种情况时会出现a1只能b2,b1只能流向a2,这样做应该是不可行的,但实际会产生可行解
解决的办法很简单,我们只要把b1,b2位置换一下,重新构图,再做一次最大流即可
首先对于情况一,如果b1到b2必须多次经过某条边若干次,并且与a1到a2经过这条边反向
那我们把b1b2调换后,就变成了经过双方都是同向经过,这样就只受到了一个流量限制
而对于情况二,正确性是显然的
于是我们就解决了这个问题
const inf=;
type node=record
point,next,flow:longint;
end; var edge:array[..] of node;
a:array[..,..] of longint;
pre,p,numh,cur,h,d:array[..] of longint;
i,j,t,a1,a2,an,b1,b2,bn,n,len:longint;
ch:char; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var neck,u,i,j,tmp,q:longint;
begin
fillchar(h,sizeof(h),);
fillchar(numh,sizeof(numh),);
numh[]:=t+;
for i:= to t do
cur[i]:=p[i];
u:=;
sap:=;
neck:=inf;
while h[]<t+ do
begin
{ writeln(u);
readln; }
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
pre[j]:=u;
cur[u]:=i;
u:=j;
neck:=min(edge[i].flow,neck);
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then
if h[j]<tmp then
begin
tmp:=h[j];
q:=i;
end;
i:=edge[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; procedure work(x,y,f:longint);
begin
add(x,y,f);
add(y,x,);
end; procedure build;
var i,j:longint;
begin
fillchar(p,sizeof(p),);
len:=-;
for i:= to n do
for j:= to n do
if a[i,j]<> then work(i,j,a[i,j]);
end; begin
while not eof do
begin
readln(n,a1,a2,an,b1,b2,bn);
inc(a1);
inc(a2);
inc(b1);
inc(b2);
fillchar(a,sizeof(a),);
t:=n+;
for i:= to n do
begin
for j:= to n do
begin
read(ch);
if ch='O' then a[i,j]:=
else if ch='N' then a[i,j]:=inf;
end;
readln;
end;
build;
work(,a1,*an);
work(a2,t,*an);
work(,b2,*bn);
work(b1,t,*bn);
if sap=*(an+bn) then
begin
build;
work(,a1,*an);
work(a2,t,*an);
work(,b1,*bn);
work(b2,t,*bn);
if sap=*(an+bn) then writeln('Yes')
else writeln('No');
end
else writeln('No');
end;
end.