您當前位置：首頁 > php開源 > php教程 > 【BZOJ 3504】 [Cqoi2014]危橋

【BZOJ 3504】 [Cqoi2014]危橋

來源：程序員人生發布時間：2015-04-21 08:25:07 閱讀次數：3944次

3504: [Cqoi2014]危橋

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 583 Solved: 309
[Submit][Status][Discuss]
Description

Alice和Bob居住在1個由N座島嶼組成的國家，島嶼被編號為0到N⑴。某些島嶼之間有橋相連，橋上的道路是雙
向的，但1次只能供1人通行。其中1些橋由于年久失修成為危橋，最多只能通行兩次。Alice希望在島嶼al和a2之間來回an次（從al到a2再從a2到al算1次來回）。同時，Bob希望在島嶼bl和b2之間來回bn次。這個進程中，所有危橋最多通行兩次，其余的橋可以無窮次通行。請問Alice和Bob能完成他們的欲望嗎？

Input

本題有多組測試數據。
每組數據第1行包括7個空格隔開的整數，分別為N、al、a2、an、bl、b2、bn。
接下來是1個N行N列的對稱矩陣，由大寫字母組成。矩陣的i行j列描寫編號i11和j-l的島嶼間的連接情況，若為“O”則表示有危橋相連：為“N”表示有普通的橋相連：為“X”表示沒有橋相連。
|

Output

對每組測試數據輸出1行，如果他們都能完成欲望輸出“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

數據范圍

4<=N<50

O<=a1, a2, b1, b2<=N⑴

1 <=an. b<=50

網絡流。

如果我們直接網絡流建圖，從 $s$ 到兩個出發點各流 $2*an,2*bn$ 的流量，終點到 $s$ 各流 $2*an,2*bn$ 的流量，點與點之間依照讀入來流，就會出現從 $a1$ 流到 $b2$ ， $b1$ 流到 $a2$ 而致使滿流的情況。

怎樣解決呢？

把 $b1,b2$ 交換1下看是不是仍然滿流。

下面說1下官方題解的證明（我還不能完全理解= =）：
假定第1次跑網絡流a1到a2流 $an-x$ ，a1到b2流 $x$ ，b1到b2流 $bn-x$ ，b1到a2流 $x$
在交換以后，由因而無向圖，a1到a2仍然能流 $an-x$ ，b2到b1也仍然能流 $bn-x$ 。

此時由于還是滿流的，那末a1到b1流 $x$ ，b2到a2流 $x$ 。

把兩次綜合起來看，第1次a1到b2流 $x$ ，第2次a1到b1流 $x$ ；
由因而無向圖，我們把邊反向1下b1到a1流 $x$ ，a1到b2流 $x$ ，這就相當于b1到b2流了 $x$ ，加上第1次b1到b2的 $bn-x$ ，b1到b2確切流了bn(a的同理)

我不理解的地方是第2次滿流a1到a2雖然能流 $an-x$ ，但他不1定還是流 $an-x$ 吧，為了滿流他可能流的少1些，也可能多1些啊

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
char S[55][55];
int d[55],v[55],cur[55],tot,s,t,h[55],n,a1,a2,an,b1,b2,bn;
struct edge
{
    int from,to,cap,flow,ne;
}E[100005];
void Addedge(int from,int to,int cap)
{
    E[++tot]=(edge){from,to,cap,0,h[from]};
    h[from]=tot;
    E[++tot]=(edge){to,from,0,0,h[to]};
    h[to]=tot;
}
void Build()
{
    tot=1;
    for (int i=s;i<=t;i++)
        h[i]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<n;j++)
        {
            if (S[i][j]=='O') Addedge(i,j+1,2);
            if (S[i][j]=='N') Addedge(i,j+1,inf);
        }
}
bool bfs()
{
    for (int i=s;i<=t;i++)
        v[i]=0;
    queue<int> q;
    q.push(s);
    v[s]=1;
    d[s]=0;
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        for (int i=h[x];i;i=E[i].ne)
        {
            edge e=E[i];
            if (!v[e.to]&&e.cap>e.flow)
            {
                v[e.to]=1;
                d[e.to]=d[x]+1;
                q.push(e.to);
            }
        }
    }
    return v[t];
}
int dfs(int x,int a)
{
    if (x==t||!a) return a;
    int flow=0;
    for (int &i=cur[x];i;i=E[i].ne)
    {
        edge &e=E[i];
        if (d[e.to]!=d[x]+1) continue;
        int f=dfs(e.to,min(a,e.cap-e.flow));
        if (f>0)
        {
            e.flow+=f;
            E[i^1].flow-=f;
            flow+=f;
            a-=f;
            if (!a) break;
        }
    }
    return flow;
}
int dinic()
{
    int flow=0;
    while (bfs())
    {
        for (int i=s;i<=t;i++)
            cur[i]=h[i];
        flow+=dfs(s,inf);
    }
    return flow;
}
int main()
{
    while (scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF)
    {
        s=0,t=n+1;
        for (int i=1;i<=n;i++)
            scanf("%s",S[i]);
        an*=2,bn*=2;
        a1++,a2++,b1++,b2++;
        Build();
        Addedge(s,a1,an),Addedge(a2,t,an);
        Addedge(s,b1,bn),Addedge(b2,t,bn);
        if (dinic()==an+bn)
        {
            Build();
            Addedge(s,a1,an),Addedge(a2,t,an);
            Addedge(s,b2,bn),Addedge(b1,t,bn);
            if (dinic()==an+bn) puts("Yes");
            else puts("No");
        }
        else puts("No");
    }
    return 0;
}