关于建模的一点疑问
查看原帖
关于建模的一点疑问
214728
剑雪清寒楼主2022/9/13 20:15

在我代码中的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;
}
2022/9/13 20:15
加载中...