首页 > 代码库 > POJ1679 The Unique MST 生成树+DFS
POJ1679 The Unique MST 生成树+DFS
题意：求一个无向图的最小生成树与次小生成树的边权和是否相等
题解：
首先有一个性质，就是最小生成树上的任意两点的距离就是其在原图中的最短路，严格的证明我不会- -，但是由于Prim Dijkstra算法的过程完全相同，所以这个性质比较显然（不会证就不会证呗为何还要找理由QAQ）
还要一条性质就是无向MST上加入一条边一定会形成一个环，因此我们可以枚举加入一条不在MST上的边e，然后删除MST上形成的环中除e之外的最长的一条边，得到了一个新的最小生成树，由于e一定大于等于删除的那条边，因此得到的新的生成树也一定大于等于MST，因此枚举出的最小的生成树就是次小生成树了。
当然实际操作的时候并不需要每次都找一边最长的边，我们先把MST给存下来，然后DFS出MST上任意两点(i,j)路径上的最长边f[i][j]，然后枚举的过程中的新的生成树的长度就是dist_MST+w(u,v)-f[u][v]
#include <queue>#include <vector>#include <functional>#include <cstdio>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int MAXN=100+2;const int MAXM=10000+2;struct HASH{ int u,w; HASH *next; HASH(){} HASH(int _u,int _w,HASH *_next):u(_u),w(_w),next(_next){}}*table[MAXN],mem[2*MAXM],*table_MST[MAXN],mem_MST[2*MAXM];struct NODE{ int u,v,w; NODE(){} NODE(int _u,int _v,int _w):u(_u),v(_v),w(_w){} friend bool operator<(NODE a,NODE b){ return a.w>b.w;}};int T,N,M,dist,d[MAXN],e[MAXN][MAXN],cnt;bool flag[MAXN],mark[MAXN][MAXN];priority_queue<NODE> q;void Insert(int u,int v,int w){ table[u]=&(mem[cnt++]=HASH(v,w,table[u]));}void Insert_MST(int u,int v,int w){ table_MST[u]=&(mem_MST[cnt++]=HASH(v,w,table_MST[u]));}int Prim(){ int ret=0; memset(d,0X7F,sizeof(d)); d[1]=0,q.push(NODE(0,1,0)); NODE x; while(!q.empty()){ x=q.top(),q.pop(); if(flag[x.v]) continue; flag[x.v]=1; ret+=x.w; if(x.u) mark[x.u][x.v]=mark[x.v][x.u]=1,Insert_MST(x.u,x.v,x.w),Insert_MST(x.v,x.u,x.w); for(HASH *p=table[x.v];p;p=p->next) if(d[p->u]>p->w) d[p->u]=p->w,q.push(NODE(x.v,p->u,p->w)); } return ret;}void DFS(int u,int w,int f,int b){ for(HASH *p=table_MST[u];p;p=p->next) if(p->u!=f) e[b][p->u]=max(w,p->w),DFS(p->u,max(w,p->w),u,b);}int main(){ cin >> T; while(T--){ cnt=dist=0; memset(e,0,sizeof(e)); memset(mark,0,sizeof(mark)); memset(flag,0,sizeof(flag)); memset(table,0,sizeof(table)); memset(table_MST,0,sizeof(table_MST)); cin >> N >> M; for(int i=1,u,v,w;i<=M;i++){ cin >> u >> v >> w; Insert(u,v,w),Insert(v,u,w); } cnt=0,dist=Prim(); for(int i=1;i<=N;i++) DFS(i,0,0,i); for(int i=1;i<=N;i++) for(HASH *p=table[i];p;p=p->next) if(!mark[i][p->u] && p->w==e[i][p->u]){ flag[0]=1; break; } if(flag[0]) cout << "Not Unique!" << endl; else cout << dist << endl; } return 0;}
POJ1679 The Unique MST 生成树+DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。