注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]奶牛的电信  

2015-08-04 17:48:13|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:最大流最小割,拆点。

Link&Limit


        [洛谷1345]  [codevs1563]
        时间限制:1000ms  空间限制:131072kb

Description


        农夫约翰的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由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便不能互发信息了。

Input Format


        第一行 四个由空格分隔的整数: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行中,每行包含两台直接相连的电脑的编号。

Output Format


        一个整数表示使电脑c1和c2不能互相通信需要坏掉的电脑数目的最小值。

Sample Input #1


3 2 1 2
1 3
2 3

Sample Output #1


1

        求最小割的题目。其实我很想吐槽直接把c1或c2踩坏不就可以了么...
        本题是经典的拆点模型:将一个点拆为两个点——入点和出点,从入点向出点连一条容量为1的边,表示每台电脑只能损坏一次。图中已有的边容量就是INF(因为不能切掉图中原有的边)。源点指向c1的出点,c2的入点指向汇点,跑一边最大流(最小割)就好了。

#include <stdio.h>
#define INF 999999
#define S 0
#define T 201
int n,m,sta,fin;
int e[3010][3],p[210],tot = 1;
int dis[210],from[210],cur[210],gap[210];
int min(int a,int b)
{
return a<b?a:b;
}
void adde(int sn,int fn,int val)
{
e[++tot][0] = fn; e[tot][1] = val; e[tot][2] = p[sn]; p[sn] = cur[sn] = tot;
e[++tot][0] = sn; e[tot][1] = 0; e[tot][2] = p[fn]; p[fn] = cur[fn] = tot;
}
int sap()
{
int i,mmin,sn = S,flow = INF,tans = 0;
gap[0] = (n<<1)+2;
while(dis[S] <= T)
{
for(i=cur[sn];i;i=e[i][2]) if(e[i][1]>0 && dis[sn] == dis[e[i][0]]+1) break;
cur[sn] = i;
if(i)
{
sn = e[i][0]; from[sn] = i;
flow = min(flow,e[i][1]);
if(sn != T) continue;
tans += flow;
for(;sn!=S;sn=e[from[sn]^1][0]) { e[from[sn]][1] -= flow; e[from[sn]^1][1] += flow;}
flow = INF;
}
else
{
if(--gap[dis[sn]] == 0) break;
cur[sn] = p[sn]; mmin = T+3;
for(i=p[sn];i;i=e[i][2]) if(e[i][1]>0) mmin = min(mmin,dis[e[i][0]]);
gap[dis[sn] = mmin+1]++;
if(sn) sn = e[from[sn]^1][0];
}
}
return tans;
}
int main()
{
int i,sn,fn;
scanf("%d%d%d%d",&n,&m,&sta,&fin);
for(i=1;i<=n;i++)
{
if(i == sta || i == fin) adde(i,i+n,INF);
else adde(i,i+n,1);
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&sn,&fn);
adde(sn+n,fn,INF); adde(fn+n,sn,INF);
}
adde(S,sta+n,INF); adde(fin,T,INF);
printf("%d",sap());
return 0;
}

  评论这张
 
阅读(22)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018