超级玄学错误求助!

P3355 骑士共存问题

AThousandSuns @ 2018-12-14 19:29:43

这是代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    char ch=getchar();int x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
const int d[8][2]={{1,-2},{1,2},{2,-1},{2,1},{-1,-2},{-1,2},{-2,-1},{-2,1}};
int n,m,s,t,el=1,head[44444],cur[44444],to[1444444],flow[1444444],nxt[1444444],dis[44444],q[44444],h,r;
bool block[222][222],vis[222][222];
inline void add(int u,int v,int w){
    if(vis[u][v]) return;vis[u][v]=true;
    to[++el]=v;flow[el]=w;nxt[el]=head[u];head[u]=el;
    to[++el]=u;flow[el]=0;nxt[el]=head[v];head[v]=el;
}
bool bfs(){
    MEM(dis,-1);
    dis[q[h=r=1]=s]=0;
    while(h<=r){
        int u=q[h++];
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(~dis[v] || !flow[i]) continue;
            dis[q[++r]=v]=dis[u]+1;
        }
    }
    return ~dis[t];
}
int dfs(int u,int minres){
    if(u==t || !minres) return minres;
    int f,rtf=0;
    for(int &i=cur[u];i;i=nxt[i]){
        int v=to[i];
        if(dis[v]==dis[u]+1 && (f=dfs(v,min(minres,flow[i])))){
            flow[i]-=f;
            flow[i^1]+=f;
            rtf+=f;
            minres-=f;
            if(!minres) break;
        }
    }
    if(!minres) dis[u]=-1;
    return rtf;
}
int dinic(){
    int flow=0;
    while(bfs()){
        FOR(i,1,n*n+2) cur[i]=head[i];
        flow+=dfs(s,1e9);
    }
    return flow;
}
int main(){
    n=read();m=read();
    FOR(i,1,m){
        int x=read(),y=read();
        block[x][y]=true;
    }
    FOR(i,1,n)
        FOR(j,1,n){
            if(block[i][j]) continue;
            FOR(k,0,7){
                int x=i+d[k][0],y=j+d[k][1];
                if(x<1 || x>n || y<1 || y>n || block[x][y]) continue;
                if((i+j)&1) add((i-1)*n+j,(x-1)*n+y,1);
                else add((x-1)*n+y,(i-1)*n+j,1);
            }
        }
    s=n*n+1;t=n*n+2;
    FOR(i,1,n)
        FOR(j,1,n){
            if(block[i][j]) continue;
            if((i+j)&1) add(s,(i-1)*n+j,1);
            else add((i-1)*n+j,t,1);
        }
    printf("%d\n",n*n-m-dinic());
}

然后我发现输入46 0时,nxt[4448]变成了一个很大的数(1.6*10^7)!

我试着在add中加入

if(el==4448) printf("nxt[4448]=%d\n",nxt[4448]);

结果又输出了"nxt[4448]=0",但是bfs时nxt[4448]还是1.6*10^7!

帮忙看一下吧……调不出了……


by VenusM1nT @ 2018-12-14 19:39:31

@AThousandSuns 你在add函数里输出一下uv的值,再看看你开的vis数组你就知道问题了


by VenusM1nT @ 2018-12-14 19:40:11

我又要说那句话了

十年OI一场空,__________


by VenusM1nT @ 2018-12-14 19:40:48

我用你的代码连建模部分都跑不过去……


by AThousandSuns @ 2018-12-14 19:41:36

@Venus 妈呀,居然犯了这种错……

谢谢大佬~


by VenusM1nT @ 2018-12-14 19:44:54

@AThousandSuns 你数组咋开那么小啊……我做网络流题的原则都是在不MLE的前提下开到3~10倍……


by AThousandSuns @ 2018-12-14 19:46:15

@Venus 我是严格按照最坏情况开的……经过计算的……

果然不是边的就没注意


by VenusM1nT @ 2018-12-14 19:50:38

@AThousandSuns Orz


|