POJ 1679 次小生成树裸题

题意：

给定n个点m条无向带权边的图

问：是否最小生成树唯一

是则输出最小生成树的权值

思路：

求出次小生成树，判断权值是否于最小生成树相同即可。

dp[u][v] 表示在最小生成树下 [u,v] 路径中最大的边权值

每次BFS求出u点距离其他点的 路径上的最大边权值。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define N 105 #define M 100005 #define inf 1000000 struct Edge{ int from, to, dis, yes; bool operator<(const Edge&a)const{ return a.dis>dis; } }edge[M]; vector
        
         G[N]; int f[N]; int find(int x){return x==f[x]   x : f[x] = find(f[x]);} bool Union(int x, int y){ int fx = find(x), fy = find(y); if(fx == fy)return true; if(fx
         
          q; q.push(node(0, x,-1)); while(!q.empty()){ node u = q.front(); q.pop(); for(int i = 0; i < G[u.to].size(); i++){ int v = G[u.to][i]; if(v == u.fa)continue; int nowmax = max(dis[u.to][v], u.maxdis); dp[x][v] = dp[v][x] = max(dp[x][v], nowmax); q.push(node(nowmax, v, u.to)); } } } void init(){ memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { G[i].clear(), f[i] = i; for(int j = 1; j <= n; j++)dis[i][j] = inf; dis[i][i] = 0; } } int main(){ int T, u, v, i, j;scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); init(); for(i = 0; i < m; i++) { scanf("%d%d%d",&edge[i].from, &edge[i].to, &edge[i].dis); u = edge[i].from, v = edge[i].to; edge[i].yes = false; } int mindis = Kru(); for(i = 1; i <= n; i++) BFS(i); int ans = inf; for(i = 0; i < m; i++)if(!edge[i].yes) { int u = edge[i].from, v = edge[i].to; ans = min(ans, mindis + edge[i].dis - dp[u][v]); } if(ans == mindis)puts("Not Unique!"); else printf("%d\n", mindis); } return 0; } /* 99 3 3 1 2 2 2 3 3 3 1 3 3 3 1 2 3 2 3 2 3 1 3 3 2 1 2 2 2 3 2 */