Codeforces 828F Best Edge Weight - 随机堆 - 树差分 - Kruskal - 倍增算法

时间:2022-09-12 15:04:34

You are given a connected weighted graph with n vertices and m edges. The graph doesn't contain loops nor multiple edges. Consider some edge with id i. Let's determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don't change the other weights.

You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can't be two edges with changed weights at the same time.

Input

The first line contains two integers n and m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105), where n and m are the number of vertices and the number of edges in the graph, respectively.

Each of the next m lines contains three integers uv and c (1 ≤ v, u ≤ nv ≠ u1 ≤ c ≤ 109) meaning that there is an edge between vertices u and v with weight c.

Output

Print the answer for each edge in the order the edges are given in the input. If an edge is contained in every minimum spanning tree with any weight, print -1 as the answer.

Examples
input
4 4
1 2 2
2 3 2
3 4 2
4 1 3
output
2 2 2 1 
input
4 3
1 2 2
2 3 2
3 4 2
output
-1 -1 -1 

  题目大意 给定一个无向连通带权图,求每条边在所有最小生成树中的最大权值(如果可以无限大就输出-1)。

  对于求1条边在无向连通图带权图的所有最小生成树中的最大权值可以用二分再用Kruskal进行check,但是如果每条边都这么做就会T掉。

  所以考虑整体二分,然而并不行。

  所以考虑先跑一遍Kruskal,然后分类讨论一下:

  1)考虑一条非树边可以取的最大权值。

  考虑把它加入树中,那么会形成1个环,为了保证最小生成树的边权和最小,方法是删掉环上权值最大的一条边。

  所以找到它连接的两端在树上形成的简单路径中边权最大的一个,它的边权-1就是这条非树边的答案。

  这个操作可以用树链剖分或者倍增解决。

  2)考虑一条树边可以取到的最大权值

  具体考虑一条树边会比较难做(不过好像有同学设计了时间戳把它搞定了),但是对于每条非树边都会对它连接的两端在树上形成的简单路径上的所有边有个边权的限制,就是不能超过它的边权 - 1,否则会被它替换掉。

  这个区间取min操作可以用树链剖分。然而考试的时候我脑子瓦特了,觉得线段树不能区间取min(可能是脑补了一个求和操作)

  然后想到了只有到最后会一起求得树边的答案,于是想到了差分。

  为了维护这个最小值,又想到了可并堆。由于要删除,所以可以用下面这个方法构造可删堆(一位dalao的博客提到这个黑科技,我就学习了一下)

    再开一个堆记录要删除的元素,如果两个堆堆顶元素相同,则都弹出堆顶元素。

  于是便又有一个名为树差分 + 可并堆的zz做法。

Code

  1 /**
  2  * Codeforces
  3  * Problem#828F
  4  * Accepted
  5  * Time: 420ms
  6  * Memory: 57864k
  7  */ 
  8 #include <iostream>
  9 #include <fstream>
 10 #include <sstream>
 11 #include <cstdio>
 12 #include <cstdlib>
 13 #include <cstring>
 14 #include <ctime>
 15 #include <cmath>
 16 #include <cctype>
 17 #include <algorithm>
 18 #include <map>
 19 #include <set>
 20 #include <queue>
 21 #include <stack>
 22 #include <vector>
 23 #include <bitset>
 24 #ifdef WIN32
 25 #define Auto "%I64d"
 26 #else
 27 #define Auto "%lld"
 28 #endif
 29 using namespace std;
 30 typedef bool boolean;
 31 #define ll int
 32 #define smin(_a, _b) _a = min(_a, _b)
 33 #define smax(_a, _b) _a = max(_a, _b)
 34 #define fi first
 35 #define sc second
 36 const signed int inf = (signed) (~0u >> 1);
 37 const signed ll llf = (signed ll) (~0ull >> 1);
 38 typedef pair<int, int> pii;
 39 
 40 template<typename T>
 41 inline void readInteger(T& u) {
 42     static char x;
 43     while(!isdigit(x = getchar()));
 44     for(u = x - '0'; isdigit(x = getchar()); u = u * 10 + x - '0');
 45 }
 46 
 47 template<typename T>
 48 class Matrix {
 49     public:
 50         T* p;
 51         int row;
 52         int col;
 53         Matrix():p(NULL) {        }
 54         Matrix(int row, int col):row(row), col(col) {
 55             p = new T[(row * col)];
 56         }
 57         
 58         T* operator [] (int pos) {
 59             return p + (pos * col);
 60         }
 61 };
 62 #define matset(a, i, s)    memset(a.p, i, sizeof(s) * a.row * a.col)
 63 
 64 typedef class Edge {
 65     public:
 66         int u;
 67         int v;
 68         int w;
 69         boolean seced;
 70         int rid;
 71         
 72         Edge(int u = 0, int v = 0, int w = 0):u(u), v(v), w(w), seced(false) {    }
 73 
 74         boolean operator < (Edge b) const {
 75             return w < b.w;
 76         }
 77 }Edge;
 78 
 79 typedef class Node {
 80     public:
 81         int val;
 82         Node *nxt[2];
 83         
 84         Node(int val = inf):val(val) {    nxt[0] = nxt[1] = NULL;    }
 85 }Node;
 86 
 87 typedef pair<Node*, Node*> pnn;
 88 #define limit 1000000
 89 
 90 Node pool[limit];
 91 Node *top = pool;
 92 
 93 Node* newnode(int x) {
 94     if(top == pool + limit)
 95         return new Node(x);
 96     *top = Node(x);
 97     return top++;
 98 }
 99 
