P3931 SAC E#1 - 一道难题Tree题解(树型dp|dfs|网络流)

Description

传送门:P3931

冴月麟为了守护幻想乡,而制造了幻想乡的倒影,将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了,但是她给前来救她的魏潇承留了一个线索。

她设置了一棵树(有根)。树的每一条边上具有割掉该边的代价。

魏潇承需要计算出割开这棵树的最小代价,这就是冴月麟和魏潇承约定的小秘密。

帮帮魏潇承吧。

注:所谓割开一棵有根树,就是删除若干条边,使得任何任何叶子节点和根节点不连通。


Input

输入第一行两个整数n,S表示树的节点个数和根。

接下来n-1行每行三个整数a、b、c,表示a、b之间有一条代价为c的边。

Output

输出包含一行,一个整数,表示所求最小代价。

Sample Input

1
2
3
4
5
6
7
8
9
4 1
1 2 1
1 3 1
1 4 1

4 1
1 2 3
2 3 1
3 4 2

Sample Output

1
2
3
3

1

题目大意

给你一颗有根树,对于每一条边割去这条边有一个代价,问使根节点到所有叶子节点不连通的最小代价。

思路

这道题可以用树型dp,dfs或者网络流都可以做,但是我没做过树型dp的题,所以用树型dp写了一下,定义\(dp[i]\)为使得\(i\)到以\(i\)为子树的叶子节点需要的最小代价,那么状态转移方程就是\(dp[i] = \sum_{j \in son_i}{min(w_{i->j},dp[j])}\),对于叶子节点有\(dp[i]=INF\),使得\(i\)\(j\)的叶子节点不连通,那么可以通过删除\(j\)子树中的边或者\(i\)\(j\)这条边,然后最小代价,就取这两者之间的较小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/************************************************************
> File Name: P3931.cpp
> Author: TSwiftie
> Mail: 2224273204@qq.com
> Created Time: Fri 20 Dec 2019 02:53:12 PM CST
************************************************************/

#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
#define lowbit(x) (x&-x)
#define lc (o<<1)
#define rc (o<<1|1)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
const int MOD = 1e9+7;
const int dir[4][2] = {1,0,-1,0,0,1,0,-1};
const double PI = acos(-1.0);
const double EXP = 1e-8;
struct Edge{
int v,w,next;
}edge[MAXN<<1];
int head[MAXN],tot;
int n, S;
void add_edge(int u,int v,int w){
edge[++tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot;
}
int dp[MAXN];
void dfs(int u,int pre){
dp[u] = 0;
bool mark = true;//判断叶子节点
for(int i = head[u];i;i = edge[i].next){
int v = edge[i].v;
if(v==pre)
continue;
mark = false;
dfs(v,u);
dp[u] += min(edge[i].w,dp[v]);
}
if(mark)//如果这个节点是叶子节点
dp[u] = INF;
}
int main(void){
scanf("%d%d",&n,&S);
for(int i = 1;i < n;i++){
int u, v, w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
dfs(S,0);
printf("%d\n",dp[S]);
return 0;
}

本文标题:P3931 SAC E#1 - 一道难题Tree题解(树型dp|dfs|网络流)

文章作者:TSwifite

发布时间:2019年12月20日 - 15:12

最后更新:2019年12月20日 - 15:12

原始链接:http://tswiftie.com/P3931-SAC-E-1-一道难题Tree题解-树型dp-dfs-网络流/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%