AtCoder ARC #078 : F - Mole and Abandoned Mine

時間かかったけど解けてよかった。
http://arc078.contest.atcoder.jp/tasks/arc078_d

問題

N頂点の連結無向グラフが与えられる。
各辺にはコストが設定されている。

このグラフからいくつか辺を取り除き、頂点1→Nに移動する同一頂点を2回以上通らない経路が1通りになるようにしたい。
取り除く辺のコストの総和の最小値を求めよ。

解法

O(3^N*N)のbitDPで解く。
以下の状態を考えよう。
dp(mask,v) := bitmaskであるmaskに含まれる頂点群に対し、頂点1→vに移動する同一頂点を2回以上通らない経路が1通りになるような状態の最小コスト
求めたいのはdp((2^N)-1,N)である。

この時、経路上に乗らない頂点がどうあるべきかを考えよう。
入力例１を見るとわかるが、経路上に乗らない頂点2,3は、経路上の頂点1,2のうち最大1つまでなら連結させてよい。

この考察をもとに、dp(mask,v)からの遷移を以下2種類が考える。

• v→v'と経路を一つ延長させ、dp(mask,v)からdp(mask|(2^v'),v')を求める。
  • この時、mask中に含まれるv以外の頂点とv'の間に辺があってはならないので、それらの辺を取り除くコストを支払う。
• maskに含まれない頂点群を、mask中vと連結させる(正確には、vと連結しなくてもよいがv以外のmask中の頂点と連結させないことを確約させる)。
  • これはmaskに含まれない頂点群のsubmaskに対し、dp(mask,v)からdp(mask|submask,v)を求めることに相当する。
  • maskとsubmaskの列挙はO(3^N)で行える。submaskに対し、mask中v以外の頂点との辺のコストの総和は、前処理でO(2^N*N^2)かけて求めておくことができる。

int N,M;
int mat[101][101];
int dp[1<<15][15];
int cost[1<<15][15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		mat[x-1][y-1]=r;
		mat[y-1][x-1]=r;
	}
	
	FOR(i,1<<N) {
		FOR(x,N) {
			dp[i][x]=1<<30;
			FOR(y,N) if(i&(1<<y)) cost[i][x]+=mat[x][y];
		}
	}
	
	dp[1][0]=0;
	for(int mask=0;mask<1<<N;mask++) {
		FOR(x,N) if((mask&(1<<x)) && dp[mask][x]<1<<30) {
			FOR(y,N) if(mat[x][y] && (mask&(1<<y))==0) {
				int addco=cost[mask][y]-mat[x][y];
				dp[mask|(1<<y)][y]=min(dp[mask|(1<<y)][y],dp[mask][x]+addco);
			}
			
			int nmask=mask^(1<<x);
			int left=((1<<N)-1)^mask;
			for(int i=left; i>0; i=(i-1)&left) {
				int add=0;
				FOR(y,N) if(i&(1<<y)) add+=cost[nmask][y];
				dp[mask|i][x]=min(dp[mask|i][x],dp[mask][x]+add);
			}
		}
	}
	
	cout<<dp[(1<<N)-1][N-1]<<endl;
	
}

まとめ

本番色々遠回りもしたけど時間内に解法にたどり着けてよかった。