kmjp's blog

競技プログラミング参加記です

AtCoder ARC #018 : D - 僕は友達が少ない

ARC

これは知らない定理が使われていたので本番での解答は無理だ…。
http://arc018.contest.atcoder.jp/tasks/arc018_4

問題

初期状態でN個の点がある。
ここに辺の候補がM個あり、各候補は辺の両端の点および辺を張るコストからなる。

これらの点から全域木を作るとき、辺を張る最小のコストを求めよ。
また、その最小コストで生成できる木の組み合わせ数を答えよ。

解法

AtCoder Regular Contest 018 解説 を見て解いてみた。


まず、最小コストについてはプリム法で求めればよい。
問題は組み合わせ数である。

処理過程において、あるN点の集合V[i]を連結できる同一コストの辺が(N-1)本以上ある場合、プリム法において(N-1)本以上のうちから(N-1)本だけ選んでそれらを連結することになる。
このような条件では、同一コストで生成できる木が複数存在する。
この組み合わせ数は行列木定理によって計算できるため、そのような辺集合が登場するたびにその組み合わせを掛け合わせていけば良い。

int N,M;
ll mo=1000000007;
map<int,vector<pair<int,int> > > MM;

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll mat[101][101];
ll det_mo(int N) {
	int x,y,z;
	ll ret=1;
	FOR(y,N) FOR(z,N) mat[y][z]=((mat[y][z]%mo)+mo)%mo;
	FOR(x,N) {
		if(mat[x][x]==0) {
			for(y=x+1;y<N;y++) if(mat[y][x]) break;
			if(y==N) return 0;
			FOR(z,N) swap(mat[x][z],mat[y][z]);
		}
		ret=ret*mat[x][x]%mo;
		ll rev=modpow(mat[x][x],mo-2,mo);
		FOR(z,N) mat[x][z]=rev*mat[x][z]%mo;
		for(y=x+1;y<N;y++) if(mat[y][x]) {
			rev=mat[y][x];
			for(z=x;z<N;z++) mat[y][z]=((mat[y][z]-mat[x][z]*rev)%mo+mo)%mo;
		}
	}
	return ret;
}

class UF {
	public:
	static const int ufmax=10002;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return 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;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>j;
		if(x>y) swap(x,y);
		MM[j].push_back(make_pair(x-1,y-1));
	}
	
	UF uf1,uf2;
	
	int cg=N;
	ll co=0,tc=0,ret=1;
	ITR(it,MM) {
		int pcg=cg;
		uf2=uf1;
		co=it->first;
		ITR(it2,it->second) if(uf1[it2->first] != uf1[it2->second]) {
			uf1.unite(it2->first,it2->second);
			tc+=co;
			cg--;
		}
		if(pcg==cg) continue;
		vector<int> V;
		ITR(it2,it->second) if(uf2[it2->first] != uf2[it2->second]) V.push_back(uf1[it2->first]);
		sort(V.begin(),V.end());
		V.erase(unique(V.begin(),V.end()),V.end());
		ITR(vit,V) {
			ZERO(mat);
			map<int,int> MM;
			ITR(it2,it->second) if(uf1[it2->first]==*vit) {
				x = uf2[it2->first];
				y = uf2[it2->second];
				if(x==y) continue;
				if(MM.find(x) == MM.end()) MM[x]=MM.size()-1;
				if(MM.find(y) == MM.end()) MM[y]=MM.size()-1;
				mat[MM[x]][MM[x]]++;
				mat[MM[y]][MM[y]]++;
				mat[MM[x]][MM[y]]--;
				mat[MM[y]][MM[x]]--;
			}
			ret=ret*det_mo(MM.size()-1)%mo;
		}
		if(cg==1) break;
	}
	_P("%lld %lld\n",tc,ret);
	
}

まとめ

行列木定理なんて知らんかった…。