思路上的疑惑

P2016 战略游戏

Allorry @ 2023-10-17 15:21:59

求大佬解答,感激不尽

  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]);
}

by Nobelium_255 @ 2023-10-17 15:29:09

1.无向边 2.无所谓 3.不一样


|