Codeforces ECR #096 : G. Yet Another DAG Problem

ECRの最終問の割には、コード量はさほど多くない。
https://codeforces.com/contest/1430/problem/G

問題

DAGを成すグラフが与えられる。
各辺eには重みW[e]が設定されている。

以下を満たすように、各点vに整数A[v]を割り当てる1例を示せ。

• u→vに辺eがあるとき、B[e]=A[v]-A[u]とすると、B[e]は正となる。
• B[e]*W[e]の総和は最小である。

解法

f(mask) := maskに該当する頂点群の値を設定した状態における、それらの頂点群の部分グラフにおけるB[e]*W[e]の総和の最小値
として、mask中の頂点vにおける最大値A[v]に対し、A[v]+1を割り当てる頂点集合を総当たりしよう。

最後に復元パートがあるのでちょっと面倒。

int N,M;
int W[20][20];
ll sum[1<<18];
int A[20];
ll mi[1<<18];
int from[1<<18];
int ng[1<<18];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		x--,y--;
		W[x][y]=r;
	}
	int mask;
	FOR(mask,1<<N) {
		FOR(j,N) FOR(i,N) if(i!=j&&(mask&(1<<i))&&(mask&(1<<j))&&W[i][j]) ng[mask]=1;
		if(ng[mask]) mi[mask]=1LL<<60;
	}
	for(mask=1;mask<1<<N;mask++) if(mi[mask]<1LL<<60) {
		FOR(i,N) FOR(j,N) if(W[i][j]) {
			if((mask&(1<<i)) && (mask&(1<<j))==0) mi[mask]+=W[i][j];
			if((mask&(1<<i))==0 && (mask&(1<<j))) mi[mask]=1LL<<60;
		}
		int lef=((1<<N)-1)^mask;
		for(int sm=lef; sm>0; sm=(sm-1)&lef) {
			if(ng[sm]==0&&mi[sm|mask]>mi[mask]) {
				mi[sm|mask]=mi[mask];
				from[sm|mask]=mask;
			}
		}
	}
	
	x=(1<<N)-1;
	int cur=100;
	while(x) {
		y=from[x];
		FOR(i,N) if((x^y)&(1<<i)) A[i]=cur;
		cur++;
		x=y;
	}
	FOR(i,N) cout<<A[i]<<" ";
	cout<<endl;
	
}

まとめ

こちらもECRのボス問の割に素直。