题意
给出一个图，和一堆边，不保证没有重边，每一个边上携带者一个权值，现在问你能不能删去一条边，使图不再联通。可以的话删去权值最小的那条边，并且输出这个权值。
注意(坑点)
因为题意的特殊性，如果图本来就不联通，输出0.如果可以满足条件但最小的权值恰好是0，要输出1。
思路
删一个边把图裂开这种要求很明显就是找图的割边了。寻找割边是很典型的问题，应该使用tarjan算法，但是一定要注意重边对于找割边的影响(因为割边删掉后，图应该会裂开，但是如果有重边，删掉一条，还有一条，图显然不会裂开)，因此我们要对原来的方法稍作修改，首先是存图的方式，我们不能漏掉任意一条边，因此一个理想的方式就是链式前向星。链式前向星有一个很好用的特性，我们在创建无向边的时候实际上是创建了两条有向边，而这两条有向边在链式前向星的容器中的编号是相邻的，也就是说对于编号i的边i^1就是这条边对应的反向边，这样我们就可以非常方便地标记这条边是不是已经走过(vis_e[i] = vis_e[i^1] = true)。tarjan部分附带了注释。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
// // HDU4738.cpp // playground // // Copyright (c) 2015 Adam Chang. All rights reserved. // #include <iostream> #include <iomanip> #include <algorithm> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <cmath> using namespace std; #define MAXN 1005 #define MAXE 2000005 struct EDGE { int u, v, w; int next; }; int first[MAXN], rear; EDGE edge[MAXE]; void init(int n) { memset(first, -1, sizeof(first[0])*(n+1)); rear = 0; } void insert(int tu, int tv, int tw) { edge[rear].u = tu; edge[rear].v = tv; edge[rear].w = tw; edge[rear].next = first[tu]; first[tu] = rear++; edge[rear].u = tv; edge[rear].v = tu; edge[rear].w = tw; edge[rear].next = first[tv]; first[tv] = rear++; } int pre[MAXN], low[MAXN]; bool vis_e[MAXE]; //是否访问了边 bool is_bridge[MAXE]; //是否是桥 int dfs_clock; int res = 909303; void dfs(int cur) { pre[cur] = low[cur] = ++dfs_clock; for(int i = first[cur]; ~i; i = edge[i].next) { //便利以当前点出发的所有边 int tv = edge[i].v; if(!pre[tv]) { //如果这条边连接着的节点还没有访问过，那就进到这个节点里面 vis_e[i] = vis_e[i^1] = true; dfs(tv); low[cur] = min(low[cur], low[tv]); if(pre[cur] < low[tv]){ //当前边连着的这个节点处理完毕了，如果发现这个节点的low值还是比当前节点大，说明这个节点及其联通部分没有指向已访问任何节点的回边，也就是说割开当前这条边，这个节点以及其联通的部分就和当前节点裂开了，这条边也就理所当然的是割边 is_bridge[i] = is_bridge[i^1] = true; res = min(res,edge[i].w);//更新答案用的 } } else if(pre[tv] < pre[cur] && !vis_e[i]) { //这里是如果当前这条边是一条回边，那么就要更新当前节点的low值了 vis_e[i] = vis_e[i^1] = true; low[cur] = min(low[cur], pre[tv]); } } } void find_bridge(int n) { res = 909303; dfs_clock = 0; memset(pre, 0, sizeof(pre[0])*(n+1)); memset(vis_e, 0, sizeof(vis_e[0])*rear); memset(is_bridge, 0, sizeof(is_bridge[0])*rear); dfs(1); } int main(){ int n = 0,m = 0; while (scanf(" %d %d",&n,&m) != EOF) { if (n == 0 && m == 0) { break; } init(n); for (int i = 1; i <= m; i++) { int u = 0,v = 0,w = 0; scanf(" %d %d %d",&u,&v,&w); insert(u, v, w); } find_bridge(n); if (dfs_clock < n) { cout << 0 << endl; }else if (res == 909303) { cout << -1 << endl; }else if(res == 0){ cout << 1 << endl; }else { cout << res << endl; } } } |
