BZOJ 3504: [Cqoi2014]危桥 [最大流]

时间：2023-03-08 19:07:08

3504: [Cqoi2014]危桥

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1407  Solved: 703
[Submit][Status][Discuss]

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
双向图，往返=走好几次--流量
危桥c=2，普通c=INF
s--an-->a1   a2--an-->t
  --bn-->b1  b2--bn-->t
看是否满流即可
但是有个问题，a1的流量可能流到b2，同时b1的到a2
于是，交换b1和b2的位置，再做一遍最大流看是否满流，满流则可行
为什么呢？
linkct讲课说，两个流f1和f2可行，|f1+f2|/2也可行(平均都小于每一个)
证明具体忘了，自己又想了一下，不一定对
考虑前后两次流，
第一次：f1
a1-->a2  an-x
b1-->b2  an-x
a1-->b2 x
a2-->b1 x
第二次：f2
a1-->a2  an-x
b2-->b1  an-x
a1-->b1  x
b2-->a2  x
相加|f1+f2|/2:  f(a1,a2)=an-x  f(b1,b2)=0  f(a1,a2)=x  所以f(a1,a2)=an
实现上的问题：
1.老老实实的重构图
2.老老实实的保存边容量 g[i][j]=0!!!
3.双向图反向边c=c就行了
4.+1 *2
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,a1,a2,an,b1,b2,bn,s,t;

int g[N][N];

int tot;

char ss[N];

struct edge{

    int v,ne,c,f;

}e[N*N<<];

int cnt,h[N];

inline void ins(int u,int v,int c){

    cnt++;

    e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[v];h[v]=cnt;

}

int q[N],head,tail,vis[N],d[N];

bool bfs(){

    memset(vis,,sizeof(vis));

    memset(d,,sizeof(d));

    head=tail=;

    q[tail++]=s;d[s]=;vis[s]=;

    while(head!=tail){

        int u=q[head++];

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v;

            if(!vis[v]&&e[i].c>e[i].f){

                vis[v]=;

                d[v]=d[u]+;

                if(v==t) return true;

                q[tail++]=v;

            }

        }

    }

    return false;

}

int cur[N];

int dfs(int u,int a){

    if(u==t||a==) return a;

    int flow=,f;

    for(int &i=cur[u];i;i=e[i].ne){

        int v=e[i].v;

        if(d[v]==d[u]+&&(f=dfs(v,min(a,e[i].c-e[i].f)))>){

            flow+=f;

            e[i].f+=f;

            e[((i-)^)+].f-=f;

            a-=f;

            if(a==) break;

        }

    }

    return flow;

}

int dinic(){

    int flow=;

    while(bfs()){

        for(int i=s;i<=t;i++) cur[i]=h[i];

        flow+=dfs(s,INF);

    }

    return flow;

}

int th[N],tc;

bool solve(){

    s=;t=n+;

    ins(s,a1,an);ins(s,b1,bn);

    ins(a2,t,an);ins(b2,t,bn);

    int ans=dinic();//printf("ans1 %d\n",ans);

    if(ans!=an+bn) return false;

    cnt=;memset(h,,sizeof(h));

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++) if(g[i][j]) ins(i,j,g[i][j]);

    ins(s,a1,an);ins(s,b2,bn);

    ins(a2,t,an);ins(b1,t,bn);

    ans=dinic();//printf("ans2 %d\n",ans);

    if(ans!=an+bn) return false;

    return true;

}

int main(){

    //freopen("in.txt","r",stdin);

    while(scanf("%d",&n)!=EOF){

        a1=read()+;a2=read()+;an=read()*;

        b1=read()+;b2=read()+;bn=read()*;

        cnt=;memset(h,,sizeof(h));

        for(int i=;i<=n;i++){

            scanf("%s",ss+);

            for(int j=i+;j<=n;j++){

                if(ss[j]=='O') ins(i,j,),g[i][j]=;

                else if(ss[j]=='N') ins(i,j,INF),g[i][j]=INF;

                else g[i][j]=;

            }

        }

        if(solve()) puts("Yes");

        else puts("No");

    }

}

相关文章