求助,WAon#3,实在调不出来了
查看原帖
求助,WAon#3,实在调不出来了
1011907
_QWQ_TAT_楼主2024/4/6 09:28

rt,

#include<bits/stdc++.h>
using namespace std;

struct Edge{
	int to,next;//to是去哪,next是上一个同起点下标在哪 
};

int n,cnt;
int dp[1505][10];
int head[1505];
Edge edge[2005];
int treb[1505];
int rot;
bool vis[1505];

void init(){
	memset(dp,0,sizeof (dp));
	memset(head,-1,sizeof(head));
	cnt=0;
}
void add_edge(int u,int v){
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void dpp(int u,int fa){
	bool aa=0;int mnmin=1e9;
	for (int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
//		if (v==fa) continue;
		dpp(v,u);
		dp[u][0]+=min(min(dp[v][0],dp[v][1]),dp[v][2]);
		dp[u][2]+=min(dp[v][0],dp[v][1]);
		if (dp[v][0]<dp[v][1])aa=1;
		else mnmin=min(mnmin,dp[v][0]-dp[v][1]);
		dp[u][1]+=min(dp[v][0],dp[v][1]);
	}
	if (!aa) dp[u][1]+=mnmin;
}
int main(){
	init();
	cin>>n;
	for (int i=1;i<=n;i++){
		int u,pnt,mm,v;
		cin>>u;cin>>pnt>>mm;
		dp[i][0]=pnt;
		for (int j=1;j<=mm;++j){
			cin>>v;
			add_edge(u,v);
//			add_edge(v,u);
			vis[v]=1;
		}
	}//puts("    ");
	for (int i=1;i<=n;i++) if (!vis[i]) rot=i;
	dpp(rot,-1);
//	for(int i=1;i<=n;++i){
//		for (int k=0;k<3;++k) cout<<dp[i][k]<<" ";puts(" "); 	
//	}
	cout<<min(dp[rot][0],dp[rot][1]);
	return 0;
}
2024/4/6 09:28
加载中...