皇后看守
作者:
wyatt
,
2022-04-06 12:31:25
,
所有人可见
,
阅读 179
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3500;
int e[N],ne[N],h[N],idx = 0;
int w[N];
bool st[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int f[N][3];
void dfs(int u,int p)
{
f[u][2] = w[u]; // 选择当前节点 默认 cost
f[u][0] = 0;
for(int i = h[u] ; i != -1 ; i = ne[i])
{
int j = e[i];
if(j == p)continue;
dfs(j,u);
f[u][0] += min(f[j][2],f[j][1]); // 当前节点被父亲节点看见,所以子节点可以 放,或者 被子节点(对于 j来说)看见
f[u][2] += min(f[j][0],min(f[j][1],f[j][2])); // 当前放,子节点无所谓
}
f[u][1] = 1e9;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(p == j)continue;
f[u][1] = min(f[u][1],f[u][0] - min(f[j][1],f[j][2]) + f[j][2] ); // f[u][0] = sum 要总的,所以f[u][1]要后算
}
}
int main()
{
memset(h, -1, sizeof h);
int n;
cin >> n;
for (int i = 1; i <= n; i ++ )
{
int x , cost , cnt;
cin >> x >> cost >> cnt;
int y;
w[x] = cost; // 当前点设置最小花费
while(cnt--)
{
cin >> y;
add(x,y);
st[y] = true;
}
}
int root = -1;
for (int i = 1; i <= n; i ++ )
{
if(!st[i])
{
root = i;
break;
}
}
dfs(root,-1);
cout << min(f[root][1],f[root][2]);
}