The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

TC SRM 470

做完心情不太好,1000分的水题居然因为自己开小了数组而挂掉。算了,不解释。
250
#include<iostream>
#include
<algorithm>
#include
<cstdio>
#include
<string>
#include
<vector>
using namespace std;
struct point
{

    
int x,y;
    
bool operator <(point o)
    
{

        
if(x!=o.x)
            
return x<o.x;
        
else
            
return y<o.y;
    }

}
p[100];
int n;

int get(int i,int j)
{
    
return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
}



class LinearTravellingSalesman
{
public:
    
int findMinimumDistance(vector <int> x, vector <int> y)
    
{
        n
=x.size();
        
int i;
        
for(i=0;i<n;i++)
        
{

            p[i].x
=x[i];
            p[i].y
=y[i];
        }

        sort(p,p
+n);
        
int ans=0;
        
for(i=1;i<n;i++)
            ans
+=get(i,i-1);
        
return ans;


    }

    
}
;

1000
#include<iostream>
#include
<algorithm>
#include
<cstdio>
#include
<string>
#include
<vector>
using namespace std;
int n,m;


int f[3000];
int r[3000];

int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;

}


struct node
{

    
int a,b;
    
int v;
    
bool operator<(node o)const
    
{

        
return v>o.v;
    }

}
edge[1000000];

int mm[500][500];

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

bool god(int x,int y)
{

    
if(x>=0&&x<n&&y>=0&&y<m)
        
return true;
    
else return false;
}


class ActivateGame
{
public:
    
int findMaxScore(vector <string> g)
    
{
        n
=g.size();
        m
=g[0].length();
        
int i,j;
        
for(i=0;i<n;i++)
        
{
            
for(j=0;j<m;j++)
            
{

                
if(g[i][j]>='0'&&g[i][j]<='9')
                    mm[i][j]
=g[i][j]-'0';
                
else if(g[i][j]>='a'&&g[i][j]<='z')
                    mm[i][j]
=g[i][j]-'a'+10;
                
else if(g[i][j]>='A'&&g[i][j]<='Z')
                    mm[i][j]
=g[i][j]-'A'+36;
            }

        }

        
//////////////////////////////////////////////////////////////////////////
        int p=0;
        
for(i=0;i<n;i++)
        
{
            
for(j=0;j<m;j++)
            
{

                
int k;
                
for(k=0;k<4;k++)
                
{
                    
int nx=i+dir[k][0];
                    
int ny=j+dir[k][1];
                    
if(god(nx,ny))
                    
{

                        edge[p].a
=i*m+j;
                        edge[p].b
=nx*m+ny;
                        edge[p].v
=abs(mm[i][j]-mm[nx][ny]);
                        p
++;
                    }


                }

                

            }

        }

        
for(i=0;i<n*m;i++)
        
{
            f[i]
=i;
            r[i]
=1;
        }

        
int cnt=0;
        
int sum=0;
        sort(edge,edge
+p);
        
for(i=0;i<p;i++)
        
{
            
if(Union(edge[i].a,edge[i].b))
            
{

                cnt
++;
                sum
+=edge[i].v;
            }

            
if(cnt==n*m-1)
                
break;
        }

        
return sum;



    }



}
;

不过还是要简要证明一下,无序生成边的kruskal算法其实和从a[0][0]位置不断向外扩张的方法是等价的。
因为二者都构造了最小生成树,所以权值和必然相等。所以是不是按照题目的意思从啊0 0位置扩张其实只是一个无关条件。

posted on 2010-05-21 01:22 abilitytao 阅读(1132) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理