TopCoder SRM 790 : Div1 Easy Div2 Hard TheSocialNetwork

もったいない…。
https://community.topcoder.com/stat?c=problem_statement&pm=16444&rd=18194

問題

N頂点M無効辺からなるグラフがある。
各辺には削除コストが与えられる。
このコストは2の累乗の形をしており、各辺のコストは異なる。

このグラフを非連結となるように辺をいくつか削除したい。
削除の総コストの最小値を求めよ。

解法

コストの大きい順に辺を見て、つなぐと全体が連結してしまいそうな辺が登場したら削除する、そうでなければつなぐ、を繰り返そう。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

const ll mo=1000000007;
ll p2[101010];

class TheSocialNetwork {
	public:
	int minimumCut(int n, int m, vector <int> u, vector <int> v, vector <int> l) {
		
		int i;
		p2[0]=1;
		FOR(i,100100) p2[i+1]=p2[i]*2%mo;
		ll ret=0;
		vector<pair<int,int>> V;
		FOR(i,l.size()) V.push_back({l[i],i});
		sort(ALL(V));
		reverse(ALL(V));
		UF<303> uf;
		
		
		FORR(x,V) {
			int a=u[x.second];
			int b=v[x.second];
			if(uf[a]==uf[b]) continue;
			if(uf.count(a)+uf.count(b)<n) {
				uf(a,b);
			}
			else {
				ret+=p2[x.first];
			}
		}
		return ret%mo;
	}
}

まとめ

あれ、これコストが2の累乗でなくてもよい？