做完心情不太好，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位置擴張其實只是一個無關條件。