描述
xiaomengxian的哥哥是一个游戏迷，他喜欢研究各种游戏。这天，xiaomengxian到他家玩，他便拿出了自己最近正在研究的一个游戏给xiaomengxian看。这个游戏是这样的：一个国家有N个城市，有些城市之间可以建设铁路，并且不同城市之间建设铁路的费用各不相同。问如何用最小的费用，使整个国家的各个城市之间能够互相到达。另外，铁路是双向的。xiaomengxian心想，这不是太简单了吗？这就是经典的MST问题。他的哥哥说，这个当然不算什么。关键是它还要求费用第二小的方案，这真是让人伤脑筋。xiaomengxian想了很久，也没有想出来，你能帮助他吗？ 费用第二小的方案的定义为：与费用最小的方案不完全相同，且费用值除费用最小的方案外最小。
输入
第一行两个数N（2<=N<=500），M，分别表示国家的城市数和可以修建铁路的城市有多少对。
接下来M行，每行三个正整数Ai，Bi，Ci，表示城市Ai和Bi之间可以修建铁路，费用为Ci。
输出
第一行：”Cost: “+一个整数，表示最小费用。（若不存在，输出-1）
第二行：”Cost: “+一个整数，表示第二小费用。（若不存在，输出-1）
样例输入
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1
输入样例2：
3 2
1 2 2
2 3 2
样例输出
Cost: 4
Cost: 4
输出样例2：
Cost: 4
Cost: -1
代码
prime
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],minc[N],fa[N],maxd[N][N];
bool con[N][N],vis[N];
int n,m;
int prime()
{
memset(maxd,0,sizeof(maxd));
memset(vis,false,sizeof(vis));
memset(con,false,sizeof(con));
int ans=0;
for(int i=1;i<=n;i++)
{
minc[i]=g[1][i],fa[i]=1;
}
vis[1]=1;
for(int i=1;i<n;i++)
{
int mi=0x3f3f3f3f,k=0;
for(int j=2;j<=n;j++)
if(!vis[j]&&minc[j]<mi)
mi=minc[j],k=j;
if(k==0) return -1;
vis[k]=1;
con[k][fa[k]]=con[fa[k]][k]=true;
ans+=mi;
maxd[fa[k]][k]=maxd[k][fa[k]]=mi;
for(int j=1;j<=n;j++)
{
if(j!=k&&vis[j])
maxd[k][j]=maxd[j][k]=max(maxd[j][fa[k]],minc[k]);
if(!vis[j]&&g[k][j]<minc[j])
{
minc[j]=g[k][j];
fa[j]=k;
}
}
}
return ans;
}
int main()
{
// freopen("soc.cpp","r",stdin);
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof(g));
for(int i=1,a,b,c;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=c;
}
int ans=prime();
printf("Cost: %d\n",ans);
if(ans==-1){printf("Cost: -1");return 0;}
int tmp=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j||g[i][j]==0x3f3f3f3f) continue;
if(!con[i][j]) tmp=min(tmp,ans-maxd[i][j]+g[i][j]);
}
}
if(tmp==0x3f3f3f3f) printf("Cost: -1");
else printf("Cost: %d",tmp);
}
Kruskal
#include<bits/stdc++.h>
#define N 500010
using namespace std;
inline int rd()
{
int data=0;int w=1;char ch=0;
ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar();
if(ch==‘-‘)w=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)data=(data<<3)+(data<<1)+ch-‘0‘,ch=getchar();
return data*w;
}
struct edge{
int u,v,w;
}e[N];
int n,m,i,j,ans,num,psum;
bool hash[N],bk;
int fa[N],E[N];
bool cmp(const edge a,const edge b)
{
return a.w<b.w;
}
int find(int x)
{
if (x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void kruscal()
{
int i,a,b;
for(i=1;i<=n;i++)fa[i]=i;
num=0;
for(i=1;i<=m;i++)
{
a=find(e[i].u);b=find(e[i].v);
if(a!=b){
fa[b]=a;ans+=e[i].w;
num++;E[num]=i;
if(num==n-1)
return;
}
}
}
void sec_kruscal()
{
int nnum=0,a,b,i1;
for(i1=1;i1<=n;i1++)fa[i1]=i1;
for(i1=1;i1<=m;i1++)
if(hash[i1])
{
a=find(e[i1].u);b=find(e[i1].v);
if(a!=b)
{
psum+=e[i1].w;fa[b]=a;
nnum++;
if(nnum==n-1)
{
bk=true;return;
}
}
}
}
int main()
{
n=rd();m=rd();
for(i=1;i<=m;i++)
{
e[i].u=rd();e[i].v=rd();e[i].w=rd();
}
sort(e+1,e+m+1,cmp);
ans=0;kruscal();
printf("Cost: %d\n",ans);
ans=0x7fffffff;
memset(hash,1,sizeof(hash));
for(i=1;i<=num;i++)
{
hash[E[i]]=0;psum=0;
bk=false;
sec_kruscal();
if(bk){
if(psum<ans)ans=psum;
}
hash[E[i]]=1;
}
if(ans==0x7fffffff)
printf("Cost: %d\n",-1);
else
printf("Cost: %d\n",ans);
return 0;
}