题目链接:
http://218.62.22.209:8080/problem.php?cid=1580&pid=0
懒得粘题面(QAQ题面好像粘不了)
最多5维,很容易就能想到把每一维都排序后跑最小生成树,然后就A了
水题~~
上代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100020
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,k;
int tot=0;
struct DMF{
int wei[7],bh;
}hxr[N];
struct Edge{
int x,y,z;
Edge(int _=0,int __=0,int ___=0):x(_),y(__),z(___){}
}zhn[1000050];
inline void add(int x,int y,int k){
zhn[++tot]=Edge(x,y,k);
}
int fa[N];
int find(int k){
if(fa[k]!=k) fa[k]=find(fa[k]);
return fa[k];
}
inline bool cmp666(Edge a,Edge b){
return a.z<b.z;
}
inline bool cmp1(DMF a,DMF b){
return a.wei[1]<b.wei[1];
}
inline bool cmp2(DMF a,DMF b){
return a.wei[2]<b.wei[2];
}
inline bool cmp3(DMF a,DMF b){
return a.wei[3]<b.wei[3];
}
inline bool cmp4(DMF a,DMF b){
return a.wei[4]<b.wei[4];
}
inline bool cmp5(DMF a,DMF b){
return a.wei[5]<b.wei[5];
}
int main(){
n=read();
k=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
hxr[i].wei[j]=read();
hxr[i].bh=i;
}
}
for(int i=1;i<=k;i++){
if(i==1)
sort(hxr+1,hxr+n+1,cmp1);
if(i==2)
sort(hxr+1,hxr+n+1,cmp2);
if(i==3)
sort(hxr+1,hxr+n+1,cmp3);
if(i==4)
sort(hxr+1,hxr+n+1,cmp4);
if(i==5)
sort(hxr+1,hxr+n+1,cmp5);
for(int j=2;j<=n;j++){
add(hxr[j-1].bh,hxr[j].bh,abs(hxr[j].wei[i]-hxr[j-1].wei[i]));
}
}
long long ans=0;
sort(zhn+1,zhn+tot+1,cmp666);
for(int i=1;i<=n;i++) fa[i]=i;
int tot2=0;
for(int i=1;i<=tot;i++){
int fx=find(zhn[i].x),fy=find(zhn[i].y);
if(fx!=fy) {
ans+=zhn[i].z;
tot2++;
fa[fx]=fy;
}
if(tot2==n-1){
printf("%lld",ans);
return 0;
}
}
}
我不会告诉你我又把数组开小了(QWQ)