次小生成树
最小生成树有kruskal算法，那么我们如何求出次小生成树呢?先跑一边最小生成树，然后依次选择一条最小生成树中的边并删除，在新的图里跑最小生成树。将所有删除一条边的图全部跑完最小生成树后，选取最小的那个长度和就是次小生成树的路径长度和。#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=102;
const int INF=1<<30;
struct edge
{
int fr,to,w,nxt;
//int samee;
bool deleted,inmst;
bool operator < (const edge &a) const {
return w<a.w;
}
};
int pre,n,m,head,cnt,tmp=0;
edge e;
void add(int fr,int to,int w)
{
e.fr=fr;
e.to=to;
e.w=w;
e.nxt=head;
e.deleted = false;
e.inmst=false;
head=cnt++;
}
int fin(int x)
{
if(x==pre)
return x;
return pre=fin(pre);
}
int Kruskal1()
{
for(int i=1;i<=n;++i)
pre=i;
sort(e,e+2*m);
int ans=0;
for(int i=0;i<cnt;++i)
{
//if (e.deleted == true){continue;}
int u=fin(e.fr);
int v=fin(e.to);
if(u!=v)
{
ans+=e.w;
e.inmst=true;
//tmp++;
pre=v;
}
}
return ans;
}
int Kruskal2()
{
for(int i=1;i<=n;++i)
pre=i;
sort(e,e+cnt);
int ans=0;
for(int i=0;i<cnt;++i)
{
if (e.deleted == true){/*cout << 1 <<endl;*/continue;}
int u=fin(e.fr);
int v=fin(e.to);
// cout << e.deleted << endl;
if(u!=v)
{
ans+=e.w;
//e.inmst=true;
pre=v;
}
}
return ans;
}
int main()
{
int a,b,c;
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
//while(scanf("%d",&n)&&n)
//{
cnt=0;
//int m=n*(n-1)/2;
memset(head,-1,sizeof(head));
for (int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
/* int gg;
// gg=e[cnt
e.samee=cnt-2;
e.samee=cnt-1;
printf("%d %d\n",e.samee,e.samee);*/
}
printf("%d ",Kruskal1());
//cout << cnt << endl;
int smst = 999999999;
for (int i=0;i<cnt;i++)
{
if (e.inmst==true)
{
e.deleted = true;
e.deleted=true;
//cout << smst << endl;
smst=min(smst,Kruskal2());
e.deleted= false;
e.deleted = false;
}
}
printf("%d\n",smst);
}
return 0;
}
这个代码可能有问题，但是思路是对的。
页:
[1]