CodeForces 618D Hamiltonian Spanning Tree

题意：要把所有的节点都访问一次，并且不能重复访问，有两种方式访问，一种是根据树上的路径

走和当前节点连接的下一个节点cost x, 或者可以不走树上边，直接跳到不与当前节点连接的节点，cost y

分析：

别被树吓着！

一定会走n-1条路，那么就是有一些走树上的边，有一些不走。

如果树上的路径cost更大(x >= y)，那么尽可能的不走树上的路径，那么根据尝试可以找到规律

如果有一个节点是所有节点的父节点，也就是说这个节点的度为n-1，那么只会走一个x其他都是y

如果没有这个节点，一定可以全部走y

另一种情况如果（x < y），那么也就是说要尽可能的多走树上的边，我们知道一个节点只能访问一次，也就是说

一个节点最多只能连两条边出去，然后dfs搜索，找到最多可以走多少条，每个节点的度数如果不被剪完就可以继续连，

剩下的只能走y。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <queue>

 #include <vector>

 #include <algorithm>

 #include <stack>

 #include <set>

 #include <map>

 #include <math.h>

 #define pb push_back

 #define CLR(a) memset(a, 0, sizeof(a));

 #define MEM(a, b) memset(a, b, sizeof(a));

 #define fi first

 #define se second

 using namespace std;

 typedef long long ll;

 const int MAXN = ;

 const int MAXV = ;

 const int MAXE = ;

 const int INF = 0x3f3f3f3f;

 ll x, y, n;

 struct Edge

 {

     int to, next;

     Edge () {}

     Edge(int to, int next) : to(to), next(next) {}

 }edge[MAXN << ];

 int num;

 int head[MAXN];

 void Add(int from, int to)

 {

     edge[num] = Edge(to, head[from]);

     head[from] = num++;

 }

 int deg[MAXN];

 ll ans = ;

 ll len = ;

 int cnt = ;

 bool dfs(int crt, int fa)

 {

     int rem = ;

     for (int t = head[crt]; t != -; t = edge[t].next)

     {

         Edge e = edge[t];

         int v = e.to;

         if (v == fa) continue;

         if (dfs(v, crt) && rem > )

         {

             len++; rem--;

         }

     }

     return rem > ;

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     while (~scanf("%lld%lld%lld", &n, &x, &y))

     {

         MEM(head, -);

         MEM(edge, -);

         CLR(deg);

         num = ;

         len = ;

         for (int i = ; i < n-; i++)

         {

             int u, v;

             scanf("%d%d", &u, &v);

             Add(u, v);

             Add(v, u);

             deg[u]++;

             deg[v]++;

         }

         bool done = false;

         if (x >= y)

         {

             for (int i = ; i <= n; i++)

             {

                 if (deg[i] == n-)

                 {

                     ans = y*(n-)+x;

                     printf("%lld\n", ans);

                     done = true;

                     break;

                 }

             }

             if (done) continue;

             ans = (n-)*y;

             printf("%lld\n", ans);

             continue;

         }

         dfs(, ); ans = len*x + (n--len)*y;

         printf("%lld\n", ans);

     }

     return ;

 }

巴特西

CodeForces 618D Hamiltonian Spanning Tree

最新文章

热门文章