关于建模的一点疑问

P3355 骑士共存问题

剑雪清寒 @ 2022-09-13 20:15:18

在我代码中的98行,若使用 if((i+j)&1)==0就18pts,而若是if((i+j)&1)则AC,可是我觉得这两种实际结果区别不大,球球解答

以下完整代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
    long long x;bool f;char ch;
    for(f=0;!isdigit(ch=getchar());f=ch=='-');
    for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
    return f?-x:x;
}
inline void print(long long x,char las) {
    if(!x) {
        putchar(48),putchar(las);
        return ;
    }
    if(x<0) putchar('-'),x=-x;
    int ls[20],k=0;
    while(x) ls[++k]=x%10,x/=10;
    while(k) putchar(ls[k--]+48);
    putchar(las);
    return ;
}
int n=read(),m=read(),s,t,ans,dist[40050],cnt[40050];
int ux[8]={1,1,-1,-1,2,2,-2,-2};
int uy[8]={2,-2,2,-2,1,-1,1,-1};
inline int get(int x,int y) {
    return x*n-n+y;
}
struct edge {
    int to,name;int lim;
    edge *next;
};
struct graph {
    int rs;edge *head[40050],rd[200500];
    inline void add(int u,int v,long long lim) {
        rd[rs].to=v;rd[rs].lim=lim;rd[rs].name=rs;rd[rs].next=head[u];head[u]=&rd[rs++];
    }
}g1,g2;
inline void st() {
    for(int i=0;i<=n*n;i++) dist[i]=-1;
    queue<int>que;que.push(t);cnt[0]=1;
    while(!que.empty()) {
        int now=que.front();que.pop();
        for(edge *i=g2.head[now];i;i=i->next) {
            int nex=i->to;
            if(dist[nex]!=-1) continue;
            dist[nex]=dist[now]+1;que.push(nex);cnt[dist[nex]]++;
        }
    }
    return ;
}
inline int ISAP(int x,int lim) {
    if(x==t) {
        ans-=lim;
        return lim;
    }
    int used=0;
    for(edge *i=g1.head[x];i;i=i->next) {
        int nex=i->to;
        if(i->lim && dist[nex]+1==dist[x]) {
            int cost=ISAP(nex,min(i->lim,lim-used));
            if(cost) {
                i->lim-=cost;
                g2.rd[i->name].lim+=cost;
                used+=cost;
                if(used==lim) return used;
            }
        }
    }
    for(edge *i=g2.head[x];i;i=i->next) {
        int nex=i->to;
        if(i->lim && dist[nex]+1==dist[x]) {
            int cost=ISAP(nex,min(i->lim,lim-used));
            if(cost) {
                i->lim-=cost;
                g1.rd[i->name].lim+=cost;
                used+=cost;
                if(used==lim) return used;
            }
        }
    }
    cnt[dist[x]]--;
    if(!cnt[dist[x]]) dist[s]=n+1;
    dist[x]++;
    cnt[dist[x]]++;
    return used;
}
bitset<201>in[201];
signed main() {
    s=0;t=n*n+1;
    for(int i=1;i<=m;i++) {
        int x=read(),y=read();
        in[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
            if(in[i][j]) continue;
            ans+=1;
            if((i+j)&1) g1.add(get(i,j),t,1),g2.add(t,get(i,j),0);
            else {
                g1.add(s,get(i,j),1),g2.add(get(i,j),s,0);
                for(int l=0;l<8;l++) {
                    int xx=i+ux[l],yy=j+uy[l];
                    if(xx<1 || yy<1 || xx>n || yy>n) continue;
                    if(in[xx][yy]) continue;
                    g1.add(get(i,j),get(xx,yy),INT_MAX),g2.add(get(xx,yy),get(i,j),0);
                }
            }
        }
    st();
    n=n*n+1;
    while(dist[s]<n) ISAP(s,INT_MAX);
    print(ans,'\n');
    return 0;
}

by cymrain07 @ 2022-11-28 23:02:45

& 的优先级甚至比 == 还低

曾经我的惨痛经历


by cymrain07 @ 2022-11-28 23:03:08

@剑雪清寒


by 剑雪清寒 @ 2022-12-04 20:12:46

@cymrain07 thx,不过退役


by cymrain07 @ 2022-12-04 20:15:58

@剑雪清寒 祝好 whk冲


|