剑雪清寒 @ 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冲