P5038 奇怪的游戏

题目询问了一个不能确定的时间，所以显然做法中要包含一个二分答案。

我们将整张图分为黑白点两种，黑点旁边的点就是白点，白点旁边的点就是黑点，想一下就能知道，每次操作会使黑白点的数字各加一，而我们的目的就是让整张图的黑白点都是同一个数字。

设这个数字是 \(x\)，黑点有 \(num_0\) 个，未操作前的数字总和是 \(sum_0\)，白点有 \(num_1\) 个，未操作前的数字总和是 \(sum_1\)，因为操作次数相等，

那么有：

\[num_0\times x-sum_0=num_1\times x-sum_1
\]

移项可得：

\[x=(sum_1-sum_0)/(num_1-num_0)
\]

于是：

当 \(num_1 \not= num_0\) 时，可以解出 \(x\)，若它是个小数则无解。另外我们要操作的次数为 \((x\times n\times m-sum_1-sum_0)/2\) ，所以如果这也是一个小数也无解，接着我们用网络流 \(check\) 一下 \(x\)，得出它能操作多少次，和上面算的一样就有解，否则无解。
\(num_1=num_0\) 显然这说明 \(n,m\) 中至少一个是偶数，操作次数还是 \((x\times n\times m-sum_1-sum_0)/2\)，前一项是偶数，后两项算一下如果是奇数，那么算出次数一定是小数，也无解，否则我们就可以利用单调性二分出合适的 \(x\) ，利用网络流得出答案。

单调性证明：

因为 \(num_1=num_0\)，则

\[(num_1+num_0)\bmod 2=0
\]

即可以构造一层正好的满覆盖。也就是在正确答案后多铺了几层。所以具有单调性。

于是本题就愉快的做完了～

Code

#include<cstring>

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

namespace EMT{

	typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;

	#define int long long

	#define pf printf

	#define F(i,a,b) for(register int i=a;i<=b;i++)

	#define D(i,a,b) for(register int i=a;i>=b;i--)

	inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}

	inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}

	inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}

	inline void pi(int x){pf("%lld ",x);}inline void pn(){pf("\n");}

	const int N=1650;struct dp{int num,sum;}p[2];const int inf1=1e18,inf2=1e14;

	int head[N],dis[N],co,Hd[N],n,pos[45][45],q[N],hd,tot,tl,cnt,m,S,T,a[45][45],b[45][45];struct node{int next,to,w;}e[N*10];

	inline void add(int next,int to,int w){e[++co].next=head[next],e[co].to=to,e[co].w=w,head[next]=co;}

	inline bool bfs(){

		memcpy(head,Hd,sizeof(Hd));

		memset(dis,0x3f,sizeof(dis));

		q[hd=tl=1]=S;dis[S]=0;

		while(hd<=tl){

			int x=q[hd++];

			for(register int i=head[x];i;i=e[i].next)if(e[i].w){

				if(dis[e[i].to]>dis[x]+1){

					dis[e[i].to]=dis[x]+1;

					q[++tl]=e[i].to;

				}

			}if(x==T)return 1;

		}return 0;

	}

	inline int dfs(int x,int in){

		if(x==T)return in;

		int rest=in,go;

		for(register int i=head[x];i;head[x]=i=e[i].next)if(e[i].w){

			if(dis[e[i].to]==dis[x]+1){

				go=dfs(e[i].to,min(e[i].w,rest));

				if(go)e[i].w-=go,e[i^1].w+=go,rest-=go;

				else dis[e[i].to]=0;

			}if(!rest)break;

		}return in-rest;

	}

	inline int check(int x){

		int ans=0;co=1;

		memset(head,0,sizeof(head));tot=x*n*m-p[0].sum-p[1].sum;

		F(i,1,n)

			F(j,1,m)

			if(b[i][j]){

				if(j+1<=m)add(pos[i][j],pos[i][j+1],inf1),add(pos[i][j+1],pos[i][j],0);

				if(j-1>=1)add(pos[i][j],pos[i][j-1],inf1),add(pos[i][j-1],pos[i][j],0);

				if(i-1>=1)add(pos[i][j],pos[i-1][j],inf1),add(pos[i-1][j],pos[i][j],0);

				if(i+1<=n)add(pos[i][j],pos[i+1][j],inf1),add(pos[i+1][j],pos[i][j],0);

				add(S,pos[i][j],x-a[i][j]);add(pos[i][j],S,0);

			}else add(pos[i][j],T,x-a[i][j]),add(T,pos[i][j],0);

		memcpy(Hd,head,sizeof(head));

		while(bfs())ans+=dfs(S,inf1);

		if(ans>=tot/2)return ans;else return 0;

	}

	inline short main(){

		int TT=read();

		while(TT--){

			cnt=0;n=read(),m=read();S=++cnt;T=++cnt;int maxn=0;

			p[0].num=p[0].sum=p[1].num=p[1].sum=0;

			F(i,1,n)

				F(j,1,m){

					if(j==1)b[i][j]=b[i-1][j]^1;else b[i][j]=b[i][j-1]^1;

					p[b[i][j]].num++;pos[i][j]=++cnt;

					a[i][j]=read();p[b[i][j]].sum+=a[i][j];

					maxn=max(maxn,a[i][j]);

				}

			if(p[1].num!=p[0].num){

				if((p[1].sum-p[0].sum)%(p[1].num-p[0].num)!=0){pi(-1);pn();}

				int tt=(p[1].sum-p[0].sum)/(p[1].num-p[0].num);

				int x;

				if(tt!=(int)tt){pi(-1);pn();continue;}else x=tt;

				if((x*n*m-p[1].sum-p[0].sum)&1||x*n*m<p[1].sum+p[0].sum){pi(-1);pn();continue;}

				if(!check(x)){pi(-1);pn();}

				else{pi(check(x));pn();}

			}else{

				int l=maxn,r=inf2,ans=inf2;

				if((p[0].sum+p[1].sum)&1){pi(-1);continue;}

				while(l<=r){

					int mid=(l+r)>>1;

					int t=check(mid);

					if(t)r=mid-1,ans=t;

					else l=mid+1;

				}

				if(ans==inf2){pi(-1);pn();continue;}

				else pi(ans),pn();

			}

		}

		return 0;

	}

}

signed main(){return EMT::main();}

巴特西

P5038 奇怪的游戏

Code

最新文章

热门文章