区域赛名额分配赛被这东西浪费了不少时间，直接导致peanlly++,士气--，然后最后一题还没写完，痛失名额。把有关这个知识点的两道题整理一下吧。

1.ACM International Collegiate Programming Contest Asia Regional Contest, Tokyo, 2012–11–18

　　Problem F Never Wait for Weights

　　https://codeforces.com/group/Us3rfLfgWv/contest/101412

　　题意：有n个数（n <= 1e5），给出m组信息或询问，信息：其中两个数的差；询问：任意两个数的差

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define db long double
 5 #define pii pair<int, int>
 6 #define fi first
 7 #define se second
 8 #define pb push_back
 9 #define all(x) (x).begin(), (x).end()
10 #define inc(i, l, r) for (int i = l; i <= r; i++)
11 #define dec(i, l, r) for (int i = l; i >= r; i--)
12 #define mes(x, k) memset(x, k, sizeof(x))
13 #define bug() printf("LINE: %d\n", __LINE__)
14 const int mod = 1e9 + 7;
15 const int inf = 0x7f7f7f7f;
16 const int maxn = 1e5 + 5;
17 
18 int t, n, m, u, v, val;
19 int par[maxn], ran[maxn];
20 ll dis[maxn];
21 char ch;
22 
23 int find(int x) {
24     if (x == par[x]) return x;
25     int pp = par[x];
26     par[x] = find(par[x]);
27     dis[x] += dis[pp];
28     return par[x];
29 }
30 
31 void unite(int x, int y, int d) {
32     int xx = find(x), yy = find(y);
33     if (ran[xx] >= ran[yy]) {
34         if (ran[xx] == ran[yy]) ran[xx]++;
35         par[yy] = xx;
36         dis[yy] = d + dis[x] - dis[y];
37     } else {
38         par[xx] = par[yy];
39         dis[xx] = -d + dis[y] - dis[x];
40     }
41 }
42 
43 bool same(int x, int y) { return find(x) == find(y); }
44 
45 int main() {
46     while (scanf("%d%d", &n, &m) != EOF, n) {
47         inc(i, 1, n) {
48             par[i] = i;
49             ran[i] = 0;
50             dis[i] = 0;
51         }
52         inc(i, 1, m) {
53             cin >> ch;
54             if (ch == '!') {
55                 scanf("%d%d%d", &u, &v, &val);
56                 unite(u, v, val);
57             } else {
58                 scanf("%d%d", &u, &v);
59                 if (!same(u, v)) {
60                     printf("UNKNOWN\n");
61                 } else {
62                     printf("%d\n", dis[v] - dis[u]);
63                 }
64             }
65         }
66     }
67 }

View Code

2.xdu2019校赛F题 1426：qko的传输

　　http://acm.xidian.edu.cn/problem.php?id=1426

　　

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
#define mes(x, k) memset(x, k, sizeof(x))
#define bug() printf("LINE: %d\n", __LINE__)
const int mod = 1e9 + 7;
const int inf = 0x7f7f7f7f;
const int maxn = 1e6 + 5;

int m, u, v, val;
int par[maxn], ran[maxn], dis[maxn];

int find(int x) {
    if (x == par[x]) return x;
    int pp = par[x];
    par[x] = find(par[x]);
    dis[x] += dis[pp];
    return par[x];
}

void unite(int x, int y, int d) {
    int xx = find(x), yy = find(y);
    if (xx == yy) return;
    if (ran[xx] >= ran[yy]) {
        if (ran[xx] == ran[yy]) ran[xx]++;
        par[yy] = xx;
        dis[yy] = -d + dis[x] - dis[y];
    } else {
        par[xx] = yy;
        dis[xx] = d + dis[y] - dis[x];
    }
}

bool same(int x, int y) { return find(x) == find(y); }

int main() {
    cin >> m;
    inc(i, 1, 2 * m) par[i] = i;
    inc(i, 1, m) {
        scanf("%d%d%d", &u, &v, &val);
        unite(u, v, val);
    }
    cin >> m;
    inc(i, 1, m) {
        scanf("%d%d", &u, &v);
        if (!same(u, v)) {
            printf("Can't reach!\n");
        } else {
            printf("%d\n", dis[u] - dis[v]);
        }
    }
}

View Code