首页 > 代码库 > hdu Caocao's Bridges(无向图边双连通分量,找出权值最小的桥)
hdu Caocao's Bridges(无向图边双连通分量,找出权值最小的桥)
1 /* 2 题意:给出一个无向图,去掉一条权值最小边,使这个无向图不再连同! 3 4 tm太坑了... 5 1,如果这个无向图开始就是一个非连通图,直接输出0 6 2,重边(两个节点存在多条边, 权值不一样) 7 3,如果找到了桥的最小权值为0,也就是桥上的士兵数为0,那么还是要最少派一个 8 士兵过去炸掉桥! 9 10 思路:假设每两个节点最多只有一条边进行相连!11 进行tarjan算法,如果该算法调用了超过2次,说明这个原图就是不连通的!12 否则在tarjan算法中将桥存起来!然后我们遍历每一座桥,看一看我们找到的13 桥(连接的两个定点分别是u, v)是不是(u, v)只有一条路相连接,如果是的,14 那么就跟新最小值! 15 */16 #include<iostream>17 #include<cstdio>18 #include<cstring>19 #include<algorithm>20 #define M 100000521 #define INF 0x3f3f3f3f22 #define N 100523 using namespace std;24 struct EDGE{25 int u, v, w, nt; 26 EDGE(){}27 EDGE(int u, int v, int w, int nt){28 this->u=u;29 this->v=v;30 this->w=w;31 this->nt=nt; 32 }33 };34 35 EDGE edge[M];36 EDGE brige[M];37 int first[N];38 int low[N], pre[N];39 int dfs_clock;40 int n, m, cnt, ret;41 42 43 void tarjan(int u, int fa){44 low[u]=pre[u]=++dfs_clock;45 for(int e=first[u]; e!=-1; e=edge[e].nt){46 int v=edge[e].v;47 48 if(!pre[v]){49 tarjan(v, u);50 low[u]=min(low[u], low[v]);51 if(low[v]>pre[u])52 brige[ret++]=edge[e];53 } 54 else if(v!=fa && pre[u]>pre[v])55 low[u]=min(low[u], pre[v]);56 } 57 }58 59 int main(){60 while(scanf("%d%d", &n, &m) && (n||m)){61 memset(first, -1, sizeof(first));62 cnt=0;63 while(m--){64 int u, v, w;65 scanf("%d%d%d", &u, &v, &w);66 edge[cnt]=EDGE(u, v, w, first[u]);67 first[u]=cnt++;68 edge[cnt]=EDGE(v, u, w, first[v]);69 first[v]=cnt++;70 } 71 dfs_clock=0;72 ret=0;73 memset(low, 0, sizeof(low));74 memset(pre, 0, sizeof(pre)); 75 int flag=0;76 for(int i=1; i<=n; ++i)77 if(!pre[i]){78 ++flag;79 if(flag==2) break;80 tarjan(i, -1);81 }82 83 int minNum=INF;84 if(flag==2) minNum=0;85 else{86 for(int i=0; i<ret; ++i)87 if(brige[i].w<minNum){//对假定的桥判断 88 int cc=0;89 for(int e=first[brige[i].u]; e!=-1; e=edge[e].nt)90 if(edge[e].v==brige[i].v) ++cc;91 if(cc==1) minNum=brige[i].w;//说明是真正的桥 92 }93 if(minNum==INF) minNum=-1;94 else if(minNum==0) minNum=1;//这一句不要忘记了! 95 }96 printf("%d\n", minNum);97 } 98 return 0; 99 }
hdu Caocao's Bridges(无向图边双连通分量,找出权值最小的桥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。