hex2007 @ 2022-10-26 18:07:09
RT
代码如下
#include<iostream>
#include<cstdio>
#define NUM 1510
#define FOR(a,b,c) for( int a = b;a <= c;a++ )
using namespace std;
int n;
struct bian { //边
int next, to;
};
bian e[NUM << 4];
int head[NUM];
int cnt;
void add( int x, int y ) {
e[++cnt].next = head[x];
e[cnt].to = y;
head[x] = cnt;
}
int tou = 0x7f7f7f;//记录树根
int ling;//零(ling 表示白色节点的数量)
int yi;//一(yi 表示黑色节点的数量)
bool v[NUM];
void dfs( int p, int now ) {
if ( v[p] ) return; //防止多次访问同一个点
v[p] = 1;
if ( now ) yi++;
else ling++;
for ( int i = head[p]; i; i = e[i].next ) {
int to = e[i].to;
dfs( to, now ^ 1 );
}
}
int main() {
cin >> n;
FOR( i, 1, n ) {
int x, y, z;
cin >> x >> y;
tou = min(tou, x); //用编号最小的点当做树根
FOR( j, 1, y ) { //无向边
cin >> z;
add( x, z );
add( z, x );
}
}
dfs( tou, 0 ); //黑白染色
cout << min( ling, yi ); //取黑或取白
return 0;
}
by Strelitzia_ @ 2022-10-26 18:27:02
有没有这样一种可能,就是说,这个题正解是树形 DP
by hzy1 @ 2023-01-30 14:41:43
黑白染色不一定最优,比如这个图,选中间两个相邻的点才是最优的。
by y_kx_b @ 2023-03-01 21:10:29
@Strelitzia_ 有没有这样一种可能,就是说,楼主问的是这题为什么不能用黑白染色,而不是为什么可以树形 dp
一题多解很常见吧,只不过 lz 的贪心假了(悲
by y_kx_b @ 2023-03-01 21:11:19
@hex2007 楼上的楼上已经给出了答案,at lz 捞一下 qwq