題意：
? ? ?判斷最小樹是否唯一。
思路：
? ? ?我用了兩種方法，主要就是好久沒敲了，找個水題練練手，第一種就是先一遍最小生成樹，然后枚舉最小生成樹上的每一條邊，然后取消這條邊，在跑一遍最小生成樹，就這樣一直跑最小生成樹，如果找到了一顆和之前的那個一樣的，那么就是不唯一，第二種方法也是先最小樹，然后枚舉，在枚舉的時候不是繼續重新跑，而是斷開當前邊，把樹分成兩個集合<兩次深搜實現>，然后在枚舉這連個集合之間是否可以找到一個可以代替當前枚舉的最小樹的邊，實現復雜度的話應該是第二種快點，但理論上也快不多少，只是為了練練手，在多說一句，第二種方法和求次小樹的思路有點像，但是次小樹可以再這個上面進行dp優化，其實這個題目也可以直接判斷次小樹是否等于最小樹。好像有點說多了。




#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 110


using namespace std;


typedef struct
{
? ?int x ,y ,c;
}EDGE;


EDGE edge[N*N];
int ?mer[N] ,mst[N];


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


bool camp(EDGE a ,EDGE b)
{
? ?return a.c < b.c;
}


int MST(int n ,int m ,int co)
{
? ?for(int i = 1 ;i <= n ;i ++)mer[i] = i;
? ?int Ans = 0 ,sum = 0;
? ?for(int i = 1 ;i <= m ;i ++)
? ?{
? ? ? if(i == co) continue;
? ? ? int xx = finds(edge[i].x);
? ? ? int yy = finds(edge[i].y);
? ? ? if(xx != yy)?
? ? ? {
? ? ? ? ?Ans += edge[i].c ,sum ++ ;
? ? ? ? ?mer[xx] = yy;
? ? ? ? ?if(co == -1) mst[sum] = i;
? ? ? }
? ? ? if(sum == n - 1) break;
? ?}
? ?return Ans;
}?
? ?


int main ()
{
? ?int t ,i ,n ,m;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? scanf("%d %d %d" ,&edge[i].x ,&edge[i].y ,&edge[i].c);
? ? ? sort(edge + 1 ,edge + m + 1 ,camp);
? ? ? int Ans = MST(n ,m ,-1);
? ? ? for(i = 1 ;i < n ;i ++)
? ? ? {
? ? ? ? ?int tmp = MST(n ,m ,mst[i]);
? ? ? ? ?if(Ans == tmp) break;
? ? ? }
? ? ? i == n || m == n - 1? printf("%d\n" ,Ans) : puts("Not Unique!");
? ?}
? ?return 0;
}
? ? ??
? ? ?
? ? ??
? ? ??
? ? ??
? ?
#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 110


using namespace std;


typedef struct
{
? ?int x ,y ,c;
}EDGE;


typedef struct
{
? ?int to ,next;
}STAR;


EDGE edge[N*N];
STAR E[N*N];
int ?map[N][N] ,mer[N] ,mark[N];
int list[N] ,tot ,mst[N];
int L[N] ,R[N] ,ll ,rr;


void add(int a, int b)
{
? ?E[++tot].to = b;
? ?E[tot].next = list[a];
? ?list[a] = tot;
}


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


int minn(int x ,int y)
{
? ?return x < y ? x : y;
}


bool camp(EDGE a ,EDGE b)
{
? ?return a.c < b.c;
}


int MST(int n ,int m)
{
? ?for(int i = 1 ;i <= n ;i ++) mer[i] = i;
? ?int Ans = 0 ,sum = 0;
? ?memset(list ,0 ,sizeof(list)) ,tot = 1;
? ?for(int i = 1 ;i <= m ;i ++)
? ?{
? ? ? int xx = finds(edge[i].x);
? ? ? int yy = finds(edge[i].y);
? ? ? if(xx != yy)?
? ? ? {
? ? ? ? ?Ans += edge[i].c ,sum ++;
? ? ? ? ?mer[xx] = yy;
? ? ? ? ?mst[sum] = i;
? ? ? ? ?add(edge[i].x ,edge[i].y);
? ? ? ? ?add(edge[i].y ,edge[i].x);
? ? ? }
? ? ? if(sum == n - 1) break;
? ?}
? ?return Ans;
}


void DFS1(int x)
{
? ?for(int k = list[x] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(mark[to]) continue;
? ? ? mark[to] = 1;
? ? ? L[++ll] = to;
? ? ? DFS1(to);
? ?}
}


void DFS2(int x)
{
? ?for(int k = list[x] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(mark[to]) continue;
? ? ? mark[to] = 1;
? ? ? R[++rr] = to;
? ? ? DFS2(to);
? ?}
}




int main ()
{
? ?int t ,n ,m ,i ,j ,mk;
? ?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] = 100000000;
? ? ? ?for(i = 1 ;i <= m ;i ++)
? ? ? ?{
? ? ? ? ? scanf("%d %d %d" ,&edge[i].x ,&edge[i].y ,&edge[i].c);?
? ? ? ? ? int x = edge[i].x ,y = edge[i].y;
? ? ? ? ? map[x][y] = map[y][x] = minn(map[x][y] ,edge[i].c);
? ? ? }
? ? ? sort(edge + 1 ,edge + m + 1 ,camp);
? ? ? int Ans = MST(n ,m);
? ? ? if(m == n - 1)
? ? ? {
? ? ? ? ?printf("%d\n" ,Ans);
? ? ? ? ?continue;
? ? ? }
? ? ? mk = 0;
? ? ? for(i = 1 ;i < n && !mk;i ++)
? ? ? {
? ? ? ? ?memset(mark ,0 ,sizeof(mark));
? ? ? ? ?int l = edge[mst[i]].x ,r = edge[mst[i]].y;
? ? ? ? ?mark[l] = mark[r] = 1;
? ? ? ? ?ll = rr = 0;
? ? ? ? ?L[++ll] = l ,R[++rr] = r; ? ?
? ? ? ? ?DFS1(l) ,DFS2(r);
? ? ? ? ?for(int j = 1 ;j <= ll && !mk;j ++)
? ? ? ? ?{
? ? ? ? ? ? for(int k = 1 ;k <= rr && !mk ;k ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ?if(L[j] == edge[mst[i]].x && R[k] == edge[mst[i]].y || L[j] == edge[mst[i]].y && R[k] == edge[mst[i]].x)
? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ?if(map[L[j]][R[k]] == edge[mst[i]].c) mk = 1;
? ? ? ? ? ? }
? ? ? ? ?}
? ? ? }
? ? ? mk ? printf("Not Unique!\n"): printf("%d\n" ,Ans);
? ?}
? ?return 0;
}
? ? ? ? ?
? ? ??
? ?
? ?
? ?
? ?
? ?
? ?




? ?
? ?
? ?
? ?






















?
? ?















《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的POJ1679判断最小生成树的唯一性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。