一个错误的代码一个ac代码,半天没发现错误,求求大佬帮帮忙!
查看原帖
一个错误的代码一个ac代码,半天没发现错误,求求大佬帮帮忙!
630992
djsavu楼主2022/3/11 16:05
这个是错误的代码
#include<iostream>
#include<algorithm>
//using namespace std;
const int maxn = 2000;
#define inf 1e6
#define ll long long
int n, m, start, end;
struct edge {
	int from;
	int next;
	int val;
	int to;
}edge1[maxn],edge2[maxn];

int next2[maxn], first2[maxn];
int tot2 = 1;
void add2(int u, int v, int val) {//新图,边的序号从2开始
	tot2++;
	edge2[tot2].from = u;
	edge2[tot2].to = v;
	edge2[tot2].val = val;
	edge2[tot2].next = first2[u];
	first2[u] = tot2;
}

int deep[maxn], queue[maxn], left, right;
bool bfs() {
	memset(deep, 0, sizeof(deep));
	queue[left = right = 1] = start + n;
	deep[start + n] = 1;
	while (left <= right) {
		int u = queue[left++];
		for (int p = first2[u]; p; p = next2[p]) {
			int v = edge2[p].to;
			if (edge2[p].val && !deep[v]) {
				deep[v] = deep[u] + 1;
				queue[++right] = v;
			}
		}
	}
	return deep[end];
}

int dfs(int u, int in) {
	if (u == end)
		return in;
	int out = 0;
	for (int p = first2[u]; p&&out<in; p = next2[p]) {
		int v = edge2[p].to;
		if (edge2[p].val&&deep[v] == deep[u] + 1) {
			int res = dfs(v, std::min(edge2[p].val, in - out));
			edge2[p].val -= res;
			edge2[p ^ 1].val += res;
			//in -= res;
			out += res;
		}
	}
	if (out < in)
		deep[u] = -1;
	return out;
}

int main() {

	std::cin >> n >> m >> start >> end;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		std::cin >> u >> v;
		add2(u + n, v, inf);
		add2(v, u + n, 0);
		add2(v + n, u, inf);
		add2(u, v + n, 0);
	}
	int ans = 0;
	while (bfs())
		ans += dfs(start + n, 1e10);
	std::cout << ans << std::endl;
	return 0;
}
这个是ac代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define scanf scanf_s
const int N = 205, M = 5e3 + 5;
int n, m, tot = 1, first[N], to[M], next[M], val[M], dep[N];

void add(int u, int v, int w) {
	to[++tot] = v, next[tot] = first[u], first[u] = tot, val[tot] = w;
}
void addedge(int u, int v, int w) {
	add(u, v, w), add(v, u, 0);
}
int bfs(int s, int t) {
	memset(dep, 0, sizeof(dep));
	std::queue<int> q;
	q.push(s), dep[s] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = first[u]; i; i = next[i]) {
			int v = to[i];
			if (val[i] && !dep[v])
				q.push(v), dep[v] = dep[u] + 1;
		}
	}
	return dep[t];
}
int dfs(int u, int t, int flow) {
	if (u == t)
		return flow;
	int ans = 0;
	for (int i = first[u]; i&&ans < flow; i = next[i]) {
		int v = to[i];
		if (val[i] && dep[v] == dep[u] + 1) {
			int x = dfs(v, t, std::min(val[i], flow - ans));
			if (x)
				val[i] -= x, val[i ^ 1] += x, ans += x;
		}
	}
	if (ans < flow) dep[u] = -1;
	return ans;
}
int dinic(int s, int t) {
	int ans = 0;
	while (bfs(s, t)) {
		int x;
		while ((x = dfs(s, t, 1 << 30))) 
			ans += x;
	}
	return ans;
}
int main() {
	int s, t;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 1; i <= n; ++i)
		addedge(i, i + n, 1);
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		addedge(u + n, v, 1 << 30);
		addedge(v + n, u, 1 << 30);
	}
	printf("%d\n", dinic(s + n, t));
	return 0;
}

第一份代码哪里错了,我看了好久都没看出区别,求求大佬帮帮忙。

2022/3/11 16:05
加载中...