CQOI2014危桥_牛客博客

~~调了半天TLE，发现初始化的位置有问题。（自闭）~~

题意:

给你一个无向图，其中有一些岛屿间有桥，有一些没有，然后桥又有一些是危桥，只能走两次。 ~~（危桥难道不应该只能走一次吗）~~

然后 $Alice$ 和 $Bob$ ~~两个拆桥大队队员来了~~ ， $Alice$ 希望在 $a_1$ 和 $a_2$ 两个岛屿之间往返 $a_n$ 次， $Bob$ 希望在 $b_1$ 和 $b_2$ 两个岛屿之间往返 $b_n$ 次，问两个人的希望能不能成功。 ~~（可是希望多半要落空,Alice 和 Bob的也不例外...）~~

分析：

题目让我们判断是否这个图能完成 $Alice$ 和 $Bob$ 的愿望是否能成功。

往返 $a_n$ 次相当于从 $a_1$ ~ $a_2$ 走 $2 \times a_n$ 次， $b_n$ 同理。

然后我们就可以明了，为什么会有危桥允许走两次~~的奇葩设定~~了。

于是我们就可以看成从 $a_1$ ~ $a_2$ 走 $a_n$ 次， $b_n$ 同理，且危桥只能走一次。

然后我们就可以建出一个图，发现从 $a_1$ ~ $a_2$ 走 $a_n$ 次相当于从 $a_1$ ~ $a_2$ 的最大流，且流量不能小于 $a_n$ ， $b_n$ 依然同理。

到这里难道这道题就 $A$ 了吗？？？

有可能会出现一些流量在 $a_1$ ， $b_2$ 间往返，一些在 $b_1$ , $a_2$ 中往返，总之瞎流。

于是我们可以交换 $b_1$ ， $b_2$ （ $a_1$ , $a_2$ 也可以）再跑一次最大流，如果最大流也不小于 $a_n$ , $b_n$ 即可行。

那么会不会出现两次都在瞎流呢？？？

拿 $nodgd$ 的话来讲：如果两次都在瞎流，那么一定能在图中找到一个不在瞎流且合法的流。

注意：

这道题是从 $0$ ~ $n-1$ 编号，所以需要 $a_1,a_2,b_1,b_2+1$
有多组数据，不要忘了初始化
注意输出是"Yes"而不是"YES" ~~(可能只有我一个人犯了这样的错）~~
为了方便，我们可以将源点到 $a_1,b_1$ 汇点到 $a_2$ , $b_2$ 的边权设为 $a_n$ , $b_n$ 这样保证最大流不会超过 $a_n,b_n$ 最后只需要判断是否 $flow$ 是否等于 $a_n+b_n$
此图是无向图

$code(isap):$

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int N=20005;
const int M=100005;
char ma[105][105];
int n,a1,a2,an,b1,b2,bn,S,T;
int Next[M],End[M],len[M],tot;
int Last[N],_last[N],gap[N],dis[N];
inline void cb(int x,int y,int z){
    End[tot]=y,Next[tot]=Last[x],len[tot]=z,Last[x]=tot++;
    End[tot]=x,Next[tot]=Last[y],len[tot]=z,Last[y]=tot++;
}
void bfs(){
    for(int i=1;i<=T;i++) dis[i]=T,gap[i]=0,_last[i]=Last[i];
    gap[0]=dis[T]=0;
    queue<int> q;
    q.push(T);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=Last[x];i;i=Next[i]){
            int y=End[i];
            if(dis[y]>dis[x]+1){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    for(int i=1;i<=T;i++) gap[dis[i]]++;
    return;
}
int isap(int x,int flow){
    if(x==T) return flow;
    int flow_now=0;
    for(int &i=_last[x];i;i=Next[i]){
        int y=End[i];
        if(len[i] && dis[x]==dis[y]+1){
            int f=isap(y,min(len[i],flow-flow_now));
            flow_now+=f;
            len[i]-=f;
            len[i^1]+=f;
            if(flow==flow_now || dis[S]==T) return flow_now;
        }
    }
    gap[dis[x]]--;
    if(!gap[dis[x]]) dis[S]=T;
    dis[x]++;
    gap[dis[x]]++;
    _last[x]=Last[x];
    return flow_now;
}
void _main(){
    a1++,a2++,b1++,b2++;
    S=n*n+1,T=S+1,tot=2;
    for(int i=1;i<=n;i++)
        scanf("%s",ma[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(ma[i][j]=='O') cb(i,j,1);
            else if(ma[i][j]=='N') cb(i,j,inf);
        }
    }
    //建立源点，汇点的限制流量(边权)
    cb(S,a1,an),cb(a2,T,an);
    cb(S,b1,bn),cb(b2,T,bn);
    int flow=0;
    bfs();
    while(dis[S]<T) flow+=isap(S,inf);
    memset(Last,0,sizeof(Last));
    if(flow!=an+bn){
        puts("No");
        return;
    }
    tot=2;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(ma[i][j]=='O') cb(i,j,1);
            else if(ma[i][j]=='N') cb(i,j,inf);
        }
    }
    cb(S,a1,an),cb(a2,T,an);
    cb(S,b2,bn),cb(b1,T,bn);
    bfs();
    while(dis[S]<T) flow-=isap(S,inf);
    if(flow!=0) puts("No");
    else puts("Yes");
    memset(Last,0,sizeof(Last));
    return;
}
int main(){
    while(scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF) _main();
    return 0;
}