【题解】CF618D Hamiltonian Spaning Tree

· · 题解

前言

我不会DP，但我会运用人类本质。

题目

给定一个 n 个点的完全图，边权相同为 y ，在完全图中标定一颗生成树，树上边权变为 x，求不重复遍历所有节点的最短路径长度。

思路

既然题目中非常鲜明地指出了 不过注意x不一定小于y 那么肯定是让我们来进行分类讨论的。

一、完全图的边权更小。

大家肯定知道这个情况一定会选择更小的，也就是使选择的完全图的边更多一些。

那么现在讨论两种情况：

1、菊花图。

生成树为菊花图说明必须要选择一条树边 e，那么其他的路径一定可以在完全图的边上遍历完成，所以其他的选择完全图上的边即可。答案为 \text{x+(n-2)y}。

判断是否为菊花图，只需要判断一个点的出度是否为 \text{n-1} 即可。

2、非菊花图。

这个时候连接一个点的边一定有一条是完全图边，那么肯定有一条路径是不会经过任何的树边的，可以手模几组样例尝试尝试。

此时的答案就是 (\text{n-1}) y 。

二、边权相同。

那肯定随便选就行了，答案为 (\text{n-1})y。

三、树边的边权更小。

根据贪心思想，一定会尽可能多得选择树边去走，但是这个并没有一些很固定的规律，那么就可以利用人类本质了，可以发现，路径中一个点的度最大为 2，也就是

a-x-b

一条进，一条出。

那么我们就会贪心地想，尽量使选择的树边最多，那么就可以用深搜判断是否可以选择即可。

最后答案就是 cnt_e y+(n-cnt_e-1) x

代码实现

/*

    分类讨论:

    生成树边x > 完全图边y : 1、非菊花图，通过手模发现，只要生成树不是菊花图，那么一定可以找到一条路径不会经过树边，也就是
                                    ans=y*(n-1)
                            2、菊花图，一定会经过一条树边，其他的边都可以经过完全图边， ans=x+y*(n-2)
                            (判断菊花图找度为 n-1 的即可)
    x=y ans=x*(n-1)

    生成树边x < 完全图边y : 1、尽可能地找生成树的边，另有一条性质，度最多为2，那么直接贪心计算就可以了！只要一条合法的树边没有被选，贪心选上即可。 
                                    ans=stick*x+(n-stick-1)*y

*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#include<vector>
#define int long long
#define ZPL return
#define AK 0
#define IOI ;
using namespace std;
const int N=2e5+9;
struct node{
    int last;
    int to;
    int dis;
}e[N<<1];
int head[N];
int cnt;
int f[N][3];
int ans;
int ind[N];
int stick;//选择的树边 
int n,x,y;//x生成树，y完全图上 
int read()
{
    int f=1,x=0;
    char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s^'0');s=getchar();}
    return f*x;
}
void add(int from,int to,int dis)
{
    e[++cnt].last=head[from];
    e[cnt].to=to;
    e[cnt].dis=dis;
    head[from]=cnt;
}
bool dfs(int u,int fa)
{
    int du=2;//度最多为2
    for(int i=head[u];i;i=e[i].last)
    {
        int v=e[i].to;
        if(v==fa) continue;
        if(dfs(v,u)&&du)//可以使用树边！ 
        {
            du--;
            stick++;
        }
    }
    if(du>0) return true;
    else return false; 
}
void work()
{
    dfs(1,0);
    cout<<stick*x+(n-stick-1)*y<<endl;
    return;
}
signed main()
{
    n=read();
    x=read();//生成树边 
    y=read();//完全图边 
    bool flag=false;
    for(int i=1;i<n;i++)
    {
        int u=read();
        int v=read();
        add(u,v,x);
        add(v,u,x);
        ind[v]++;
        ind[u]++;
        if(ind[v]==n-1||ind[u]==n-1)
            flag=true;  
    }
    if(flag&&x>y)
    {
        cout<<x+(n-2)*y<<endl;
        return 0;
    }
    if(x>y)
    {
        cout<<(n-1)*y<<endl;
        return 0;
    }
    if(x==y)
    {
        cout<<(n-1)*y<<endl;
        return 0;
    }
    work();
    ZPL AK IOI 
}