UKE求助!!!!求调
查看原帖
UKE求助!!!!求调
361794
Gyan楼主2021/8/25 20:28

不是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更不知道为什么.......

UKE

求大佬点破天机

2021/8/25 20:28
加载中...