CF 1430G Yet Another DAG Problem

• 给定一个有向无环图，设定每个点的点权，使得每条边的起点权值大于终点，最小化每条边的边权与起点与终点之差的乘积之和。

第一种方法可以将贡献记在点上，对答案的贡献为 \(a_i*( \sum w_{出边} - \sum w_{入边} )\)。于是可以从低到到高来安排每个点的权值。

设 \(f_{i,S}\) 为考虑到第 \(i\) 层，已安排了的集合为 \(S\)，所需要的最小代价，每个点要被选入必须要所有比它小的选了之后才能选，枚举子集转移即可。

第二种方法是将贡献按相隔层数拆分，设 \(f_{S}\) 为已经权值确定的点的集合为 \(S\)，最小所需要的代价和，转移到下一个状态 \(S‘\) 时要把所有边的端点恰好有一个在 \(S\) 中的边权累计。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
typedef long long LL;
typedef pair <int, int> P;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7, N = 2e6 + 10;
template <typename T>
inline void rd_(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	while (ch > ‘9‘ || ch < ‘0‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
	while (ch >= ‘0‘ && ch <= ‘9‘) x = x*10 + ch - ‘0‘, ch = getchar();
	x *= f;
}

int n, m, a[N], b[N], c[N], deg[N], p[N], S, s[N], f[N], h[N], w[N], tot, ans[N];
vector <int> g[N];

int main() {
	//freopen("data.in", "r", stdin);
	rd_(n), rd_(m), S = (1<<n) - 1;
	rep (i, 1, m) {
		rd_(a[i]), rd_(b[i]), rd_(c[i]);
		deg[b[i]]++, g[a[i]].push_back(b[i]);
	}
	queue <int> q;
	rep (i, 1, n) if (!deg[i]) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v, i = 0; i < (int) g[u].size(); i++) {
			p[v = g[u][i]] |= (p[u] | (1<<u - 1));
			if (!--deg[v]) q.push(v);
		}
	}
	rep (i, 0, S) {
		rep (j, 0, n - 1) if (i&(1<<j)) s[i] |= p[j + 1];
		rep (j, 1, m) 
			if ((i&(1<<a[j] - 1)) && ((i&(1<<b[j] - 1)) == 0)) 
				w[i] += c[j];
	//	cout<<i<<" "<<w[i]<<endl;
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	rep (i, 1, S) {
		for (int j = i; j; j = (j - 1)&i) {
			int k = i^j;
			if ((k&s[j]) == s[j] && f[i] > f[k] + w[k])
				f[i] = f[k] + w[k], h[i] = j;
		}
	}
	while (S) {
		++tot;
		rep (i, 0, n - 1) if (h[S]&(1<<i)) ans[i + 1] = tot;
		S -= h[S];
	}
	rep (i, 1, n) printf("%d ", ans[i]);
}

CF 1430G Yet Another DAG Problem

原文：https://www.cnblogs.com/ympc2005/p/14303386.html