社区讨论
为什么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 条回复,欢迎继续交流。
正在加载回复...