AtCoder ARC #029 : C - 高橋君と国家

こちらは意外とあっさり。
http://arc029.contest.atcoder.jp/tasks/arc029_3

問題

N個の頂点とM個の無向辺がある。
初期状態では、全ての頂点は交易所を持たず、全ての辺は舗装されていない。

ここで、全ての頂点について、交易所を持つか、もしくは舗装された辺だけをたどり交易所を持つ他の頂点にたどり着けるようにしたい。
各頂点に対し交易所を持つコストはC[i]である。
また、辺の舗装コストはR[i]である。

条件を満たす最小コストを求めよ。

解法

各頂点についてunion-findで連結状態を管理し、かつ各連結頂点群が１つでも交易所を持つか管理する。
そして、クラスカル法のアレンジで、コストの小さい順に交易所作成または舗装を行う。

• ある頂点の交易所作成は、連結頂点群中に交易所がなければ作成する。すでに交易所があれば作成しない。
• ある辺の舗装は、辺の両端の頂点が未連結で、かつどちらかの頂点の連結頂点群に交易所がなければ舗装を行う。
  • 頂点が未連結でも、両頂点がすでに交易所を持つ頂点と連結しているなら舗装しなくてよい。

class UF {
	public:
	static const int ufmax=100052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M;
int ok[100002];
vector< pair<int,ll> > V;
UF uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		V.push_back(make_pair(x,i*100000LL+i));
	}
	FOR(i,M) {
		cin>>x>>y>>j;
		x--;y--;
		V.push_back(make_pair(j,x*100000LL+y));
	}
	sort(V.begin(),V.end());
	ll tot=0;
	ITR(it,V) {
		int c=it->first;
		int s=it->second/100000,t=it->second%100000;
		
		if(s==t) {
			if(ok[uf[s]]==0) ok[uf[s]]=1, tot+=c;
		}
		else if(uf[s]!=uf[t] && (!ok[uf[s]] || !ok[uf[t]])) {
			int ok2=ok[uf[s]] | ok[uf[t]];
			uf.unite(s,t);
			ok[uf[s]]=ok2;
			tot+=c;
		}
	}
	cout << tot << endl;
	
}

まとめ

すんなり思いついたはいいが、これもしょうもないoverflowをしてもったいない。