DAY 12

A,B,C水水

D总出一些奇怪的原因，不过莫名其妙改过去了

E模拟，把所有边存起来排序模拟就行了，简单

#include <bits/stdc++.h>
using namespace std;
long long r, c, p[2505], top, ans, kl[2505];
char a[55][55];
struct sd {
    long long u, v, w;
} b[1662505];
int cmp(sd A, sd B) { return A.w < B.w; }
int main() {
    cin >> r >> c;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (a[i][j] == &#039;X&#039;) {
                for (int h = 1; h <= r; h++) {
                    for (int o = 1; o <= c; o++) {
                        if (a[h][o] == &#039;L&#039;) {
                            top++;
                            b[top].u = (i - 1) * c + j;
                            b[top].v = (h - 1) * c + o;
                            b[top].w = (i - h) * (i - h) + (j - o) * (j - o);
                        }
                    }
                }
            }
        }
    }
    sort(b + 1, b + top + 1, cmp);
    for (int i = 1; i <= top; i++) {
        if (kl[b[i].u] == 0) {
            if (p[b[i].v] == 0) {
                p[b[i].v] = b[i].w;
                kl[b[i].u] = 1;
            } else {
                if (p[b[i].v] == b[i].w) {
                    ans++;
                    kl[b[i].u] = 1;
                    p[b[i].v] = -1;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

F，思路大概是先处理链，再处理环，找环上最少钱就可以

”启动！“（发癫）

的点开始跑（口糊5分钟，代码俩小时）

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, res;
int d[N], f[N], v[N], w[N];
stack<int> stk;
void get(int u) {
    int Min = 1e9;
    for (int j = f[u]; d[j]; u = j, j = f[j]) {
        d[j] = 0;
        int t = max(0, v[j] - w[u]);
        res += t;
        Min = min(Min, v[j] - t);
    }
    res += Min;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &f[i], &w[i]);
        d[f[i]]++;
        v[i] = w[i];
    }
    for (int i = 1; i <= n; i++) {
        if (!d[i])
            stk.push(i);
    }
    while (stk.size()) {
        int u = stk.top();
        stk.pop();
        res += v[u];
        v[f[u]] = max(0, v[f[u]] - w[u]);
        if (!(--d[f[u]]))
            stk.push(f[u]);
    }
    for (int i = 1; i <= n; i++) {
        if (d[i])
            get(i);
    }
    printf("%d", res);
    return 0;
}