我傻掉了,90分求助
查看原帖
我傻掉了,90分求助
209808
银河AI楼主2021/7/4 16:29
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15010,inf=1e9;
int n;
int k[N];
struct edge{
	int to,ne;
}e[N<<2];
int adj[N],l;
int ind[N],rt;
int f[N][3];//0-wu,1-fugai,2-you
inline void add(int x,int y){e[++l].to=y,e[l].ne=adj[x],adj[x]=l;}
void dfs(int x,int fa){
	f[x][2]=k[x];
	for(int i=adj[x];i;i=e[i].ne){
		int y=e[i].to;
		if(y==fa) continue;
		dfs(y,x);
		f[x][0]+=min(f[y][1],f[y][2]);
		f[x][2]+=min(min(f[y][1],f[y][0]),f[y][2]);
	}
	int q=f[x][0];f[x][1]=inf;
	for(int i=adj[x];i;i=e[i].ne){
		int y=e[i].to;
		if(y==fa) continue;
		f[x][1]=min(f[x][1],q-min(f[y][1],f[y][2])+f[y][2]);
	}
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%lld%lld",&x,&k[i]);
		int m;
		scanf("%lld",&m);
		for(int j=1;j<=m;j++){
			int y;
			scanf("%lld",&y);
			add(x,y);add(y,x);
		}
	}
	dfs(1,0);
	printf("%lld",min(f[1][1],f[1][2]));
}

感谢

2021/7/4 16:29
加载中...