求大佬帮助

P2016 战略游戏

神之蒟蒻xyk @ 2019-10-05 21:26:42

感觉这道题和P2279 [HNOI2003]消防局的设立 一模一样

为什么同样的贪心,这道题只能过一个点? 求救

#include<bits/stdc++.h>
#define fir(a, b, c) for(register int a = b; a <= c; a ++)
#define ll long long
using namespace std;
inline int read(){
    int x = 0; bool flg = 1; char c = getchar();
    for(; !isdigit(c); c = getchar()) if (c == '-') flg = 0;
    for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    return flg ? x : -x;
}

const int N = 2010;
int n, head[N], l, fa[N];
struct node{
    int v, nxt;
}e[2*N];
inline void add(int u, int v){e[++l].v = v; e[l].nxt = head[u]; head[u] = l;}
int o[N];

int ans;
bool vis[N];

void work(int p){
    int t1 = N;
    for(int i = head[p]; i; i = e[i].nxt){
        int y = e[i].v;
        vis[y] = 1;
        work(y);
    }
    t1 = o[fa[p]];
    o[p] = min(o[p], t1+1);
    if(o[p] <= 1) return;
    else {
        o[p] = 1;
        o[fa[p]] = 0;
        o[fa[fa[p]]] =  min(o[fa[fa[p]]], 1);
        ans ++;
    }
}

int main(){
        n = read();
        for(int i = 1; i <= n; i++){
            int x, t;
            char ch;
            x = read(); t = read();
            x ++;
            int y;
            while(t--){
                y = read();
                y ++;
                add(x, y);
                fa[y] = x;
            }
        }
        fir(i, 0, n) o[i] = N;
        ans = 0;
        int rt = 0;
        fir(i, 1, n){
            if(vis[i]) continue;
            if(fa[i] == 0) continue;
            vis[i] = 1;
            work(i);
        }
        cout<<ans<<endl;
    return 0;
}

|