5.4.5 Telecowmunication 奶牛的电信
时间： 1ms 内存：64M
描述：
农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由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便不能互发信息了。
输入：
第一行 四个由空格分隔的整数：N,M,c1,c2.N是电脑总数(1<=N<=100)，电脑由1到N编号。M是电脑之间连接的总数(1<=M<=600)。最后的两个整数c1和c2是上述两头奶牛使用的电脑编号。连接没有重复且均为双向的(即如果c1与c2相连，那么c2与c1也相连)。两台电脑之间至多有一条连接。电脑c1和c2不会直接相连。 第2到M+1行 接下来的M行中，每行包含两台直接相连的电脑的编号。
输出：
输出共有两行。第一行是使电脑c1和c2不能互相通信需要坏掉的电脑数目的最小值。第二行是排好序的坏掉的电脑的编号列表。注意c1和c2都不能坏掉。如果有多种可能情况，输出第一个数最小的一种，如果第一个数相同，则输出第二个数最小的一种，依此类推。
示例输入：
3 2 1 2
1 3
2 3
示例输出：
1
3
提示：
参考答案（内存最优[1672]）：
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=201;
#define inf 1000000000
int max_flow(int n,int mat[][maxn],int source,int sink){
int v[maxn],c[maxn],p[maxn],ret=0,i,j;
for (;;){
for (i=0;i<n;i++)
v[i]=c[i]=0;
for (c[source]=inf;;){
for (j=-1,i=0;i<n;i++)
if (!v[i]&&c[i]&&(j==-1||c[i]>c[j]))
j=i;
if (j<0) return ret;
if (j==sink) break;
for (v[j]=1,i=0;i<n;i++)
if (mat[j][i]>c[i]&&c[j]>c[i])
c[i]=mat[j][i]<c[j]?mat[j][i]:c[j],p[i]=j;
}
for (ret+=j=c[i=sink];i!=source;i=p[i])
mat[p[i]][i]-=j,mat[i][p[i]]+=j;
}
}
int min_ver(int n,int mat[][maxn],int source,int
sink, int* set){
int m0[maxn][maxn],m[maxn][maxn],i,j,k,ret=0,last;
if (source==sink||mat[source][sink])
return -1;
for (i=0;i<n+n;i++)
for (j=0;j<n+n;j++)
m0[i][j]=0;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (mat[i][j])
m0[i][n+j]=inf;
for (i=0;i<n;i++)
m0[n+i][i]=1;
for (i=0;i<n+n;i++)
for (j=0;j<n+n;j++)
m[i][j]=m0[i][j];
last=max_flow(n+n,m,source,n+sink);
for (k=0;k<n&&last;k++)
if (k!=source&&k!=sink){
for (i=0;i<n+n;i++)
for (j=0;j<n+n;j++)
m[i][j]=m0[i][j];
m[n+k][k]=0;
if (max_flow(n+n,m,source,n+sink)<last){
set[ret++]=k;
m0[n+k][k]=0;
last--;
}
}
return ret;
}
int main()
{
int n,m,Start,End,i;
int map[maxn][maxn],s[maxn];
while(cin>>n>>m>>Start>>End){
memset(map,0,sizeof(map));
memset(s,0,sizeof(s));
for(i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
map[a][b]=map[b][a]=1;
}
Start--;End--;
int k=min_ver(n,map,Start,End,s);
cout<<k<<endl;
sort(s,s+k);
for(i=0;i<k;i++){
cout<<s[i]+1;
if(i!=k-1)
cout<<" ";
}
cout<<endl;
}
return 0;
}
参考答案（时间最优[300]）：
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=201;
#define inf 1000000000
int max_flow(int n,int mat[][maxn],int source,int sink){
int v[maxn],c[maxn],p[maxn],ret=0,i,j;
for (;;){
for (i=0;i<n;i++)
v[i]=c[i]=0;
for (c[source]=inf;;){
for (j=-1,i=0;i<n;i++)
if (!v[i]&&c[i]&&(j==-1||c[i]>c[j]))
j=i;
if (j<0) return ret;
if (j==sink) break;
for (v[j]=1,i=0;i<n;i++)
if (mat[j][i]>c[i]&&c[j]>c[i])
c[i]=mat[j][i]<c[j]?mat[j][i]:c[j],p[i]=j;
}
for (ret+=j=c[i=sink];i!=source;i=p[i])
mat[p[i]][i]-=j,mat[i][p[i]]+=j;
}
}
int min_ver(int n,int mat[][maxn],int source,int
sink, int* set){
int m0[maxn][maxn],m[maxn][maxn],i,j,k,ret=0,last;
if (source==sink||mat[source][sink])
return -1;
for (i=0;i<n+n;i++)
for (j=0;j<n+n;j++)
m0[i][j]=0;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (mat[i][j])
m0[i][n+j]=inf;
for (i=0;i<n;i++)
m0[n+i][i]=1;
for (i=0;i<n+n;i++)
for (j=0;j<n+n;j++)
m[i][j]=m0[i][j];
last=max_flow(n+n,m,source,n+sink);
for (k=0;k<n&&last;k++)
if (k!=source&&k!=sink){
for (i=0;i<n+n;i++)
for (j=0;j<n+n;j++)
m[i][j]=m0[i][j];
m[n+k][k]=0;
if (max_flow(n+n,m,source,n+sink)<last){
set[ret++]=k;
m0[n+k][k]=0;
last--;
}
}
return ret;
}
int main()
{
int n,m,Start,End,i;
int map[maxn][maxn],s[maxn];
while(cin>>n>>m>>Start>>End){
memset(map,0,sizeof(map));
memset(s,0,sizeof(s));
for(i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
map[a][b]=map[b][a]=1;
}
Start--;End--;
int k=min_ver(n,map,Start,End,s);
cout<<k<<endl;
sort(s,s+k);
for(i=0;i<k;i++){
cout<<s[i]+1;
if(i!=k-1)
cout<<" ";
}
cout<<endl;
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。