目前对于样例,可以通过合法方案,请大家帮助验证。
#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.");
}
}
}