http://poj.org/problem?id=167 9
問最小生成樹是否唯一 ? ?其實就是問次小生成樹是否等于最小生成樹
思路：
1 ?Kruskal 求最小生成樹MIN 記錄哪些邊用了 哪些沒有用 并建樹
2 ?dfs 從每一點開始 求最小生成樹上任意兩點間的最長邊
3 枚舉沒用過的邊加入的情況 取(MIN+此邊權-樹中此兩點間最長邊權) ?最小的那一個就是次小生成樹
代碼及其注釋：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<cmath>
#define LL long long
using namespace std;
const int N=105;
struct node
{
struct tt *next;
}mem[N];
struct tt
{
int j,k;
struct tt *next;
};
struct ss
{
bool used;
int i,j,d;
}side[N*N];
int Mi_j[N][N];
int f[N];
void build(int i,int j,int d)//建樹
{
struct tt *t=new tt;
t->j=j;
t->k=d;
t->next=mem[i].next;
mem[i].next=t;
}
void Dele(int n)//刪樹
{
for(int i=1;i<=n;++i)
mem[i].next=NULL;
}
inline int findx(int x)//并查集
{
if(f[x]!=x)
f[x]=findx(f[x]);
return f[x];
}
int Kruskal(int n,int m)//求最小生成樹
{
int sum=0;
for(int i=1;i<=n;++i)
f[i]=i;
for(int l=0;l<m;++l)
{
int x=side[l].i;
int y=side[l].j;
if(findx(x)!=findx(y))
{
build(x,y,side[l].d);//建樹
build(y,x,side[l].d);
f[findx(x)]=y;
sum+=side[l].d;
side[l].used=true;//標記是否用過
}
}
return sum;
}
void dfs(int st,int x,int pre,int M)
{
if(M!=0)
Mi_j[st][x]=max(Mi_j[st][x],M);//求st到x最長邊權
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
dfs(st,t->j,x,max(M,t->k));
}
t=t->next;
}
}
int Fmtree(int n,int m,int MIN)
{
int mtree=MIN+1;
memset(Mi_j,0,sizeof(Mi_j));
for(int i=1;i<=n;++i)
dfs(i,i,0,0);//求樹中任意兩點間的最長邊權
for(int l=0;l<m;++l)
{
if(side[l].used==true)
continue;
int x=side[l].i;
int y=side[l].j;
mtree=min(mtree,MIN+side[l].d-Mi_j[x][y]);//枚舉
}
return mtree;
}
int main()
{
//freopen("data.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;++i)
{
scanf("%d %d %d",&side[i].i,&side[i].j,&side[i].d);
side[i].used=false;
}
int MIN=Kruskal(n,m);
if(MIN==Fmtree(n,m,MIN))
printf("Not Unique!\n");
else
printf("%d\n",MIN);
Dele(n);
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
