贪心做法为什么和P3942不一样。
  • 板块P2016 战略游戏
  • 楼主Herio
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/12 11:32
  • 上次更新2024/12/12 11:58:43
查看原帖
贪心做法为什么和P3942不一样。
257206
Herio楼主2024/12/12 11:32
o[f[w]] = 1;

请问为什么要去掉标记父亲这一行才能过,和P3942的贪心有什么不同吗。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 1505
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,t,b[N],f[N],d[N],o[N],ans,v;
vector<int>e[N];
bool cmp(int x,int y){return d[x]>d[y];}
void dfs(int u,int fa){
	f[u] = fa;
	d[u] = d[fa]+1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs(v,u);
	}
}
int main(){
	scanf("%d",&n);b[1]=1,o[1]=o[0]=N;
	for(int i=1;i<=n;i++){
		int id,x;scanf("%d%d",&id,&x);id++;
		while(x--){
			int y;scanf("%d",&y);y++;
			e[id].emplace_back(y);
			e[y].emplace_back(id);
		}
		b[i] = i;
		o[i] = N;
	}
	dfs(1,0);
	sort(b+1,b+n+1,cmp);
	o[0]=0;  //加上这一句
	FOR(i,1,n){
		v=b[i];
		int w = f[v];
		o[v]=min(o[v],o[w]+1);
		if(o[v]>1){
			o[w]=0,ans++;
			//o[f[w]] = 1;
		}
	}printf("%d",ans);
}
2024/12/12 11:32
加载中...