思路上的疑惑
查看原帖
思路上的疑惑
592223
Allorry楼主2023/10/17 15:21

求大佬解答,感激不尽

  1. 到底该输入无向边还是有向边?
  2. 输入无向边,dfs(root),root是谁应该无所谓吧,代码错了暂时没改好
  3. 题意理解上,看到所有“边”和看到所有“点”是一样的吗?
#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]);
}
2023/10/17 15:21
加载中...