不知道哪里错了 和题解几乎一样
  • 板块P2016 战略游戏
  • 楼主CLCK
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/9/19 22:45
  • 上次更新2023/10/27 10:33:57
查看原帖
不知道哪里错了 和题解几乎一样
323183
CLCK楼主2022/9/19 22:45

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

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

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

万分感谢!!!

#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;
}
2022/9/19 22:45
加载中...