状压模板求条
查看原帖
状压模板求条
565707
mediocre_楼主2025/7/3 21:28

16pts,剩下全WA,不知道拿错了QAQ

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, w[N][N], dp[N][1 << N]; 
int dfs(int u, int vis, int y) {
     //printf("%d %d %d\n", u, vis, y);
    if (u == n - 1 && vis < (1 << n) - 1) return INT_MIN; 
	if (vis == (1 << n) - 1 && u == n - 1) return y;
	if (dp[u][vis] != INT_MIN) return dp[u][vis];
	for (int i = 0; i < n; ++i) {
		if (vis >> i & 1 || w[u][i] == INT_MIN) continue ;
		dp[u][vis] = max(dp[u][vis], dfs(i, vis | (1 << i), y + w[u][i]));
	}
	return dp[u][vis];
}
int main() {
	scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            w[i][j] = INT_MIN;
	while (m--) {
        int u, v, ww;
        scanf("%d%d%d", &u, &v, &ww);
        w[u][v] = max(w[u][v], ww);
    }
    for (int i = 0; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j)
            dp[j][i] = INT_MIN;
	printf("%d", dfs(0, 1, 0));
	return 0;
}
2025/7/3 21:28
加载中...