神之蒟蒻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;
}