题目大意: 给出一个无向图(不一定连通)
求连通所有点,从一顶点可以到任何顶点的路线
并且这条路线总长度减去两倍最长线段的值最小
也就是求总长度减去最长边的值最小的生成树
解题思路: 先把问题简化一下:
最小生成树总长度 — 最长边*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; }
注:原创文章,转载请注明出处