土下座しながら探索中

主に競技プログラミング

CODE FESTIVAL 2016 予選B : C - Gr-idian MST

問題リンク :
C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 :
日本語なので略

解法 :
(ほぼ備忘録)
クラスカル法。
ただし、辺が多すぎて愚直に列挙することはできない。
そこで、この問題では行または列ごとに辺の重みが決まっていることを利用する。

最小の行または列を見つけて、それらを舗装してしまう。
ただし、既に連結であるようなものは舗装しない(舗装した行の数と列の数を別々に覚えておいてそれを引けば良い、詳しくは下の例で)。
Sample Input2の実行例を以下に示す。
赤線が舗装した道を表す。
f:id:tei3344:20161012222424p:plain
f:id:tei3344:20161012224611p:plain
f:id:tei3344:20161012224654p:plain
f:id:tei3344:20161012224757p:plain
f:id:tei3344:20161012224827p:plain
f:id:tei3344:20161012224902p:plain
f:id:tei3344:20161012224936p:plain
f:id:tei3344:20161012225005p:plain



コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

#define DIR_W false
#define DIR_H true

struct Data {
  ll v;
  bool dir;
  bool operator < (const Data &data) const {
    if( v != data.v ) return v < data.v;
    return dir < data.dir;
  }
};

#define MAX 100010

int W,H;
ll p[MAX], q[MAX];

void compute() {
  vector<Data> vec;
  rep(i,W) vec.push_back((Data){p[i],DIR_W});
  rep(i,H) vec.push_back((Data){q[i],DIR_H});
  sort(vec.begin(),vec.end());
  int used_H = 0, used_W = 0;
  ll mini = 0;
  rep(i,(W+H)) {
    if( vec[i].dir == DIR_W ) {
      mini += ( (H+1) - used_H ) * vec[i].v;
      ++used_W;
    } else {
      mini += ( (W+1) - used_W ) * vec[i].v;
      ++used_H;
    }
  }
  cout << mini << endl;
}

int main() {
  cin >> W >> H;
  rep(i,W) cin >> p[i];
  rep(i,H) cin >> q[i];
  compute();
  return 0;
}