题目大意: 给出一个无向图(不一定连通)
求连通所有点，从一顶点可以到任何顶点的路线
并且这条路线总长度减去两倍最长线段的值最小
也就是求总长度减去最长边的值最小的生成树
解题思路: 先把问题简化一下:
最小生成树总长度 — 最长边*2＝n-1个顶点的生成树 — 最长边
使得上式的值最小，既使得左边的值最小，右边值最大！
开始想到的是删除一个点，求n-1个点的最小生成树
然后再找删除那个点连接这个生成树最长的边，WA了
证明:
删除一个点之后，有可能不存在n－1个点的生成树.
5 6
1 2 2
2 3 2
3 4 2
3 5 2
2 5 3
2 4 3
如，删除顶点2之后，顶点1就成了孤立点
正确的做法:
先将边从小到大排序，枚举每个顶点的最长的边
每个顶点总会有连接它的最长边,然后再找出其他n-1个点的最小生成树！
很容易证明到n-1个点的最小生成树的总长度肯定有下界 (最小值)
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 2101
#define MAX_2 1000000
#define INF 0x3f3f3f3f
typedef struct snode{
int x;
int y;
int s;
}span;
int father[MAX];
span spantree[MAX_2];
span longth[MAX];
int comp(const void *a,const void *b)
{
span *pa=(span *)a;
span *pb=(span *)b;
return (pa->s)-(pb->s);
}
void Empty(int n) //并查集初始化
{
int i;
for(i=1;i<=n;i++)
{
father[i]=i;
}
}
int Find(int x)
{
int s,j;
s=x;
while(x!=father[x])
{
x=father[x];
}
while(s!=x)
{
j=father[s];
father[s]=x;
s=j;
}
return x;
}
void Union(int R1,int R2)
{
int r1,r2;
r1=Find(R1);
r2=Find(R2);
if(r1!=r2)
{
father[r1]=r2;
}
}
int main ()
{
int temp,t,n,m,i,j,min,pd,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(longth,0,sizeof(longth));
for(j=0;j<m;j++)
{
scanf("%d%d%d",&spantree[j].x,&spantree[j].y,&spantree[j].s);
if(spantree[j].s>longth[spantree[j].x].s) //找出每个顶点连接的最长边
{
longth[spantree[j].x].s=spantree[j].s;
longth[spantree[j].x].x=spantree[j].x;
longth[spantree[j].x].y=spantree[j].y;
}
if(spantree[j].s>longth[spantree[j].y].s) //找出每个顶点连接的最长边
{
longth[spantree[j].y].s=spantree[j].s;
longth[spantree[j].y].x=spantree[j].y;
longth[spantree[j].y].y=spantree[j].x;
}
}
qsort(spantree,m,sizeof(spantree[0]),comp); //边从小到大排序
Empty(n);
for(i=0;i<m;i++)
{
if(Find(spantree[i].x)!=Find(spantree[i].y))
{
Union(spantree[i].x,spantree[i].y);
}
}
for(i=1,pd=1;i<n;i++)
{
if(Find(father[i])!=Find(father[i+1])) //如果图不连通，打印"disconnected"
{
pd=0;
break;
}
}
if(pd)
{
for(j=1,min=INF;j<=n;j++) //枚举n次，每次取i顶点的最长边
{
a=longth[j].x;
b=longth[j].y;
Empty(n);
Union(a,b);
temp=-(longth[j].s); //i顶点的最长边
for(i=0,t=1;i<m;i++)
{
if(t==n-1) //生成树已有n－1个顶点则退出
break;
if(Find(spantree[i].x)!=Find(spantree[i].y))
{
Union(spantree[i].x,spantree[i].y);
t++;
temp+=spantree[i].s;
}
}
if(min>temp)
min=temp;
}
printf("%d\n",min);
}
else
printf("disconnected\n");
}
return 0;
}
注：原创文章，转载请注明出处