poj3352——Road Construction//最小割边
题意：最少添加多少条边，可以让图成为双向连通图。对trajan算法求最小割还没了解透彻，参考博客：http://www.cppblog.com/Icyflame/archive/2009/07/04/89227.html
http://hi.baidu.com/buaa_babt/blog/item/4d9a16c934384e2cf9dc61da.html
http://hi.baidu.com/archersfate/blog/item/c573f07b89faf6e42e73b3a1.html
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,r;#define maxn 1005class node{public:int to,next;};node g;int head,cnt;int dfn,low,du;void add(int u,int v){g[++cnt].to =v;g.next =head;head=cnt;}void dfs(int u,int fa){dfn=low=++cnt;int i;for(i=head;i;i=g.next ){int v=g.to;if(!dfn){dfs(v,u);low=min(low,low);}else if(v!=fa){low=min(low,dfn);}}}void solve(){int i,j,ans=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));cnt=0;dfs(1,-1);memset(du,0,sizeof(du));for(i=1;i<=n;i++){for(j=head;j;j=g.next ){int v=g.to;if(low!=low) du]++;}}for(i=1;i<=n;i++)if(du==1)ans++;printf("%d\n",(ans+1)/2);}int main(){int a,b;while(scanf("%d%d",&n,&r)!=EOF){cnt=0;while(r--){scanf("%d%d",&a,&b);add(a,b);add(b,a);}solve();}return 0;}
页:
[1]