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
感激不尽