社区讨论
求助,过了样例但全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 条回复,欢迎继续交流。
正在加载回复...