九敏,RE4个点

P2016 战略游戏

_Faith_ @ 2022-08-11 17:30:22

#include<bits/stdc++.h>
using namespace std;
int ver[2010], hd[1010], idx, nxt[2020], dp[101][2];
int n;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
inline void add(int x, int y) {
    ver[++idx] = y;
    nxt[idx] = hd[x];
    hd[x] = idx;
}
inline void dfs(int x, int y) {
    dp[x][1] = 1;
    dp[x][0] = 0;
    for (int i = hd[x]; i; i = nxt[i]) {
        if (ver[i] == y)
            continue;
        dfs(ver[i], x);
        dp[x][0] += dp[ver[i]][1];
        dp[x][1] += min(dp[ver[i]][1], dp[ver[i]][0]);
    }
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        int x = read() + 1;
        int k = read();
        for (int j = 1; j <= k; j++) {
            int y = read() + 1;
            add(x, y);
            add(y, x);
        }
    }
    dfs(1, 0);
    cout << min(dp[1][0], dp[1][1]);
    return 0;
}

by W9W9 @ 2022-08-11 17:52:13

hd开小了


by ssxvngn @ 2022-08-11 17:57:01

@Faith n\le 1500,数组开成 : int ver[3010], hd[1510], idx, nxt[3020], dp[1510][2];就可以了。


by _Faith_ @ 2022-08-11 17:59:00

谢谢大佬们,AC啦,orz


|