不是RE就是UKE,甚至连WA的点都没有 网络流dinic+弧优化
#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e6;
const int INF = 0x3f3f3f3f;
int head[N], nxt[N], to[N], tot(1), /*from[NoE],*/ cap[N];
int s, t;
int cur[N], layer[N];
inline void add(int x, int y, int z) {
nxt[++tot]=head[x], head[x]=tot, /*from[tot]=x,*/ to[tot]=y, cap[tot]=z;
nxt[++tot]=head[y], head[y]=tot, /*from[tot]=y,*/ to[tot]=x, cap[tot]=0;
}
inline bool bfs() {
for (int i(s); i<=t; ++i)
cur[i]=head[i], layer[i]=-1;
layer[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int x(q.front());
q.pop();
for (int e(head[x]), tmp(layer[x]+1); e; e=nxt[e]) {
int y(to[e]);
if (cap[e] && layer[y]==-1) {
layer[y] = tmp;
q.push(y);
if (y==t) return 1;
}
}
}
return 0;
}
int dfs(int x, int f) {
if (x==t) return f;
int res(0);
for (int &e(cur[x]); e; e=nxt[e]) {
int y(to[e]);
if (cap[e] && layer[y]>layer[x]) {
int dlt(dfs(y, min(cap[e], f-res)));
if (dlt) {
cap[e]-=dlt, cap[e^1]+=dlt;
res += dlt;
if (res==f) return res;
}
}
}
layer[x]=-1;
return res;
}
inline int dinic() {
int ans(0);
while (bfs())
ans += dfs(s, INF);
printf("ans=%d\n", ans);
return ans;
}
int main()
{
//freopen("P2763.in", "r", stdin);
int n, k, m(0);
scanf("%d%d", &k, &n);
s=0, t=n+k+1;
for (int i(1); i<=n; ++i)//2~2n+1
add(s, i, 1);
for (int i(n+1), x; i<t; ++i) {//2n+2~2nv+1
scanf("%d", &x);
m += x;
add(i, t, x);
}
for (int i(1), p, tp; i<=n; ++i) {//2nv+2~ne+1
scanf("%d", &p);
while (p--) {
scanf("%d", &tp);
add(i, tp, 1);
}
// add(s, i, 1);
}
if (dinic() != m) {
puts("No Solution!");
return 0;
}
/*
for (int i(n+1); i<t; ++i) {
printf("%d:", i-n);
for (int e(head[i]); e; e=nxt[e]) {
if (to[e] < i)
if (cap[e]) {
printf(" %d", to[e]);
}
}
putchar('\n');
}
*/
return 0;
}
可以先不用看后面输出方案的部分
本地测试样例方案数总是0,调了好久也不知道为什么,交上洛谷就UKE或者RE更不知道为什么.......
求大佬点破天机