CQOI2014危桥

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

题意:

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

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

分析：

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

往返次相当于从~走次，同理。

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

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

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

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

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

于是我们可以交换，（,也可以）再跑一次最大流，如果最大流也不小于,即可行。

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

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

注意：

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

#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;
}