2012 WUPC2 : E - 独立記念日

さて問題のE。
本番では部分点はすぐ取れたものの、ミス続きで完答できず終わってしまった問題。
その後しょうもないミスに気が付いて解けたが…。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_05

無向グラフと辺のコストが与えられるので、グラフがK個に分かれるまで辺を減らし、そのコストを最小化する問題。
そのまま行うと計算量が大きいが、ここでは閉路が１個以下であることが保障されているのでそれを利用して解いていく。

まず、DFSで初期状態でグラフが何個に分かれているかと、閉路の有無を数える。

部分点でもある閉路が無い場合を考える。
この場合、１個辺を減らせばグラフの分割数が１個増えるので、辺のコストが小さい順に、(K-(今の分割数))個分だけ辺を取り除けばよい。

次に閉路がある場合。これは以下の２通りが考えられる。

• 閉路中の辺を減らす場合。この場合、閉路中のコストが最小の辺を減らすと、閉路がなくなって上の問題に持って行ける。
• 閉路中の辺を減らさない場合、閉路を構成する辺を除いて、上記手段で辺を減らしてK個の分割できるかチェックする。

本番では、最初からグラフの分割数がK個以上の場合を正しく取り扱えておらずミスを連発した。
気づけばしょうもないミスだな…。

int N,M,K;
ll cost[200][200];
vector<ll> cl;

int npart;
int vis[101],inloop[101],LT;

int dfs(int cur) {
	int i;
	vis[cur]=1;
	FOR(i,N) {
		if(cost[cur][i]>0) {
			cost[cur][i] = cost[i][cur] = -cost[cur][i];
			if(vis[i]) {
				LT=i;
				inloop[cur]=i;
			}
			else {
				if(dfs(i)>=0 && i!=LT) inloop[cur]=i;
			}
		}
	}
	return inloop[cur];
}

void solve() {
	int x,y,z,i,j,rr,TM;
	ll p,tp;
	
	GET3(&N,&M,&K);
	ZERO(cost);
	
	cl.clear();
	FOR(i,M) {
		GET3(&x,&y,&z);
		cost[x-1][y-1]=cost[y-1][x-1]=z;
		cl.push_back(z);
	}
	
	LT=-1;
	npart=0;
	ZERO(vis);
	FOR(i,N) inloop[i]=-1;
	FOR(i,N) {
		if(vis[i]) continue;
		npart++;
		dfs(i);
	}
	FOR(x,N) FOR(y,N) cost[x][y]=abs(cost[x][y]);
	
	if(npart>=K) {
		p=0;
	}
	else if(LT>=0) {
		//輪を切る場合
		p=99999999;
		FOR(i,N) if(inloop[i]>=0) p=min(p,cost[i][inloop[i]]);
		cl.erase(find(cl.begin(),cl.end(),p));
		
		x = K-npart;
		sort(cl.begin(),cl.end());
		FOR(i,x) p+=cl[i];
		
		//切らない場合
		FOR(i,N) if(inloop[i]>=0) { cost[i][inloop[i]]=cost[inloop[i]][i]=0;}
		cl.clear();
		FOR(x,N) for(y=x+1;y<N;y++) if(cost[x][y]>0) cl.push_back(cost[x][y]);
		x = K-npart;
		if(x<=cl.size()) {
			ll tp=0;
			sort(cl.begin(),cl.end());
			FOR(i,x) tp+=cl[i];
			p = min(p,tp);
		}
	}
	else {
		x = K-npart;
		sort(cl.begin(),cl.end());
		p = 0;
		FOR(i,x) p+=cl[i];
	}
	_P("%lld\n",p);
	
	return;
}

まとめ

一生懸命デバッグした後、最初からK個以上に分割されているケースに気が付いた。
うーん、AtCoder主催のコンテストはなぜかこういうミス多いな…。