yukicoder : No.845 最長の切符

実装が割と自明なので、★3かというとちょっと迷っちゃうな。
https://yukicoder.me/problems/no/845

問題

距離付の無向グラフが与えられる。
同じ頂点を２回以上通らない最長パスの長さを求めよ。

解法

bitdpで解く。
dp(mask, v) := maskに示すbitmaskに対応する頂点を経由し、今末尾がvである最長パスの長さ
として、vに続く頂点を総当たりすればよい。

int N,M;
int A[16][16];
int dp[1<<16][16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(A);
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		x--,y--;
		A[x][y]=A[y][x]=max(A[y][x],r);
	}
	
	MINUS(dp);
	FOR(i,N) dp[1<<i][i]=0;
	int mask;
	int ma=0;
	FOR(mask,1<<N) FOR(i,N) if(dp[mask][i]>=0) {
		ma=max(ma,dp[mask][i]);
		FOR(x,N) if(A[i][x]>=0 && (mask&(1<<x))==0) dp[mask|(1<<x)][x]=max(dp[mask|(1<<x)][x],dp[mask][i]+A[i][x]);
	}
	cout<<ma<<endl;
	
}

まとめ

今回は全体的に簡単だったみたいね。