100 Node* merge(Node* &l, Node* r) {
101     if(l == NULL)    return r;
102     if(r == NULL)    return l;
103     if(l->val > r->val)    swap(l, r);
104     int p = rand() % 2;
105     l->nxt[p] = merge(l->nxt[p], r);
106     return l;
107 }
108 
109 int n, m;
110 Edge* edge;
111 int* res;
112 int* ans;
113 
114 inline void init() {
115     readInteger(n);
116     readInteger(m);
117     edge = new Edge[(m + 1)];
118     for(int i = 1; i <= m; i++) {
119         readInteger(edge[i].u);
120         readInteger(edge[i].v);
121         readInteger(edge[i].w);
122         edge[i].rid = i;
123     }
124 }
125 
126 int *f;
127 
128 int find(int x) {
129     return (f[x] != x) ? (f[x] = find(f[x])) : (x);
130 }
131 
132 vector<int> *g;
133 vector<int> *add;
134 vector<int> *del;
135 
136 inline void Kruskal() {
137     f = new int[(n + 1)];
138     g = new vector<int>[(n + 1)];
139     for(int i = 1; i <= n; i++)
140         f[i] = i;
141     sort(edge + 1, edge + m + 1);
142     int fin = 0;
143     for(int i = 1; i <= m && fin < n - 1; i++) {
144         if(find(edge[i].u) != find(edge[i].v)) {
145             f[find(edge[i].u)] = find(edge[i].v);
146             g[edge[i].u].push_back(i);
147             g[edge[i].v].push_back(i);
148             edge[i].seced = true;
149             fin++;
150         }
151     }
152 }
153 
154 const int BZMAX = 18;
155 int* dep;
156 Matrix<int> bz;
157 Matrix<int> bzm;
158 
159 void dfs1(int node, int fa, int lastv) {
160     dep[node] = dep[fa] + 1;
161     bz[node][0] = fa;
162     bzm[node][0] = lastv;
163     for(int i = 1; i < BZMAX; i++)
164         bz[node][i] = bz[bz[node][i - 1]][i - 1], bzm[node][i] = max(bzm[node][i - 1], bzm[bz[node][i - 1]][i - 1]);
165     for(int i = 0; i < (signed)g[node].size(); i++) {
166         if(!edge[g[node][i]].seced)    continue;
167         int e = (edge[g[node][i]].u == node) ? (edge[g[node][i]].v) : (edge[g[node][i]].u);
168         if(e == fa)    continue;
169         dfs1(e, node, edge[g[node][i]].w);
170     }
171 }
172 
173 pii lca(int u, int v) {
174     if(dep[u] < dep[v])    swap(u, v);
175     int rtmax = 0;
176     int ca = dep[u] - dep[v];
177     for(int i = 0; i < BZMAX; i++)
178         if(ca & (1 << i)) {
179             smax(rtmax, bzm[u][i]);
180             u = bz[u][i];
181         }
182     if(u == v)    return pii(u, rtmax);
183     for(int i = BZMAX - 1; ~i; i--) {
184         if(bz[u][i] != bz[v][i]) {
185             smax(rtmax, bzm[u][i]);
186             smax(rtmax, bzm[v][i]);
187             u = bz[u][i];
188             v = bz[v][i];
189         }
190     }
191     smax(rtmax, bzm[u][0]);
192     smax(rtmax, bzm[v][0]);
193     return pii(bz[u][0], rtmax);
194 }
195 
196 pair<Node*, Node*> dfs2(int node, int fa, int tofa) {
197     Node* rt = NULL;
198     Node* dl = NULL;
199     for(int i = 0; i < (signed)g[node].size(); i++) {
200         if(!edge[g[node][i]].seced)    continue;
201         int e = (edge[g[node][i]].u == node) ? (edge[g[node][i]].v) : (edge[g[node][i]].u);
202         if(e == fa)    continue;
203         pnn ap = dfs2(e, node, g[node][i]);
204         rt = merge(rt, ap.fi);
205         dl = merge(dl, ap.sc);
206     }
207     for(int i = 0; i < (signed)add[node].size(); i++)
208         rt = merge(rt, newnode(add[node][i]));
209     for(int i = 0; i < (signed)del[node].size(); i++)
210         dl = merge(dl, newnode(del[node][i]));
211     while(dl && rt->val == dl->val) {
212         rt = merge(rt->nxt[0], rt->nxt[1]);
213         rt = merge(rt->nxt[0], rt->nxt[1]);
214         dl = merge(dl->nxt[0], dl->nxt[1]);
215     }
216     res[tofa] = (!rt) ? (-1) : (rt->val);
217     return pnn(rt, dl);
218 }
219 
220 inline void solve() {
221     res = new int[(m + 1)];
222     dep = new int[(n + 1)];
223     bz = Matrix<int>(n + 1, BZMAX);
224     bzm = Matrix<int>(n + 1, BZMAX);
225     dep[0] = 0;
226     for(int i = 0; i < BZMAX; i++)
227         bz[0][i] = bzm[0][i] = 0;
228     dfs1(1, 0, 0);
229     add = new vector<int>[(n + 1)];
230     del = new vector<int>[(n + 1)];
231     for(int i = 1; i <= m; i++) {
232         if(edge[i].seced)    continue;
233         int u = edge[i].u, v = edge[i].v;
234         pii l = lca(u, v);
235         res[i] = l.sc - 1;
236         add[u].push_back(edge[i].w - 1);
237         add[v].push_back(edge[i].w - 1);
238         del[l.fi].push_back(edge[i].w - 1);
239     }
240     dfs2(1, 0, 0);
241     ans = new int[(m + 1)];
242     for(int i = 1; i <= m; i++)
243         ans[edge[i].rid] = res[i];
244     for(int i = 1; i <= m; i++)
245         printf("%d ", ans[i]);
246 }
247 
248 int main() {
249     srand(233);
250     init();
251     Kruskal();
252     solve();
253     return 0;
254 }