ARC076_D - そーすにっき

arc076.contest.atcoder.jp

解法：最小全域木　O(NlogN)？

普通に最小全域木をやろうとすると辺の数O(N^2)で死亡するので辺の数を減らす必要がある

とりあえずサンプル2をxで昇順ソートすると

yでソートするとこう

で、このサンプル2の解答は

{((4,9),(7,6)),((7,6),(8,3)),((8,3),(13,5)),((13,5),(12,19)),((8,3),(18,1))}

の辺集合選択で合計の重みは8

つまり、xかyでソートした時に隣り合う点を繋ぐ辺しか採用されることはない

これらの辺の数は2n-2本なのでクラスカルすればいい、という問題

この日のABCでとけなかったので解説を直後に読んでいたので解法は覚えてたけどクラスカル法の実装に不安を覚えたので6割ほど素で書くことを目標に書きましたとさ

結果：全然だめでした

主にjoinの実装が雑すぎたせいで幾度となく閉路を作ってしまうアホやってたとか

結局こちら↓を参考に修正

http://www.prefield.com/algorithm/container/union_find.html

こちらのソースは1配列で経路圧縮とrank実装を同時実装してunionfindをすんごい小さい計算量に圧縮してるけど自分はrank実装してないので少し遅いです

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <numeric>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
 
class point{
public:
  int x,y,id;
  point(int x_,int y_,int i_):x(x_),y(y_),id(i_){}
  point():x(0),y(0){}
};
 
bool compx(const point &b,const point &a){
  return b.x==a.x?b.y<a.y:b.x<a.x;
}
bool compy(const point &b,const point &a){
  return b.y==a.y?b.x<a.x:b.y<a.y;
}
 
class edge{
public:
  int f,t,c;
  bool operator<(const edge &a){
    return c<a.c;
  }
  edge(int f_,int t_,int c_):f(f_),t(t_),c(c_){}
};
 
class uf{
public:
  vector<int> r;
  uf(int n):r(n,-1){};
  int find(int x,int y){
    if(root(x)==root(y))return 0;
    if(root(x)<root(y))return -1;
    if(root(x)>root(y))return 1;
  }
  int root(int x){
    if(r[x]==-1)return x;
    else return r[x]=root(r[x]);
  }
  void join(int x,int y){
    x=root(x);y=root(y);
    if(x!=y){
      r[x]=y;
    }
  }
};
 
class graph{
public:
  int vnum;
  vector<edge> E;
  uf u;
  graph(int n):vnum(n),u(n){};
  int kruscal(){
    int res=0;
    sort(E.begin(),E.end());
    for(int i=0,c=0;i<E.size()&&c<vnum-1;i++){
      if(u.find(E[i].f,E[i].t)){
        u.join(E[i].f,E[i].t);
        res+=E[i].c;
        c++;
      }
    }
    return res;
  }
};
 
int main(){
  int n;
  cin >> n;
  int x,y;
  vector<point> p;
  for(int i=0;i<n;i++){
    cin >> x >> y;
    p.push_back(point(x,y,i));
  }
  graph g(n);
  sort(p.begin(),p.end(),compx);
  for(int i=0;i<n-1;i++){
    g.E.push_back(edge(p[i].id,p[i+1].id,min(abs(p[i].x-p[i+1].x),abs(p[i].y-p[i+1].y))));
  }
  sort(p.begin(),p.end(),compy);
  for(int i=0;i<n-1;i++){
    g.E.push_back(edge(p[i].id,p[i+1].id,min(abs(p[i].x-p[i+1].x),abs(p[i].y-p[i+1].y))));
  }
  cout << g.kruscal() << endl;
}

D問題でこの実装量、絶対理想解じゃない気がするんだよなあ…(˘ω˘)