首页 > 代码库 > AIZU AOJ 2309 Vector Compression 最小树形图（朱—刘算法）

AIZU AOJ 2309 Vector Compression 最小树形图（朱—刘算法）

2024-09-03 22:42:12   220人阅读

题意简述：给定若干个相同维度的向量，寻找一种排序方法，使得所有向量的表示长度总和最低。 所谓表示长度为（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

              

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<stack>
  8 #include<vector>
  9 using namespace std;
 10 
 11 
 12 struct edge
 13 {
 14  int begin;int end;    
 15 };
 16 
 17 const int maxx=120;
 18 bool vis[maxx],indfs[maxx];
 19 vector<double>zero;
 20 int n,m,root;
 21 vector<vector<double> >vec;
 22 double cost[maxx][maxx],Cost[maxx][maxx];
 23 bool operator <(const edge a,const edge b)
 24 {
 25  double ac=cost[a.begin][a.end];double bc=cost[b.begin][b.end];
 26  return ac>bc;//从小到大排序    
 27 };
 28 priority_queue<edge>que[maxx];
 29 double minv(vector<double> a,vector<double> b)
 30 {
 31  double ab=0,bsqrt=0,asqrt=0;
 32  for(int i=0;i<a.size();i++)
 33      {ab+=a[i]*b[i];bsqrt+=b[i]*b[i];asqrt+=a[i]*a[i];}
 34      
 35  if((bsqrt-0.0)<1e-10)return asqrt;
 36  return asqrt-(ab*ab/bsqrt);
 37 }
 38 int belongcircle[maxx];
 39 int findbelong(int x)
 40 {
 41  if(x==belongcircle[x])return x;
 42      else return belongcircle[x]=findbelong(belongcircle[x]);
 43 }
 44 
 45 double ans,ansnow;
 46 double min(double a,double b)
 47 {
 48  if(a<b)return a;
 49      else return b;
 50 }
 51 void combinecircle(int now,int begin)
 52 {
 53  now=findbelong(now);
 54  if(vis[now])return ;
 55  vis[now]=true;
 56  edge e1=que[now].top();
 57  double coste=cost[findbelong(e1.begin)][findbelong(e1.end)];
 58  ansnow+=coste;
 59  bool finish[maxx];
 60  memset(finish,0,sizeof(finish));
 61  for(int i=0;i<=m;i++)
 62      {
 63       int po=findbelong(i);
 64       if(po==now||po==begin)continue;
 65       if(finish[po])continue;
 66       finish[po]=true;
 67       cost[begin][po]=min(cost[begin][po],cost[now][po]-coste);
 68       cost[po][begin]=min(cost[po][begin],cost[po][now]);
 69     }
 70  belongcircle[now]=begin;
 71  combinecircle(e1.end,begin);
 72  return ;
 73 }
 74 void build();
 75 bool findcircle(int now)
 76 {
 77  if(now==root)return false; 
 78  now=findbelong(now);
 79  if(indfs[now])
 80      {
 81       memset(vis,0,sizeof(vis));
 82       combinecircle(now,now);
 83       build();
 84       return true;
 85     }
 86  indfs[now]=true;
 87  return findcircle(que[now].top().end);
 88 }
 89 
 90 void build()
 91 {
 92  bool finish[maxx];
 93  memset(finish,0,sizeof(finish));
 94  for(int i=0;i<m;i++)
 95      {
 96       int po=findbelong(i);
 97       if(finish[po])continue;
 98       finish[po]=true;
 99       while(!que[po].empty())que[po].pop();
100       for(int j=0;j<=m;j++)
101           {
102            int pb=findbelong(j);
103            if(po==pb)continue;
104            edge en;en.begin=po;en.end=pb;
105            que[po].push(en);
106         }
107     }
108  return ;
109 }
110 bool counted[maxx];
111 int main()
112 {freopen("1.txt","r",stdin);
113  ios::sync_with_stdio(false);
114  cin>>n>>m;
115  for(int i=0;i<n;i++)
116     zero.push_back(0.0);
117  for(int i=0;i<m;i++)
118      {
119      vector<double>nowv;
120      for(int j=0;j<n;j++)
121          { double nv;cin>>nv;nowv.push_back(nv);}
122      vec.push_back(nowv);
123     }
124  vec.push_back(zero);
125  for(int i=0;i<=m;i++)
126      for(int j=0;j<=m;j++)
127          { cost[i][j]=minv(vec[i],vec[j]);}
128  root=m;
129  ansnow=0;
130  belongcircle[root]=root;
131       for(int i=0;i<m;i++)
132           {
133            belongcircle[i]=i;
134           }
135      bool exis=false;
136           do
137               {
138                build();
139                exis=false;
140                bool finish[maxx];
141                memset(finish,0,sizeof(finish));
142                for(int i=0;i<m;i++)
143                {  
144                 int po=findbelong(i);
145                 if(finish[po])continue;
146                   memset(indfs,0,sizeof(indfs));
147                   exis=findcircle(po);
148                   finish[po]=true;
149              }
150             }while(exis);
151      memset(counted,0,sizeof(counted));
152      for(int i=0;i<m;i++)
153          {
154          int po=findbelong(i);
155          if(counted[po])continue;
156          counted[po]=true;
157          ansnow+=cost[findbelong(que[po].top().begin)][findbelong(que[po].top().end)];    
158         }
159  printf("%lf\n",ansnow);
160  return 0;
161 }

代码比较乱。。

AIZU AOJ 2309 Vector Compression 最小树形图（朱—刘算法）


联系
我们