第五个点我程序它输出太短QWQ,求大佬帮助
查看原帖
第五个点我程序它输出太短QWQ,求大佬帮助
247650
thecold楼主2020/6/25 01:28
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
#include<climits>
#include<cstring>
using namespace std;
inline int read()
{
	int res = 0;
	char c;
	bool flag = true;
	c = getchar();
	while(!isdigit(c))
	{
		if(c == '-')	flag = false;
		c = getchar();
	}
	while(isdigit(c))
	{
		res = res * 10 + (c ^ 48);
		c = getchar();
	}
	return flag ? res : -res;
}
const int Max_n = 1505;
int n , f[Max_n][3] , m , son , u , k[Max_n];//0自己覆盖自己,1儿子覆盖自己,2爸爸覆盖自己
vector<int> v[Max_n];
inline void add_edge(int x , int y)
{
	v[x].push_back(y);
	v[y].push_back(x);
}
inline void dfs(int now , int from)
{
	int sz = v[now].size();
	if(sz == 1)
	{
		f[now][0] = k[now];
		f[now][1] = INT_MAX;
		return;
	}
	bool add = true;
	int getmin = INT_MAX;
	for(int i = 0 ; i < sz ; ++ i)
	{
		int nex = v[now][i];
		if(nex == from)	continue;
		dfs(nex , now);
		f[now][0] += min(f[nex][1] , min(f[nex][2] , f[nex][0]));
		f[now][2] += min(f[nex][0] , f[nex][1]);
		f[now][1] += min(f[nex][0] , f[nex][1]);
		getmin = min(getmin , f[nex][0] - f[nex][1]);
		if(f[nex][0] <= f[nex][1])	add = false;
	}
	f[now][0] += k[now];
	f[now][1] += add * getmin;
}
int main()
{
	n = read();
	for(int i = 1 ; i <= n ; ++ i)
	{
		u = read();
		k[u] = read();
		m = read();
		for(int j = 1 ; j <= m ; ++ j)
		{
			son = read();
			add_edge(u , son);
		}
	}
	dfs(1 , 0);
	printf("%d" , min(f[1][0] , f[1][1]));
	return 0;
 } 
2020/6/25 01:28
加载中...