社区讨论

求助,过了样例但全WA

P2458[SDOI2006] 保安站岗参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lyl0b8no
此快照首次捕获于
2024/07/14 11:39
2 年前
此快照最后确认于
2024/07/14 13:54
2 年前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1505, M = 1000005;

int n;
int h[N], e[M], ne[M], idx;
int f[N][3];//自己看 父亲看 儿子看 
int w[N];
bool vis[N];

void add(int a, int b)  {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}

void dfs(int u)
{
	if (vis[u])  return;
	vis[u] = 1;
	int sum = 0, cnt = 0x3f3f3f3f;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (vis[j])  continue;
		dfs(j);
		f[u][0] += min(f[j][0], min(f[j][1], f[j][2]));
		f[u][1] += min(f[j][0], f[j][1]);
		if (f[j][0] < f[j][2])  sum ++ ;
		else cnt = min(cnt, f[j][0] - f[j][2]);
		f[u][2] += min(f[j][0], f[j][2]);
	}
	if (!sum)  f[u][2] += cnt;
	return;
}

int main()
{
	memset(h, -1, sizeof h);
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ )
	{
		int m, id;
		scanf("%d%", &id);
		scanf("%d%d", &f[id][0], &m);
		int tmp = id;
		while (m -- )  scanf("%d", &id), add(id, tmp), add(tmp, id);
	}
	
	dfs(1);
	printf("%d\n", min(f[1][0], f[1][2]));
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...