P4802 [CCO 2015]路短最

这题的题意是求一条经过起点和终点的最长路径。且一个点只能经过一次。

我们设定 \(dis_{i,j}\) 为 i 到 j 的距离（应该没有重边）

要注意的是不能用 \(Floyd\) 求最长路这样会挂掉

因为你这样就没办法保证点 \(i\) 只经过一次

显然是状压dp 我们考虑 dp 状态 \(dp_{i,j}\)

\(i\) 表示当前位置 \(j\)表示走过的地方

#include<bits/stdc++.h>

using namespace std ;

#define int long long

#define fi first

#define se second

#define pb push_back

inline int read() {

	register int x = 0 , f = 1 ;

	register char c = getchar() ;

	for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;

	for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c & 15) ;

	return x * f ;

}

template < typename T > inline bool cmax(T & x , T y) {

	return x < y ? (x = y) , 1 : 0 ;

}

template < typename T > inline bool cmin(T & x , T y) {

	return x > y ? (x = y) , 1 : 0 ;

}

template < typename T > inline bool cabs(T & x) {

	return x > 0 ? 1 : (x = - x) , 0 ;

}

inline int QP(int x , int y , int Mod) {

	int ans = 1 ;

	for( ; y ; y >>= 1 , x = (x * x) % Mod)

		if(y & 1) ans = (ans * x) % Mod ;

	return ans ;

}

int n , m ;

const int N = 19 ;

int dis[N][N] ;

int dp[N][1 << N] ;

signed main() {

	memset(dis , 0xcf , sizeof(dis)) ;

	memset(dp , 0xcf , sizeof(dp)) ;

	n = read() , m = read() ;

	for(register int i = 1 ; i <= m ; i ++) {

		int u = read() , v = read() , w = read() ;

		dis[++ u][++ v] = w ;

	}

	for(register int i = 2 ; i <= n ; i ++) dp[i][1 + (1 << i - 1)] = dis[1][i] ;

	int s = (1 << n) - 1 ;

	for(register int i = 2 ; i <= s ; i ++) {

		for(register int j = 1 ; j <= n ; j ++) {

			if((i & (1 << j - 1)))

				for(register int k = 1 ; k <= n ; k ++) {

					if(j ^ k && (! (i & (1 << k - 1)))) {

						cmax(dp[k][i | (1 << k - 1)] , dp[j][i] + dis[j][k]) ;

					}

				}

		}

	}

	int ans = 0 ;

	for(register int i = (1 << n - 1) + 1 ; i <= s ; i ++)

		cmax(ans , dp[n][i]) ;

	printf("%lld\n" , ans) ;

	return 0 ;

}

巴特西

P4802 [CCO 2015]路短最

最新文章

热门文章