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
No
数据范围
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;
}
感悟：
1.TLE是在bfs中没有写v[s]=1
2.CQOI2014题解
波比源码 » 【BZOJ 3504】 [Cqoi2014]危桥
