不知道哪里错了 和题解几乎一样

P2016 战略游戏

CLCK @ 2022-09-19 22:45:34

求大佬帮忙看看,前向星那块应该是对的

和题解对下来只有标记的地方不太一样

不知道前向星判断父节点的写法(就是第一处不一样)是不是有点问题

万分感谢!!!

#include <iostream>
using namespace std;
int n, cur, ans = 0x3f3f3f3f;
int head[1505], Next[1505];
int fl[1505], ver[1505];
int dp[1505][2];
int f = 0x3f3f3f3f;
void add(int x, int y) {
    ver[++cur] = y;
    Next[cur] = head[x], head[x] = cur;
}
void dfs(int t) {
    dp[t][1] ++;
    fl[t] = 1;
    for (int i = head[t]; i; i = Next[i]) {
        int y = ver[i];
        if (fl[y]) continue; //这里不太一样!
        dfs(y);
        dp[t][0] += dp[y][1];
        dp[t][1] += min(dp[y][0], dp[y][1]);
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, k;
        cin >> x >> k;
        for (int j = 0; j < k; j++) {
            int s;
            cin >> s;
            add(x, s);
            add(s, x);
        }
    }
    //dp[0][1] = 1;
    dfs(0);
    cout << min(dp[0][0], dp[0][1]) << endl; //这里也不太一样!
    return 0;
}

by CLCK @ 2022-09-19 22:46:07

BF写的题解~


by Wilson_Lee @ 2022-09-21 20:19:06

@CLCK 边要开两倍……


by CLCK @ 2022-09-21 20:51:19

@Wilson_Lee 啊啊啊啊啊

太久没写忘记了QAQ

感激不尽


|