CodeForces - 618D Hamiltonian Spanning Tree(思维+贪心)

题目链接：点击查看

题目大意：首先给出n个点，n*(n-1)/2条边组成的无向图，边的权值为y，现在给出一棵连接n个点的树，树上的权值都是x，现在问如何在每个点只遍历一次的情况下走遍n个点，并使一路上权值最小，输出最小权值

题目分析：因为我们需要将n个点连成一条链，所以所需要遍历的边一定是n-1条边，我们现在要做的就是分析如何让这n-1条边的权值和尽量小

我们可以大致分为两种情况来分析：

x>=y：当树上的权值大于图上的权值时，我们肯定以贪心的思想尽可能的不走树上的边：

若该图为菊花图，则中心点只能走树上的边到达其他n-1个点，故此时的答案为(n-2)*y+x

若该图不是菊花图，则任意两点之间肯定有非树边进行连接，故此时的答案为(n-1)*y

x<y：此时树上的权值小于图上的权值，所以贪心的思想肯定尽可能少的走图上的边，我们假设需要走ans条树上的边，那么答案就是ans*x+(n-1-ans)*y

我们可以将第二种情况进一步分析，我们可以将n个点分为不同长度的数个区块，每个区块中的点都可以通过一条链到达，那么我们就可以用图上的边来连接每个区块即可

这样说可能还是有点抽象，我们直接具体到某个节点来分析：

若当前节点x的子节点数大于等于2，那么我们任取两个子节点，根据贪心的思想，将这两个子节点和节点x相连为一条链，分为一个单独的区块，那么剩下的子节点，肯定不能通过节点x到达其祖先节点了，所以只能通过图上的边与其他的点相连

若当前节点x的子节点数小于等于1，我们可以直接将其子节点与节点x相连，并且继续向上延伸，就不用图上的边辅助了

根据上面两种情况设计一下dfs求出ans，答案就出来了

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<int>node[N];int ans=0;bool dfs(int u,int f) {int son=2;//子节点数for(auto v:node[u]){if(v==f)continue;if(dfs(v,u)&&son)//若此时节点u的子节点v可以顺上来一条链，并且当前子节点是前两个，那么就可以将节点u和节点v用树边连接 //若此时节点u的子节点v已经是大于等于2的子节点了，就不能通过树边连接节点u和节点v了{son--;ans++;}}return son>0;//如果节点u的子节点数小于等于1，那么就可以顺一条链上去，否则就是情况1，也就是节点u被两个子节点所占用 }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,x,y;scanf("%d%d%d",&n,&x,&y);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}if(x>=y){bool flag=true;for(int i=1;i<=n;i++)if(node[i].size()==n-1)//判断菊花图{flag=false;break;}if(flag)printf("%lld\n",1LL*(n-1)*y);elseprintf("%lld\n",1LL*(n-2)*y+x);}else{dfs(1,0);printf("%lld\n",1LL*ans*x+1LL*(n-1-ans)*y);}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 618D Hamiltonian Spanning Tree(思维+贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。