Home > Old Blog Posts > USACO 5.4.5 Telecowmunication

USACO 5.4.5 Telecowmunication


描述

农夫约翰的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由c台电脑组成的序列a1,a2,…,a(c),且a1与a2相连,a2与a3相连,等等,那么电脑a1和a(c)就可以互发电邮。

很不幸,有时候奶牛会不小心踩到电脑上,农夫约翰的车也可能碾过电脑,这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了,于是与这台电脑相关的连接也就不可用了。

有两头奶牛就想:如果我们两个不能互发电邮,至少需要坏掉多少台电脑呢?请编写一个程序为她们计算这个最小值和与之对应的坏掉的电脑集合。

以如下网络为例:

              1*
             /
            3 - 2*

这张图画的是有2条连接的3台电脑。我们想要在电脑1和2之间传送信息。电脑1与3、2与3直接连通。如果电脑3坏了,电脑1与2便不能互发信息了。

描述

程序名: telecow

输入格式 第一行四个由空格分隔的整数:N,M,c1,c2.N是电脑总数(1<=N<=100),电脑由1到N编号。M是电脑之间连接的总数(1& lt;= M<=600)。最后的两个整数c1和c2是上述两头奶牛使用的电脑编号。连接没有重复且均为双向的(即如果c1与c2相连,那么c2与c1也相 连)。两台电脑之间至多有一条连接。电脑c1和c2不会直接相连。 第2到M+1行 接下来的M行中,每行包含两台直接相连的电脑的编号。

输出格式

输出共有两行。第一行是使电脑c1和c2不能互相通信需要坏掉的电脑数目的最小值。第二行是排好序的坏掉的电脑的编号列表。注意c1和c2都不能坏掉。如果有多种可能情况,输出第一个数最小的一种,如果第一个数相同,则输出第二个数最小的一种,依此类推。

样例输入(文件telecow.in)

3 2 1 2
1 3
2 3

样例输出(文件telecow.out)

1
3

仍旧是一道求最小割的题目,只不过这道题是求最小点割集,为此,我们需要把点转化为边,将每个点i拆为i1,i2,连一条有向边(i1,i2),权值为1,对于每一条边(i, j),转换为两条有向边(i2, j1)和(j2, i1),源点为1-1,汇点为N-2,对新图求最大流,流的容量即为最小割的容量。再用一次flood求出最小边割集,最后将边还原为点。

因为要求字典序最小,有向边(i1,i2)的权值可修改为6000+i (想一想为什么,参照USACO 4.4.2的题解),最后maxflow的值再除以6000即可。

/*
ID: dementr1
PROG: telecow
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“telecow.in”);
ofstream fout(“telecow.out”);
int v[300][300],f[300][300],leave[300][300],level[300],N,M,c1,c2;
bool vis[300]={false};
int inf=2000000000;
void init()
{
int from,to,i;
fin>>N>>M>>c1>>c2;
for(i=0;i<M;i++)
{
fin>>from>>to;
v[from*2][to*2-1]=inf;
v[to*2][from*2-1]=inf;
}
fin.close();
for(i=1;i<=N;i++)
{
if(i==c1||i==c2) v[i*2-1][i*2]=inf;
else
v[i*2-1][i*2]=i+6000;
}
}
void createlevel()
{
int save[300]={},closed=-1,open=0,now,i,j;
memset(level,0,sizeof(level));
memset(leave,0,sizeof(leave));
level[c1*2-1]=0;
save[0]=c1*2-1;
for(i=1;i<=N*2;i++)
for(j=1;j<=N*2;j++)
leave[i][j]=v[i][j]-f[i][j];
for(i=1;i<=N*2;i++)
for(j=1;j<=N*2;j++)
if(f[i][j]>0) leave[j][i]=f[i][j];
while(closed<open)
{
closed++;
now=save[closed];
for(i=1;i<=N*2;i++)
{
if(i==c1*2-1) continue;
if(leave[now][i]>0)
if(level[i]==0)
{
open++;
save[open]=i;
level[i]=level[now]+1;
}
}
}
}
int dinic()
{
int p[300]={},u,i,min,ans=0;
p[0]=1;
p[1]=c1*2-1;
while(1)
{
createlevel();
if(level[c2*2]==0) break;
while(1)
{
u=p[p[0]];
if(u!=c2*2)
{
bool flag=false;
for(i=1;i<=N*2;i++)
if(level[i]==level[u]+1&&leave[u][i]>0)
{
p[0]++;
p[p[0]]=i;
flag=true;
break;
}
if(!flag)
{
p[0]–;
for(i=1;i<=N*2;i++)
if(level[i]==level[u]+1&&leave[u][i]>0)
level[i]=0;
level[u]=0;
}
}
if(u!=c2*2&&p[0]<=0) break;
if(u==c2*2)
{
min=leave[p[1]][p[2]];
for(i=2;i<p[0];i++)
if(leave[p[i]][p[i+1]]<min) min=leave[p[i]][p[i+1]];
for(i=1;i<p[0];i++)
f[p[i]][p[i+1]]+=min;
for(i=1;i<p[0];i++)
if(leave[p[i]][p[i+1]]-min==0)
{
p[0]=i;
break;
}
ans+=min;
break;
}
}
}
return ans;
}
void floodfill(int k)
{
int i;
vis[k]=true;
for(i=1;i<=N*2;i++)
if(!vis[i]&&((leave[k][i]>0)||f[i][k]>0))
floodfill(i);

}
int main()
{
int i,ansi[300]={};
init();
int ans=dinic();
floodfill(c1*2-1);
fout<<ans/6000<<endl;
for(i=1;i<=N;i++)
if(vis[i*2-1]&&!vis[i*2])
ansi[++ansi[0]]=i;
for(i=1;i<ansi[0];i++) fout<<ansi[i]<<” “;
fout<<ansi[ansi[0]]<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: