POJ 1679 判断最小树是否唯一

题意：

给你一个图，问你最小树是否唯一，唯一则输出最小数的权值，不唯一输出Not Unique!

思路：

题目问的是最小树是否唯一，其实也就是在问次小树是否等于最小树，如果等于则不唯一，求次小树快的方法应该是先求最小树，然后枚举删除最小树上的边，最快的应该是树形dp优化的那个吧，刚刚忘记了，直接求出最小树，然后暴力深搜分成两个集合枚举，0ms AC，因为点才100，所以暴力也无压力。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define N_node 100 + 10

#define N_edge 20000 + 100

#define INF 1000000000

using namespace std;

typedef struct

{

   int to ,next ,cost;

}STAR;

typedef struct

{

   int a ,b ,c;

}EDGE;

STAR E[N_edge];

EDGE edge[N_edge] ,Tree[N_node];

int list[N_node] ,tot;

int mer[N_node];

int mark[N_node];

int map[N_node][N_node];

int node_l[N_node] ,node_r[N_node];

int ll ,rr;

void add(int a ,int b)

{

    E[++tot].to = b;

    E[tot].next = list[a];

    list[a] = tot;

    E[++tot].to = a;

    E[tot].next = list[b];

    list[b] = tot;

}

bool camp(EDGE a ,EDGE b)

{

     return a.c < b.c;

}

int finds(int x)

{

    return x == mer[x] ? x : mer[x] = finds(mer[x]);

}

void DFS1(int s)

{

   node_l[++ll] = s;

   for(int k = list[s] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      if(mark[to]) continue;

      mark[to] = 1;

      DFS1(to);

   }

}

void DFS2(int s)

{

   node_r[++rr] = s;

   for(int k = list[s] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      if(mark[to]) continue;

      mark[to] = 1;

      DFS2(to);

   }

}

int minn(int x ,int y)

{

     return x < y ? x : y;

} 

int main ()

{

   int t ,n ,m ,i ,j;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d %d" ,&n ,&m);

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

      for(j = 1 ;j <= n ;j ++)

      map[i][j] = INF;

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);

         map[edge[i].a][edge[i].b] = map[edge[i].b][edge[i].a] = edge[i].c;

      }

      sort(edge + 1 ,edge + m + 1 ,camp);

      int sum = 0;

      for(i = 1 ;i <= n ;i ++) mer[i] = i;

      memset(list ,0 ,sizeof(list)) ,tot = 1;

      int tt = 0;

      for(i = 1 ;i <= m ;i ++)

      {

         int x = finds(edge[i].a);

         int y = finds(edge[i].b);

         if(x == y) continue;

         mer[x] = y;

         sum += edge[i].c;

         add(edge[i].a ,edge[i].b);

         Tree[++tt].a = edge[i].a;

         Tree[tt].b = edge[i].b;

         Tree[tt].c=  edge[i].c;

      }

      int now = 1000000000;

      for(i = 1 ;i <= tt ;i ++)

      {

         int a = Tree[i].a;

         int b = Tree[i].b;

         int c = Tree[i].c;

         memset(mark ,0 ,sizeof(mark));

         mark[a] = mark[b] = 1;

         ll = 0;

         DFS1(a);

         rr = 0;

         DFS2(b);

         for(int ii = 1 ;ii <= ll ;ii ++)

         for(int jj = 1 ;jj <= rr ;jj ++)

         {

            int aa = node_l[ii];

            int bb = node_r[jj];

            if(map[aa][bb] == INF || aa == a && bb == b || aa == b && bb == a) continue;

            now = minn(now ,sum - c + map[aa][bb]);

         }

      }

      if(now != sum) printf("%d\n" ,sum);

      else printf("Not Unique!\n");

   }

   return 0;

}

巴特西

POJ 1679 判断最小树是否唯一

最新文章

热门文章