1048 【图论进阶】截断通路

《1048 【图论进阶】截断通路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【图论进阶】截断通路TimeLimit:10000MS MemoryLimit:65536KTotalSubmit:8Accepted:1Description截断通路(sever)　　苏联在天才总书记天凯的带领下，迅速发展，一片欣欣向荣之势。经过一个星期的努力，苏联已经兴建起了n多道路，这使得想对其进行轰炸的美帝国感到十分的不爽。好战的美帝国头头LYNN制定了初步的攻击计划：切断苏联两个重镇之间的联系（也就是使这两城之间没有通路）。他们掌握了苏联道路的准确情况，并估算出轰炸一条道路所需的耗费。　　现在，请

2、你计算出切断s,t两城之间联系的最少耗费。(双向边)Input　　第一行包含三个整数，分别为N,S,T。（N<=100）　　接下来的若干行每行包含三个正整数a,b,c。分别表示城市a,b之间有道路相连，摧毁这条道路的耗费为c(c<=100)。Output　　一个整数：最少耗费。SampleInputsever.in313121232SampleOutputsever.out1Source解法：直接用最大流求两点间的最少费用。程序：constmaxn=100;vari,j,k,n,s,t,ans,m:long

3、int;a:array[1..maxn,1..maxn]oflongint;b:array[1..maxn]ofboolean;g,d:array[0..maxn]oflongint;found:boolean;proceduredfs(x:longint);vari,temp,md:longint;beginifx=tthenbeginans:=ans+m;found:=true;exitend;temp:=m;md:=n-1;fori:=1tondoifa[x,i]<>0thenbeginifd[i]<

4、mdthenmd:=d[i];if(notb[i])and(d[i]+1=d[x])thenbeginb[i]:=true;ifa[x,i]

5、lenoteolndobeginread(i,j,k);ifa[i,j]<>0thenbeginifk

6、int;dfs(s)end;writeln(ans);end.