题意简述：给定若干个相同维度的向量，寻找一种排序方法，使得所有向量的表示长度总和最低。 所谓表示长度为（Aj-r*Ai）^2,其中i<j
数据范围：向量总数和维度均小于100
思路：（1）首先Ai和Aj确定后，最小表示长度是可以在线性时间计算出来的。使用简单的二次函数分析方法即可。
（2）上述可以得出任意两向量之间的距离，即为图中的边，于是问题可以转化为有向图的“最小树形图”，i到j的有向边权值即为用Aj表示Ai的最小表示长度。
（3）朱-刘算法简述： 首先对除根以外的点选择一条权值最小的边，如果没有构成环且没有孤立点则找到了答案。
如果存在环，则将环缩为一个新的点 然后更新所有的边权
设环中的点有（Vk1，Vk2，… ，Vki）总共i个，用缩成的点叫Vk替代，则在压缩后的图中，其他所有不在环中点v到Vk的距离定义如下：
gh[v][Vk]=min { gh[v][Vkj]-mincost[Vkj] } (1<=j<=i)//由于选择入边必然放弃Vkj之前选择的入边，所以要减去mincost[Vkj]
而Vk到v的距离为
gh[Vk][v]=min { gh[Vkj][v] } (1<=j<=i)
直到不存在环算法结束得到最优解。
(4)本题向量序列是任意的，所以对应生成树的根是不确定的，我们可以枚举根，但是复杂度太高。
此时我们引入一个 零向量 作为树根 显然任何向量由零向量表示的结果都是最差的，所以对其他的所有点直接运行朱刘算法就可以得到解了。
PS：这个题用cout输出会WE。。 必须用printf
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
using namespace std; struct edge
{
int begin;int end;
}; const int maxx=;
bool vis[maxx],indfs[maxx];
vector<double>zero;
int n,m,root;
vector<vector<double> >vec;
double cost[maxx][maxx],Cost[maxx][maxx];
bool operator <(const edge a,const edge b)
{
double ac=cost[a.begin][a.end];double bc=cost[b.begin][b.end];
return ac>bc;//从小到大排序
};
priority_queue<edge>que[maxx];
double minv(vector<double> a,vector<double> b)
{
double ab=,bsqrt=,asqrt=;
for(int i=;i<a.size();i++)
{ab+=a[i]*b[i];bsqrt+=b[i]*b[i];asqrt+=a[i]*a[i];} if((bsqrt-0.0)<1e-)return asqrt;
return asqrt-(ab*ab/bsqrt);
}
int belongcircle[maxx];
int findbelong(int x)
{
if(x==belongcircle[x])return x;
else return belongcircle[x]=findbelong(belongcircle[x]);
} double ans,ansnow;
double min(double a,double b)
{
if(a<b)return a;
else return b;
}
void combinecircle(int now,int begin)
{
now=findbelong(now);
if(vis[now])return ;
vis[now]=true;
edge e1=que[now].top();
double coste=cost[findbelong(e1.begin)][findbelong(e1.end)];
ansnow+=coste;
bool finish[maxx];
memset(finish,,sizeof(finish));
for(int i=;i<=m;i++)
{
int po=findbelong(i);
if(po==now||po==begin)continue;
if(finish[po])continue;
finish[po]=true;
cost[begin][po]=min(cost[begin][po],cost[now][po]-coste);
cost[po][begin]=min(cost[po][begin],cost[po][now]);
}
belongcircle[now]=begin;
combinecircle(e1.end,begin);
return ;
}
void build();
bool findcircle(int now)
{
if(now==root)return false;
now=findbelong(now);
if(indfs[now])
{
memset(vis,,sizeof(vis));
combinecircle(now,now);
build();
return true;
}
indfs[now]=true;
return findcircle(que[now].top().end);
} void build()
{
bool finish[maxx];
memset(finish,,sizeof(finish));
for(int i=;i<m;i++)
{
int po=findbelong(i);
if(finish[po])continue;
finish[po]=true;
while(!que[po].empty())que[po].pop();
for(int j=;j<=m;j++)
{
int pb=findbelong(j);
if(po==pb)continue;
edge en;en.begin=po;en.end=pb;
que[po].push(en);
}
}
return ;
}
bool counted[maxx];
int main()
{freopen("1.txt","r",stdin);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<n;i++)
zero.push_back(0.0);
for(int i=;i<m;i++)
{
vector<double>nowv;
for(int j=;j<n;j++)
{ double nv;cin>>nv;nowv.push_back(nv);}
vec.push_back(nowv);
}
vec.push_back(zero);
for(int i=;i<=m;i++)
for(int j=;j<=m;j++)
{ cost[i][j]=minv(vec[i],vec[j]);}
root=m;
ansnow=;
belongcircle[root]=root;
for(int i=;i<m;i++)
{
belongcircle[i]=i;
}
bool exis=false;
do
{
build();
exis=false;
bool finish[maxx];
memset(finish,,sizeof(finish));
for(int i=;i<m;i++)
{
int po=findbelong(i);
if(finish[po])continue;
memset(indfs,,sizeof(indfs));
exis=findcircle(po);
finish[po]=true;
}
}while(exis);
memset(counted,,sizeof(counted));
for(int i=;i<m;i++)
{
int po=findbelong(i);
if(counted[po])continue;
counted[po]=true;
ansnow+=cost[findbelong(que[po].top().begin)][findbelong(que[po].top().end)];
}
printf("%lf\n",ansnow);
return ;
}
代码比较乱。。