- 科技
- 皇宫看守（树形dp）
思路：根据题意我们可以将每个点划分成3种状态
1.该节点由父节点处放置的守卫看护
2. 该节点由子节点处放置的守护看护
3.该节点由在该节点放置的守卫看护
下面考虑状态转移的过程，建立数组f[i][3]，其中
dp[i][0]表示第i个节点由父节点处放置的守卫看护下的最小代价
dp[i][1]表示第i个节点由子节点处放置的守卫看护下的最小代价
dp[i][2]表示第i个节点由在该节点放置的守卫看护下的最小代价
可以发现在状态1时我们只需要考虑子节点的2种情况放看守或者子节点又子节点的子节点看守，可得dp[u][0]+=min(dp[v][1],dp[v][2]);
状态3时子节点的情况就是以上3种状态的最小值dp[u][2]=min(dp[v][2],min(dp[v][1],dp[v][0]))
状态2时枚举每个子节点当看守的情况其中j为i的子节点，sum为所有子节点j的min(f[j][1],f[j][2])的和，1和3的意义很明显，2的意义代表，如果第i个节点由子节点守卫，那么所有子节点都不能由父节点守卫，并且每个子节点都得到了守卫，且至少有一个子节点处放置了守卫dp[i][1] = min(dp[i][1], sum - min(dp[j][1], dp[j][2]) + dp[j][2]);
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<cstring>
#include<time.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e9+7;
const int N
=2e6+10;
const int M
=1e3+10;
const int inf
=0x3f3f3f3f;
const int maxx
=2e5+7;
const double eps
=1e-6;
int gcd(int a
,int b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
ll
qsm(int a
,int b
,int p
)
{
ll res
=1%p
;
while(b
)
{
if(b
&1)
res
=res
*a
%p
;
a
=1ll*a
*a
%p
;
b
>>=1;
}
return res
;
}
int n
,m
;
struct node
{
int to
,nex
,w
;
}edge
[N
];
int a
[N
];
int head
[N
],tot
;
int dp
[1505][3];
int vis
[N
];
void add(int u
,int v
)
{
edge
[++tot
].to
=v
;
edge
[tot
].nex
=head
[u
];
head
[u
]=tot
;
}
void dfs(int u
)
{
dp
[u
][2]=a
[u
];
for(int i
=head
[u
];~i
;i
=edge
[i
].nex
)
{
int v
=edge
[i
].to
;
dfs(v
);
dp
[u
][2]+=min(dp
[v
][2],min(dp
[v
][1],dp
[v
][0]));
dp
[u
][0]+=min(dp
[v
][1],dp
[v
][2]);
}
dp
[u
][1]=inf
;
for(int i
=head
[u
];~i
;i
=edge
[i
].nex
)
{
int v
=edge
[i
].to
;
dp
[u
][1]=min(dp
[u
][1],dp
[u
][0]+dp
[v
][2]-min(dp
[v
][1],dp
[v
][2]));
}
}
int main()
{
SIS
;
cin
>>n
;
memset(head
,-1,sizeof head
);
for(int i
=1;i
<=n
;i
++)
{
int u
,v
,w
;
cin
>>u
;
cin
>>a
[u
];
int m
;
cin
>>m
;
while(m
--){
cin
>>v
;
add(u
,v
);
vis
[v
]=1;
}
}
int root
=1;
while(vis
[root
])root
++;
dfs(root
);
cout
<<min(dp
[root
][2],dp
[root
][1])<<endl
;
return 0;
}
Processed:
0.011, SQL:
8
