救我......

P3355 骑士共存问题

π酱 @ 2019-07-11 22:18:06

我已经改了2个多小时了,就是找不出来错误QAQ

求大佬帮忙

#include<bits/stdc++.h>
#define Inf 0x7fffffff
using namespace std;
queue<int> Q;
int Ht[9]= {0,-2,-2,-1,-1,1,1,2,2};
int Lt[9]= {0,1,-1,2,-2,2,-2,1,-1};
int a,b,x,X,Y,n,m,New,B,W,Black,White,Start,End,Cnt,Used,Ans,Head[40010],Cur[40010],Dep[40010],To[400010],Next[400010],Val[00010],Map[210][210],Id[210][210];
template<typename T>
int Read(T &x) {
    x=0;
    int f=1;
    char c=getchar();
    while(c!='-'&&!isdigit(c)) {
        c=getchar();
    }
    while(!isdigit(c)) {
        if(c=='-') {
            f=-f;
        }
        c=getchar();
    }
    while(isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    x*=f;
    if(c=='\n') {
        return 1;
    } else {
        return 0;
    }
}
void Write(long long x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) {
        Write(x/10);
    }
    putchar(x%10+'0');
}
inline int Num(int x,int y) {
    return (x-1)*n+y;
}
inline void Add(int a,int b,int x) {
    To[++Cnt]=b;
    Next[Cnt]=Head[a];
    Head[a]=Cnt;
    Val[Cnt]=x;
    To[++Cnt]=a;
    Next[Cnt]=Head[b];
    Head[b]=Cnt;
    Val[Cnt]=0;
}
bool Bfs() {
    memset(Dep,-1,sizeof(Dep));
    Dep[Start]=0;
    Q.push(Start);
    while(!Q.empty()) {
        x=Q.front();
        Q.pop();
        for(int i=Head[x]; i; i=Next[i]) {
            if(Val[i]&&Dep[To[i]]==-1) {
                Dep[To[i]]=Dep[x]+1;
                Q.push(To[i]);
            }
        }
    }
    return Dep[End]!=-1;
}
int Dfs(int x,int f) {
    int w=0,Used=0;
    if(x==End) {
        return f;
    }
    for(int i=Cur[x]; i; i=Next[i]) {
        if(Dep[To[i]]==Dep[x]+1) {
            w=f-Used;
            w=Dfs(To[i],min(Val[i],w));
            Val[i]-=w;
            if(Val[i]) {
                Cur[x]=i;
            }
            Val[i^1]+=w;
            Used+=w;
            if(Used==f) {
                return f;
            }
        }
    }
    if(!Used) {
        Dep[x]=-1;
    }
    return Used;
}
void Dinic() {
    while(Bfs()) {
        for(int i=1; i<=n*n+5; i++) {
            Cur[i]=Head[i];
        }
        Ans+=Dfs(Start,Inf);
    }
}
int main() {
    Ans=0;
    Cnt=1;
    Read(n);
    Read(m);
    for(int i=1; i<=m; i++) {
        Read(X);
        Read(Y);
        Map[X][Y]=1;
    }
    Start=n*n+1;
    End=n*n+2;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(Map[i][j]) {
                continue;
            }
            if((i+j)&1) {
                Add(Start,Num(i,j),1);
                for(int k=1; k<=8; k++) {
                    X=i+Ht[k];
                    Y=j+Lt[k];
                    if((X>n)||(X<1)||(Y<1)||(Y>n)||(Map[X][Y])) {
                        continue;
                    }
                    Add(Num(i,j),Num(X,Y),Inf);
                }
            } 
            else {
                Add(Num(i,j),End,1);
            }
        }
    }
    Dinic();
    Write(n*n-Ans-m);
    return 0;
}

by π酱 @ 2019-07-11 22:43:35

已解决,我傻逼了QAQ


|