Allorry @ 2023-10-17 15:21:59
求大佬解答,感激不尽
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1510;
int n, m, cnt;
int head[N], f[N][2];
struct edge {
int to, w, next;
}e[N<<1];
void add(int u, int v) {
e[++cnt] = { v, head[u] };
head[u] = cnt;
}
void dfs(int u, int fa) {
f[u][0] = 0, f[u][1] = 1; //初始化,重要
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == fa) continue;
dfs(v, u);
f[u][1] += min(f[v][0], f[v][1]);
f[u][0] += f[v][1];
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
int u, z, v;
cin >> u >> z;
while (z--) {
cin >> v;
add(u, v); add(v, u);
}
}
dfs(0, -1);
cout << min(f[0][0], f[0][1]);
}
by Nobelium_255 @ 2023-10-17 15:29:09
1.无向边 2.无所谓 3.不一样