WA on#67 dinic求助
查看原帖
WA on#67 dinic求助
582360
UniGravity楼主2023/12/15 21:03
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3f, N = 100005;

int n, k, s, t, ms, me;
int tot = 1, vis[N], dis[N], to[N], nxt[N], now[N], head[N], flow[N], cost[N];

inline void add(int u, int v, int f, int c) {
	to[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	flow[tot] = f;
	cost[tot] = c;
}

// about SPFA, it isn't dead.
inline bool SPFA() {
	for (int i = 0; i <= n + 1; i++) {
		dis[i] = INF;
		vis[i] = 0;
		now[i] = head[i];
	}
	queue< int > q;
	q.push(s);
	dis[s] = 0, vis[s] = 1;
	int x, y, w;
	while (!q.empty()) {
		x = q.front();
		q.pop();
		vis[x] = 0;
		for (int i = head[x]; i; i = nxt[i]) {
			y = to[i], w = cost[i];
			if (flow[i] && dis[y] > dis[x] + w) {
				dis[y] = dis[x] + w;
				if (!vis[y]) {
					q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
	return dis[t] != INF;
}

int res = 0;

inline int dinic(int u, int nowf) {
//	printf("dinic %d %d\n", u, nowf);
	if (u == t) return nowf;
	vis[u] = 1;
	int ans = 0, y, f1;
	for (int i = now[u]; i && ans < nowf; i = nxt[i]) {
		now[u] = i;
		y = to[i];
		if (!vis[y] && flow[i] && dis[y] == dis[u] + cost[i]) {
			f1 = dinic(y, min(flow[i], nowf - ans));
			if (f1) {
				res += f1 * cost[i];
				flow[i] -= f1;
				flow[i ^ 1] += f1;
				ans += f1;
			}
		}
	}
	vis[u] = 0;
	return ans;
}

inline int maxcostmaxflow() {
	int ans = 0, x;
	while (SPFA()) {
		while ((x = dinic(s, INF))) ans += x;
	}
	return ans;
}

inline void adde(int u, int v, int f, int c) {
//	printf("%d\t%d\t%d\t%d\n", u, v, f, c);
	add(u, v, f, c);
	add(v, u, 0, -c);
}

int S[N], E[N];
int id[N];

signed main() {
	scanf("%lld %lld %lld %lld", &n, &k, &ms, &me);
	int ans = 0;
	for (int i = 1; i <= n; i++) scanf("%lld", &S[i]), ans += S[i];
	for (int i = 1; i <= n; i++) scanf("%lld", &E[i]);
	s = 0, t = n + 1;
	int f = k - ms;
	for (int i = 1; i < k; i++) adde(i, i + 1, f, 0), id[i] = tot - 1; // sleep
	for (int i = k; i <= n; i++) adde(i, i + 1, f - me, 0), id[i] = tot - 1; // sleep
	adde(s, 1, f, 0); // sleep
	for (int i = 1; i <= n; i++) adde(i, min(i + k, t), 1, S[i] - E[i]); // eat
	int x = maxcostmaxflow();
	printf("%lld\n", ans - res);
//	for (int i = 1; i <= n; i++) printf("%d ", id[i]);
//	for (int i = 1; i <= n; i++) printf("%d ", flow[i * 2]);
//	for (int i = 1; i <= n; i++) printf(flow[i * 2] ? "S" : "E");
	for (int j = 1; j <= n; j++) {
		bool fg = false;
		for (int i = head[j]; i; i = nxt[i]) {
			if (cost[i] == S[j] - E[j] && to[i] == min(j + k, t)) {
				fg = flow[i];
			}
		}
		printf(fg ? "S" : "E");
	}
	return 0;
}
2023/12/15 21:03
加载中...