做完心情不太好,1000分的水题居然因为自己开小了数组而挂掉。算了,不解释。
250
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
struct point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int x,y;
bool operator <(point o)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(x!=o.x)
return x<o.x;
else
return y<o.y;
}
}p[100];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int get(int i,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class LinearTravellingSalesman
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
int findMinimumDistance(vector <int> x, vector <int> y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
n=x.size();
int i;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
};
1000
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
int n,m;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int f[3000];
int r[3000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find(int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int Union(int x,int y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f[a]=b;
r[b]+=r[a];
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f[b]=a;
r[a]+=r[b];
}
return 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int a,b;
int v;
bool operator<(node o)const
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return v>o.v;
}
}edge[1000000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int mm[500][500];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[4][2]=
{
{-1,0},
{0,1},
{1,0},
{0,-1}};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool god(int x,int y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(x>=0&&x<n&&y>=0&&y<m)
return true;
else return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class ActivateGame
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
int findMaxScore(vector <string> g)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
n=g.size();
m=g[0].length();
int i,j;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**///////////////////////////////////////////////////////////////////////////
int p=0;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int k;
for(k=0;k<4;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int nx=i+dir[k][0];
int ny=j+dir[k][1];
if(god(nx,ny))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
edge[p].a=i*m+j;
edge[p].b=nx*m+ny;
edge[p].v=abs(mm[i][j]-mm[nx][ny]);
p++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
for(i=0;i<n*m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f[i]=i;
r[i]=1;
}
int cnt=0;
int sum=0;
sort(edge,edge+p);
for(i=0;i<p;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(Union(edge[i].a,edge[i].b))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cnt++;
sum+=edge[i].v;
}
if(cnt==n*m-1)
break;
}
return sum;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
};
不过还是要简要证明一下,无序生成边的kruskal算法其实和从a[0][0]位置不断向外扩张的方法是等价的。
因为二者都构造了最小生成树,所以权值和必然相等。所以是不是按照题目的意思从啊0 0位置扩张其实只是一个无关条件。