写了本题的 SPJ
查看原帖
写了本题的 SPJ
434929
Usada_Pekora楼主2022/6/3 19:38

目前对于样例,可以通过合法方案,请大家帮助验证。

#include "testlib.h"
#include <string>
#include <vector>
#include <queue>
#include <iostream>
const int N = 1005, M = 105;
double c[N];
int dep[N], s, t, fir[N + M], nxt[(N + M) << 2], to[(N + M) << 2], flow[(N + M) << 2], cnt = 1;
bool e[N][M];
inline void add(int u, int v, int f) {
	to[++cnt] = v;
	flow[cnt] = f;
	nxt[cnt] = fir[u];
	fir[u] = cnt;
}
inline bool bfs() {
	memset(dep, 0, sizeof dep);
	dep[t] = 1;
	std::queue<int> q;
	q.push(t);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = fir[u]; i; i = nxt[i]) {
			if(flow[i] && !dep[to[i]]) {
				q.push(to[i]);
				dep[to[i]] = dep[u] + 1;
			}
		}
	}
	return dep[s] > 0;
}
inline int min(int x, int y) {
	return x < y ? x : y;
}
inline int dfs(int u, int in) {
	if(u == s) return in;
	int out = 0, res;
	for(int i = fir[u]; i && in; i = nxt[i]) {
		if(dep[to[i]] == dep[u] + 1 && flow[i]) {
			res = dfs(to[i], min(in, flow[i]));
			flow[i] -= res, flow[i ^ 1] += res, in -= res, out += res;
		}
	}
	if(out == 0) dep[u] = 0;
	return out;
}
inline int dinic() {
	int res = 0;
	while(bfs()) res += dfs(t, 1e9);
	return res;
}
int main(int argc, char* argv[]) {
	registerTestlibCmd(argc, argv);
	int std_ans = ans.readInt();
	int my_ans = ouf.readInt();
	if(std_ans == -1) {
		if(my_ans == -1) {
			quitf(_ok, "The answer is correct.");
		} else quitf(_wa, "The answer is wrong: expected = %d, found = %d.", std_ans, my_ans);
	} else {
		std::vector<int> vec_ans;
		vec_ans.push_back(my_ans);
		int n = inf.readInt(), m = inf.readInt();
		for(int i = 1; i < m; i++) my_ans = ouf.readInt(), vec_ans.push_back(my_ans);
		if(vec_ans.size() != m) quitf(_wa, "The answer is wrong : too short.");
		else {
			for(int i = 1; i <= m; i++) {
				int cnt = inf.readInt();
				for(int j = 1; j <= cnt; j++) {
					int x = inf.readInt(); 
					c[x] += 1.0 / cnt;
					e[x][i] = 1;
				}
			}
			s = 0, t = n + m + 1;
			for(int i = 1; i <= n; i++) {
				int f = ceil(c[i]);
				add(i, s, f), add(s, i, 0);
			}
			for(int i = 1; i <= m; i++)
				add(t, i + n, 1), add(i + n, t, 0);
			for(int i = 1; i <= m; i++) {
				int mat = vec_ans[i - 1];
				if(mat < 1 || mat > n || !e[mat][i]) quitf(_wa, "The answer is wrong.");
				add(i + n, mat, 1), add(mat, i + n, 0);
			}
			int maxf = dinic();
			if(maxf == m) quitf(_ok, "The answer is correct.");
			else quitf(_wa, "The answer is wrong.");
		}
	}
}
2022/6/3 19:38
加载中...