P3254 90分 最后一个点WA 调了很久还是没发现什么问题 于是向大佬求助
查看原帖
P3254 90分 最后一个点WA 调了很久还是没发现什么问题 于是向大佬求助
112917
Eason_AC楼主2020/8/19 23:37

RT

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;

int m, n, r[157], c[247], h[200007], cnt = 1/**/, tot, t = 9007, dis[100007], zz[507][507], vis[507];
struct edge {
	int v, to, nxt;
}e[5000007];

inline void a_e(int u, int v, int w) {
	e[++cnt] = (edge){w, v, h[u]}; h[u] = cnt;
	e[++cnt] = (edge){0, u, h[v]}; h[v] = cnt;
}
inline bool bfs() {
	queue<int> q;
	memset(dis, 0, sizeof(dis));
	q.push(0);
	dis[0] = 1;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(int i = h[x]; i; i = e[i].nxt) {
			int y = e[i].to, z = e[i].v;
			if(!dis[y] && z) {
				dis[y] = dis[x] + 1;
				q.push(y);
			}
		}
	}
	return dis[t];
}
inline int dfs(int u, int minflow) {
	if(u == t || !minflow)	return minflow;
	int s = 0;
	for(int i = h[u]; i; i = e[i].nxt) {
		int y = e[i].to;
		if(dis[y] == dis[u] + 1 && e[i].v) {
			int floww = dfs(y, min(e[i].v, minflow));
			if(floww) {
				s += floww;
				minflow -= floww;
				e[i].v -= floww;
				e[i ^ 1].v += floww;
				if(!minflow)	break;	//错点1:最小流为0,此时不需要再查找了,直接跳出 
			}
		}
	}
	if(!s)	dis[u] = -1;
	return s;
}
inline int NetFlow() {
	int ans = 0;
	while(bfs())	ans += dfs(0, 0x3f3f3f3f);
	return ans;	
}

int main() {
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= m; ++i) {
		scanf("%d", &r[i]);
		a_e(0, i, r[i]);
		for(int j = 1; j <= n; ++j)
			a_e(i, j + m, 1);
		tot += r[i];
	}
	for(int i = 1; i <= n; ++i)	{
		scanf("%d", &c[i]);
		a_e(i + m, t, c[i]);
	}
	if(NetFlow() == tot)	puts("1");
	else {
		printf("0");
		return 0;
	}
	for(int j = 1; j <= m/*错点2:<-cnt!太粗心了我qwq*/; ++j)
		for(int i = h[j]; i; i = e[i].nxt) {
			if(e[i].to >= m + 1 && e[i].to <= m + n/*判断是否是桌子*/ && !e[i].v) {
				zz[j][e[i].to - m] = 1;
			}
		}
	for(int i = 1; i <= m; ++i) {
		memset(vis, 0, sizeof(vis));
		for(int j = 1; j <= r[i]; ++j)
			for(int k = 1; k <= n; ++k)
				if(!vis[k] && zz[i][k]) {
					vis[k] = 1;
					printf("%d ", k);
					break;
				}
		puts("");
	}
	return 0;
}
2020/8/19 23:37
加载中...