首页 > 代码库 > HDU4738 Caocao's Bridges(桥)
HDU4738 Caocao's Bridges(桥)
http://acm.hdu.edu.cn/showproblem.php?pid=4738
题意:给定一张无向图,求其中权值最小的一座桥,派最少的士兵去炸掉它!!
思路:直接用tarjan计算出桥并且取其中权值最小者。
此题坑点甚多,1、有可能桥本来就不联通,输出-1。2、桥最小者为0,输出1(至少排一个人去炸桥)。3、不要去重边,两个岛之间允许有多座桥,tarjan忽略返回边只忽略一次,加pre_num处理下。
代码:
#include<iostream> #include<cstdio> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) #define inf 0x3f3f3f3f typedef long long LL; using namespace std; const int eps=0.00000001; const int maxn=1005; const int maxm=maxn*maxn*2; int first[maxn],low[maxn],dfn[maxn],fa[maxn],if_add[maxn]; int nex[maxm],u[maxm],v[maxm],w[maxm]; int n,m,ecnt,index,bridge; bool vcut[maxn],ecut[maxm]; void tarjan(int s,int pre) { dfn[s]=low[s]=++index; int son=0; int pre_num=0; for(int e=first[s];~e;e=nex[e]) { if(v[e]==pre&&!pre_num) { pre_num++; continue; } if(!dfn[v[e]]) { son++; tarjan(v[e],s); low[s]=min(low[s],low[v[e]]); if(low[v[e]]>dfn[s]) { bridge++; ecut[e]=1; ecut[e^1]=1; } if(s!=pre&&low[v[e]]>=dfn[s]) { vcut[s]=1; if_add[s]++; } } else low[s]=min(low[s],dfn[v[e]]); } if(s==pre&&son>1)vcut[s]=1,if_add[s]=son-1; } void add_(int a,int b,int c) { u[ecnt]=a; v[ecnt]=b; w[ecnt]=c; ecut[ecnt]=0; nex[ecnt]=first[a]; first[a]=ecnt++; } void solve() { clr(dfn,0); clr(if_add,0); clr(vcut,0); index=bridge=0; for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i,i); } int find_(int x) { if(fa[x]==-1)return x; return fa[x]=find_(fa[x]); } int main() { int a,b,c; while(~scanf("%d%d",&n,&m)&&(n||m)) { clr(first,-1);ecnt=0; clr(fa,-1);int num=n; for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); if(a!=b) { add_(a,b,c),add_(b,a,c); int x=find_(a); int y=find_(b); if(x!=y)fa[x]=y,num--; } } if(num!=1) { puts("0"); continue; } solve(); int ans=inf; for(int i=0;i<ecnt;i+=2) if(ecut[i]&&w[i]<ans)ans=w[i]; if(ans==inf)ans=-1; if(ans==0)ans++; printf("%d\n",ans); } }
HDU4738 Caocao's Bridges(桥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。