「CQOI 2014」危桥

题目链接

戳我

\(Solution\)

首先往返\(n\)次等价于走\(2n\)次。

将 \(a_n*2,b_n*2\);

那么我们直接按原图构图，然后：

\((S,a_1,a_n),(S,b_1,b_n),(a_2,T,a_n),(b_2,T,b_n)\)

但直接判断最大流是否等于\(a_n+b_n\)是不对的。因为\(a_2\)可能有来自\(b_1\)的流量，\(b_2\)也有可能有来自\(a_1\)的流量。

所以我们可以将\(b_1\)和\(b_2\)交换再跑一次最大流。如果两次最大流都等于\(a_n+b_n\) 那么有解。

至于证明，将\(a_1->a_2\)的流量设为\(x\)然后在推一下就没了，自己想想吧

\(Code\)

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

const int inf=1e12;

int read(){

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

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

struct node{

    int to,next,v;

}a[200001];

int head[100001],cnt=1,n,m,s,t,x,y,z,dep[100001],a1,a2,an,b1,b2,bn;

void add(int x,int y,int c){

    a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,head[x]=cnt;

    a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,head[y]=cnt;

}

queue<int> q;

int bfs(){

    memset(dep,0,sizeof(dep));

    q.push(s);

    dep[s]=1;

    while(!q.empty()){

        int now=q.front();

        q.pop();

        for(int i=head[now];i;i=a[i].next){

            int v=a[i].to;

            if(!dep[v]&&a[i].v>0)

                dep[v]=dep[now]+1,q.push(v);

        }

    }

    if(dep[t])

        return 1;

    return 0;

}

int dfs(int k,int list){

    if(k==t||!list)

       return list;

    for(int i=head[k];i;i=a[i].next){

        int v=a[i].to;

        if(dep[v]==dep[k]+1&&a[i].v>0){

            int p=dfs(v,min(list,a[i].v));

            if(p){

                a[i].v-=p;

                a[i^1].v+=p;

                return p;

            }

        }

    }

    return dep[k]=0;

}

int Dinic(){

    int ans=0,k;

    while(bfs())

        while((k=dfs(s,inf)))

            ans+=k;

    return ans;

}

char c[101][101];

bool build(){

    s=0,t=n+1;

    memset(head,0,sizeof(head)),cnt=1;

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

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

            if(c[i][j]=='O')

                add(i,j,2);

            if(c[i][j]=='N')

                add(i,j,inf);

        }

    add(s,a1,an),add(a2,t,an);

    add(s,b1,bn),add(b2,t,bn);

    return Dinic()==an+bn;

}

main(){

    while(scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF){

        a1++,a2++,b1++,b2++,an*=2,bn*=2;

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

            scanf("%s",c[i]+1);

        int ans=build();

        swap(b1,b2);

        ans+=build();

        if(ans==2) puts("Yes");

        else puts("No");

    }

}

巴特西

「CQOI 2014」危桥

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章