社区讨论

为什么RE了?

P4001[ICPC-Beijing 2006] 狼抓兔子参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@locnmrw1
此快照首次捕获于
2023/10/30 16:45
2 年前
此快照最后确认于
2023/11/05 03:46
2 年前
查看原帖
这样写为什么会莫名其妙的第3个点和第5个点RE?
CPP
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffff
#define maxn 2000005
#define int long long
int px[10] = {0,0,0,1,-1,-1,1};
int py[10] = {0,1,-1,1,-1,0,0};
int read(){
	int x = 0,f = 1;
	char s = getchar();
	while(s < '0' || s > '9'){
		if(s == '-') f = -1;
		s = getchar();
	}
	while(s >= '0' && s <= '9'){
		x = (x << 1) + (x << 3) + s - '0';
		s = getchar();
	}
	return x * f;
}
struct node{
	int next,to,w;
}a[maxn];
int n,m,sum,tot = 1,L,head[maxn],cur[maxn],dep[maxn],sign[maxn];
queue<int> p;
void add(int u,int v,int w){
	a[++tot].next = head[u],a[tot].to = v,a[tot].w = w,head[u] = tot;
	a[++tot].next = head[v],a[tot].to = u,a[tot].w = 0,head[v] = tot;
}
void build(){
	n = read();m = read();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j < m; j++){
			L = read();
			add((i - 1) * m + j,(i - 1) * m + j + 1,L);
			add((i - 1) * m + j + 1,(i - 1) * m + j,L);
		}
	}
	for(int i = 1; i < n; i++){
		for(int j = 1; j <= m; j++){
			L = read();
			add((i - 1) * m + j,i * m + j,L);
			add(i * m + j,(i - 1) * m + j,L);
		}
	}
	for(int i = 1; i < n; i++){
		for(int j = 1; j < m; j++){
			L = read();
			add((i - 1) * m + j,i * m + j + 1,L);
			add(i * m + j + 1,(i - 1) * m + j,L);
		}
	}
}
bool bfs(int s,int t){
	for(int i = n * m; i >= 1; i--) cur[i] = head[i],dep[i] = inf;
	dep[s] = 1;p.push(s);
	while(!p.empty()){
		int u = p.front();p.pop();
		for(int i = cur[u]; i; i = a[i].next){
			int v = a[i].to;
			if(dep[v] < inf || !a[i].w) continue;
			dep[v] = dep[u] + 1;
			p.push(v);
		}
	}
	return dep[t] < inf;
}
int dfs(int u,int lim){
	if(u == n * m) return lim;
	int rf = 0,f = 0;
	sign[u] = 1;
	for(int i = cur[u]; i; i = a[i].next){
		int v = a[i].to;cur[u] = i;
		if(!a[i].w || sign[v] || dep[u] != dep[v] - 1) continue;
		rf = dfs(v,min(lim,a[i].w));
		f += rf,lim -= rf,a[i].w -= rf,a[i ^ 1].w += rf;
		if(!lim) continue;
	}
	sign[u] = 0;
	return f;
}
signed main(){
	build();
	while(bfs(1,n * m)) sum += dfs(1,inf);
	printf("%lld",sum);
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...