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]);
}

553E - Kyoya and Train

\(n\le 55\) 个点， \(m \le 100\) 条边的有向图，每条边有代价 \(c\)，且花费的时间为 \(1...t\) 的概率是给定的，若从 \(1\) 到 \(n\) 的总时间超过了 \(t\)，则还需付出 \(x\) 的代价，求出决策最优时的期望代价。

考虑 \(dp\)，设 \(f_{u,i}\) 为当前在 \(u\)，时间为 \(i\)，最少还需要付出代价的期望。

\[f_{u,j} = \min \limits_{v} \sum_{k = 1}^t f_{v,j + k}*p_{{u,v},k} + w \]

\(i > t\) 时，\(f_{u, i} = d_{i, n} + x\)，且 \(i\le t, f_{n,i} = 0\)。

考虑每条边对 \(f\) 的贡献，发现把 \(p\) 翻转以后是卷积的形式，所以可以分治 \(FFT\) 优化这个过程。

#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 = 4e4 + 5;
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;
}

struct C {
	double x, y;
	C (double a = 0, double b = 0) {
		x = a, y = b;
	}
} A[N], B[N];
C operator + (C a, C b) { return C(a.x + b.x, a.y + b.y); }
C operator - (C a, C b) { return C(a.x - b.x, a.y - b.y); }
C operator * (C a, C b) { return C(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }

int n, m, t, x, d[55][55], a[105], b[105], c[105], len, cnt, rev[N];
double p[101][N], f[55][N], g[105][N], Pi = acos(-1);

void fft_(C *a, int f) {
	rep (i, 0, len - 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int s = 2; s <= len; s <<= 1) {
		C wn(cos(2*Pi/s), f*sin(2*Pi/s));
		for (int j = 0; j < len; j += s) {
			C w(1, 0);
			for (int k = 0; k < s/2; k++, w = w*wn) {
				C u = a[j + k], v = a[j + k + s/2]*w;
				a[j + k] = u + v, a[j + k + s/2] = u - v;
			}
		}
	}
	if (f == -1)
		rep (i, 0, len - 1) a[i].x /= len;
}

void calc_(int x, int l, int r) {
	int mid = (l + r)>>1;
	for (len = 1, cnt = 0; len <= r - mid - 1 + r - l; len <<= 1) cnt++;
	rep (i, 0, len - 1) rev[i] = (rev[i>>1]>>1) + ((i&1)<<cnt - 1), A[i] = B[i] = (C) {0, 0};
	rep (i, 0, r - l - 1) A[i].x = p[x][i + 1];
	per (i, r, mid + 1) B[r - i].x = f[b[x]][i];
	fft_(A, 1), fft_(B, 1);
	rep (i, 0, len - 1) A[i] = A[i]*B[i];
	fft_(A, -1);
	rep (i, l, mid) g[x][i] += A[r - i - 1].x;
}

void solve_(int l, int r) {
	if (l >= t) return;
	if (l == r) {
		rep (i, 1, n - 1) f[i][l] = inf;
		rep (i, 1, m) f[a[i]][l] = min(f[a[i]][l], g[i][l] + c[i]);
		return; 
	}
	int mid = (l + r)>>1;
	solve_(mid + 1, r);
	rep (i, 1, m) 
		calc_(i, l, r);
	solve_(l, mid);
}

int main() {
	rd_(n), rd_(m), rd_(t), rd_(x);
	memset(d, 0x3f, sizeof(d));
	rep (i, 1, n) d[i][i] = 0;
	rep (i, 1, m) {
		rd_(a[i]), rd_(b[i]), rd_(c[i]);
		rep (j, 1, t) rd_(p[i][j]), p[i][j] /= 100000.0;
		d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i]);
 	}
 	rep (k, 1, n) rep (i, 1, n) rep (j, 1, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
 	rep (i, 0, 2*t - 1) f[n][i] = (i > t)*x;
 	rep (i, 1, n - 1) rep (j, t, 2*t - 1) f[i][j] = d[i][n] + x;
 	solve_(0, 2*t - 1);
 	return printf("%.7f\n", f[1][0]), 0;
}