黑白染色为什么不能过

P2016 战略游戏

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


|