【 算法提高 最小方差生成树 】（MST，据说。。 没对）

【 算法提高 最小方差生成树 】（MST，据说。。 没对）

时间限制：1.0s 内存限制：256.0MB 问题描述 给定带权无向图，求出一颗方差最小的生成树。 输入格式 输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。n=m=0标志着测试文件的结束。 输出格式 对于每组数据，输出最小方差，四舍五入到0.01。输出格式按照样例。 样例输入 4 5 1 2 1 2 3 2 3 4 2 4 1 1 2 4 3 4 6 1 2 1 2 3 2 3 4 3 4 1 1 2 4 3 1 3 3 0 0 样例输出 Case 1: 0.22 Case 2: 0.00 数据规模与约定 1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。数据不超过5组。 分析： 很清楚的一道MST题目，然后上来就敲。 就直接写了个板子。 但是WA了，一组没过。 再看题，最小方差生成树，应该是方差，所以 应该枚举平均值（枚举，这里是因为要求的是最小方差生成树），求方差。 然后，照着这样写一遍，还是WA，过了1组，或者过了5组数据。 百度。。 貌似没看到能100分的代码，要么说 官网数据有问题，要么说有重边，但是改了之后还是WA。。。 【10分】。。 #include using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) #define memc(a,b) memcpy(a,b,sizeof(b)) #define rep(i,a,n) for(int i=a;i=a;i--)///[n,a] #define pb push_back #define fi first #define se second #define IO ios::sync_with_stdio(false) #define fre freopen("in.txt","r",stdin) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; typedef unsigned long long ull; const double PI=acos(-1.0); const double E=2.718281828459045; const double eps=1e-3; const int INF=0x3f3f3f3f; const double dinf=0x3f3f3f3f+1.0; const int MOD=1e8+7; const int N=1e3+5; const ll maxn=1e6+5; const int dir[4][2]= {-1,0,1,0,0,-1,0,1}; struct Node { int u,v; double w;///方差 double val;///边权 bool operator < (const Node& m)const { return w>n>>m&&n&&m) { int maxx=0,minx=0; rep(i,0,m) { cin>>a[i].u>>a[i].v>>a[i].val; p[i]=a[i].val; } ans=dinf; sort(p,p+m); for(int i=0; im-n; i--) maxx+=p[i]; for(int i=minx; i<=maxx; i++) { kruskal(i); } printf("Case %d: %.2f\n",++cas,ans/(n-1)); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。