题目链接

https://vjudge.net/contest/252211#problem/A

题目大意

T组数据$(T \leq 100)$, 给出一个n个点m条边的无向图$(1 \leq n \leq 10^5, n - 1 \leq m \leq \frac{3}{2} (n - 1))$， 每条边有容量$w_i(1 \leq w_i \leq 10^9)$, 图中最多存在两条完全不相交的路径，图连通， 无自环重边。求$\sum_{s < t} s \oplus t \oplus flow(s,t)$。$(\sum n \leq 10^6)$

题目思路

最多存在两条完全不相交的路径等价于每条边最多属于一个环上。
最大流等于最小割， 考虑割边。
由原图特性， s->t的路径构成为若干个环和一些边。
对于一个简单环， 割边一定是个其中两条边， 且一定包含环上最小的那条边。
对于若干个环加一些边组合在一起， 割边一定是某个环上的两条边或是一条单独的非环边。
将环上的边作特殊处理， 考虑到如果要割的话最小的那条边一定被割， 所以将每个环删去最小边， 将容量加在环上的其他边的上， 不会影响答案。
最后留下一棵树， 考虑从大到小加入每条边， 则新连通的这两个集合之间的最小割即为这条边的容量， 用并查集维护集合中每个二进制位为1的个数， 每次合并之前计算一次贡献即可。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>#define ll long long
#define ull unsigned ll using namespace std;const int N = (int)1e5 + 10;
const int M = (int)1e6 + 10;int n, m;
int cnt, lst[N], nxt[M], to[M], edg[M][3], id[M], del[M];
int gi(){char c = getchar(); int ret = 0;while (!isdigit(c)) c = getchar();while (isdigit(c)){ret = ret * 10 + c - '0';c = getchar();}return ret;
}
void add(int u, int v, int c){nxt[++ cnt] = lst[u]; lst[u] = cnt; to[cnt] = v;nxt[++ cnt] = lst[v]; lst[v] = cnt; to[cnt] = u; 
}int indx, pre[N], dfn[N]; bool vis[N];
void dfs(int u, int pid){vis[u] = 1; dfn[u] = ++ indx;for (int j = lst[u]; j; j = nxt[j]){if (pid == (j / 2)) continue;int v = to[j];if (!vis[v]) {pre[v] = j; dfs(v, j / 2);}else if(dfn[v] < dfn[u]){int wid = j / 2;for (int p = u; p != v; p = to[pre[p] ^ 1]){int k = pre[p] / 2;if (edg[wid][2] > edg[k][2]) wid = k;}del[wid] = 1;for (int p = u; p != v; p = to[pre[p] ^ 1]){int k = pre[p] / 2;if (k == wid) continue;edg[k][2] += edg[wid][2];}if (j / 2 != wid){if (j / 2 != wid){edg[j / 2][2] += edg[wid][2];}}}}
}int fa[N], bit[N][30], sz[N];
int find(int x){if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void unit(int r1, int r2){r1 = find(r1), r2 = find(r2);if (r1 != r2){fa[r1] = r2;for (int j = 0; j < 20; j ++)bit[r2][j] += bit[r1][j];sz[r2] += sz[r1];}
}
bool cmp(int i, int j){return edg[i][2] > edg[j][2];}int main()
{int T = gi();while (T --){n = gi(), m = gi();cnt = 1;for (int i = 1, u, v, c; i <= m; i ++){u = gi(), v = gi(), c = gi();add(u, v, c);edg[i][0] = u, edg[i][1] = v; edg[i][2] = c;}dfs(1, 0);for (int i = 1; i <= m; i ++) id[i] = i;for (int i = 1; i <= n; i ++){fa[i] = i;for (int j = 0; j < 20; j ++) bit[i][j] = (i >> j) & 1;sz[i] = 1;}sort(id + 1, id + m + 1, cmp);ull ans = 0;for (int iid = 1; iid <= m; iid ++){int i = id[iid];if (del[i]) continue;int u = edg[i][0], v = edg[i][1];u = find(u), v = find(v);if (u != v){int w = edg[i][2];for (int j = 0; j < 20; j ++){if ((w >> j) & 1){ans += (ull)bit[u][j] * bit[v][j] * (1 << j);ans += (ull)(sz[u] - bit[u][j]) * (sz[v] - bit[v][j]) * (1 << j);}else{ans += (ull)(sz[u] - bit[u][j]) * bit[v][j] * (1 << j);ans += (ull)bit[u][j] * (sz[v] - bit[v][j]) * (1 << j);}}ans += (ull)(w >> 20) * sz[u] * sz[v] * (1 << 20);unit(u, v);}}printf("%llu\n", ans);for (int i = 1; i <= n; i ++) lst[i] = 0, pre[i] = 0, vis[i] = 0;for (int i = 1; i <= m; i ++) del[i] = 0;}return 0;
}