题解 | #Rinne Loves Edges#
Rinne Loves Edges
https://ac.nowcoder.com/acm/problem/22598
小萌新第一次写题解,只能尽量按照自己的思路讲,如有不清楚或者考虑不周到的地方,请多多谅解。
首先,题目的大意是建一个无向连通图,选择一个点s,让我们删除若干条边,使得除了s以外,其他相邻边数量为一的结点都到不了s,求删除边权值和最小。
题目中应该是默认权值为非负数,然后我们很容易可以想到以s节点为根节点建立树,题目翻译过来就是,叶子结点不能到s结点,那么有两种情况,第一种是和叶子节点相邻的边切断了,另一种是叶子节点的父节点(或者父父节点,又或者是父父父节点(可以有若干层父))被切断了。
先从树的最下层开始推,如果一个叶子节点和父节点的边的权值设为a,它的父节点和父父节点的边的权值设为b,如果该叶子节点的父节点和它包含的所有叶子节点的边权和大于父节点和父父节点的边的权值,那么就不可能切割这些叶子节点和父节点连接的边,而是切割父节点和父父节点连接的边。也就是c = min(ai, b)看做以父节点为根节点的子树所需要付出的最小代价,之后就可以把这个父节点为根节点的子树看做一个叶子节点,用c来当做父节点和父父节点的边的权值,用于后面的比较,之后用递推的思想就可以了。
附上AC代码,时间复杂度O(n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int len = 1e5 + 10; vector<int>edge[2*len];//因为是无向图,所以长度是2*len map<pair<int, int>, ll>dis;//用map来存变权,因为用二维数组可能会爆(没试过,不过1e10的数组一般开不下) ll res[len];//res[len]表示每个节点为根节点向下建立的子树所需要付出的最小代价 void dfs(int x, int fa) { if((int)edge[x].size() == 1 && fa != -1) { res[x] = dis[{x, fa}]; return ; } //如果自身结点x的度为一,fa!=-1表示不是s结点,按照题目要求,这个节点是不能和s结点联通的 //它和s结点间通过切断x和fa间的边来隔断 /*但是不一定要割这条表,因为如果父节点也割断了与s的连接,而且边比现在x和fa的权值小就只需要割父节点 和爷爷节点的连接 */ ll ans = 0; //ans用来记录x的所有子节点向下建成的子树要割的权值总和。 for(int i = 0; i < (int)edge[x].size(); i++) { int y = edge[x][i]; if(y == fa) { continue; } dfs(y, x); ans += res[y]; } res[x] = min(dis[{x,fa}], ans); //在x和fa结点,以及x的所有子节点向下建成的子树要割的权值总和间取最小值。 //这个是以x为父节点所需要付出的最小价值。 return ; } int main() { int n,m,s,u,v,w; cin >> n >> m >> s; //用vector数组存储所有的边,存的是无向图。 for(int i = 0; i < m; i++) { cin >> u >> v >> w; edge[u].push_back(v); edge[v].push_back(u); dis[{u,v}] = w; dis[{v,u}] = w; } dis[{s, -1}] = 0x3f3f3f; //因为用的是dp,每次结果需要根据自身结点与父节点的值以及它的各个子节点的res来更新自身结点的res //而s和-1间没有权重,不可能取到,所以取得是0x3f3f3f(近似看做无穷大) dfs(s, -1); //深度优先搜索建图 cout << res[s]; //答案就是以s为根节点建立的子树付出的最小代价 return 0; }