求助为何这样优化不对
查看原帖
求助为何这样优化不对
463956
incra楼主2024/6/2 08:00

代码中注释部分加上去就错了,感觉没啥问题啊

#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\incra\\Desktop\\"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
	if (y > x) return x = y,true;
	return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
	if (y < x) return x = y,true;
	return false;
}
LL power (LL a,LL b,LL p) {
	LL ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
const int N = 20,M = (1 << 12) + 10,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int expand[M];
int f[N][M];
int main () {
	cin >> n >> m;
	memset (g,0x3f,sizeof (g));
	for (int i = 1;i <= n;i++) g[i][i] = 0;
	while (m--) {
		int a,b,c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min (g[a][b],c);
	}
	for (int s = 0;s < 1 << n;s++) {
		for (int i = 1;i <= n;i++) {
			if (!(s >> i - 1 & 1)) continue;
			for (int j = 1;j <= n;j++) {
				if (g[i][j] != INF) expand[s] |= 1 << j - 1;
			}
		}
	}
	memset (f,0x3f,sizeof (f));
	for (int i = 1;i <= n;i++) f[1][1 << i - 1] = 0;
	for (int s = 0;s < 1 << n;s++) {
		for (int t = s - 1 & s;t;t = t - 1 & s) {
			if ((s & expand[t]) == s && (t | expand[t]) == s) {
				int remain = s ^ t;
				int cost = 0;
				for (int i = 1;i <= n;i++) {
					if (remain >> i - 1 & 1) {
						int minx = INF;
						for (int j = 1;j <= n;j++) {
							if (t >> j - 1 & 1) tomin (minx,g[i][j]);
						}
						if (minx == INF) {
							cost = INF;
							break;
						}
						cost += minx;
					}
				}
				if (cost == INF) continue;
				for (int i = 2;i <= n;i++) tomin (f[i][s],f[i - 1][t] + cost * (i - 1));
			}
		}
	}
	int ans = INF;
	for (int i = 1;i <= n;i++) tomin (ans,f[i][(1 << n) - 1]);
	cout << ans << endl;
	return 0;
}
2024/6/2 08:00
加载中...