帮公司做网站运营/关键词优化外包服务

这题我下载出来输入的数据，有好多都是重复边。。。很难受，想不到合适的解法了，

我就直接按照不重复来做了

多次运用最小生成树（kruskal）求解

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int father[50+5];int n,m;
double mi=10000000;
struct node{int x,y,len;double v;
};
node n1[1200];
int find(int x){if(x==father[x]) return x;return father[x]=find(father[x]);
}
bool cmp(node n1,node n2){return n1.len<n2.len;
}
bool cmp2(node n1,node n2){return n1.v<n2.v;
}
void kruskal(int sum){for(int i=1;i<=n;i++)  father[i]=i;double avg=1.0*sum/(n-1);//已知sum可以求得平均值for(int i=0;i<m;i++)n1[i].v=1.0*(n1[i].len-avg)*(n1[i].len-avg);//每个边权的数-avg的平方也就能求出来sort(n1,n1+m,cmp2);//根据数-avg的平方排序double sum2=0;int sum3=0,cou=0;for(int i=0;i<m;i++){//kruskal算法int a=find(n1[i].x),b=find(n1[i].y);if(a==b) continue;father[a]=b;cou++;sum2+=n1[i].v;sum3+=n1[i].len;//每次用到的权值都相加if(cou==n-1)  break;}if(sum3==sum){//要注意的是sum只是我们假设已知的，并不一定是存在的，所以要判断一下if(sum2<mi)  mi=sum2;}
}
int main(){int co=0;while(cin>>n>>m){if(n==0||m==0)  break;	mi=10000000;for(int i=0;i<m;i++){cin>>n1[i].x>>n1[i].y>>n1[i].len;}sort(n1,n1+m,cmp);int mmin=0,mmax=0;//排序之后n-1个权值能组成的最大值和最小值for(int i=0;i<n-1;i++){mmin+=n1[i].len;}for(int i=m-1;i>m-n;i--){mmax+=n1[i].len;}for(int i=mmin;i<=mmax;i++){//假设我们已经知道了sum,就是ikruskal(i);}printf("Case %d: %.2f\n",++co,1.0*mi/(n-1));}return 0;
}