题意分析

首先我们需要求的是统一以后的值\(x\)

并且一般的棋盘操作我们都需要黑白染色

那么对于棋盘格子是偶数的情况的话

答案是存在单调性的

因为如果统一之后两两搭配还是可以再加一个的

如果棋盘格子是奇数的话

那么黑格子数量为\(num1\) 权值和为\(sum1\)

白格子数量为\(num2\) 权值和为\(sum2\)

那么

\[num1*x-sum1=num2*x-sum2\]

然后我们可以使用最大流检验合法性

用源点向黑色的点连边权为\(x-num[i][j]\)的边

白色的点向汇点连边权为\(x-num[i][j]\)的边

然后黑色的点向白色的点连边权为\(inf\)的边

然后检查能否跑满流即可

至于这么做的意义应该很好理解

也就是相邻两个点之间的匹配问题

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 1e18#define N 48#define IL inline#define M 1008611#define D double#define ull unsigned long long#define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/ll opt,n,m,tot=1,S,T,maxn;ll sum1,sum2,num1,num2,all;ll hei[N][N],bel[N][N];ll to[M],nex[M],head[N*N],fro[M];ll w[M];ll dep[N*N],cur[N*N];queue
                    
                      Q;ll tx[6]={0,0,0,1,-1},ty[6]={0,1,-1,0,0};IL void add(ll x,ll y,ll z){to[++tot]=y;fro[tot]=x;nex[tot]=head[x];head[x]=tot;w[tot]=z;swap(x,y);to[++tot]=y;fro[tot]=x;nex[tot]=head[x];head[x]=tot;w[tot]=0;}IL bool safe(ll x,ll y){return x>=1&&x<=n&&y>=1&&y<=m;}IL ll id(ll x,ll y){return (x-1)*m+y;}IL bool bfs(){ for(R ll i=1;i<=T;++i) dep[i]=0; Q.push(S);dep[S]=1; for(;!Q.empty();) { ll u=Q.front();Q.pop(); for(R ll i=head[u];i;i=nex[i]) { ll v=to[i]; if(w[i]>0&&dep[v]==0) { dep[v]=dep[u]+1;Q.push(v); } } } return dep[T]!=0;}IL ll dfs(ll now,ll res){ if(now==T||!res) return res; for(R ll &i=cur[now];i;i=nex[i]) { ll v=to[i]; if(w[i]>0&&dep[v]==dep[now]+1) { ll have=dfs(v,min(w[i],res)); if(have>0) { w[i]-=have;w[i^1]+=have; return have; } } } return 0;}IL void Dinic(){ while(bfs()) {// printf("now nowno\n"); for(R ll i=1;i<=T;++i) cur[i]=head[i]; ll d=dfs(S,inf);// printf("now now now %lld\n",d); while(d) all+=d,d=dfs(S,inf); }}IL bool check(ll now){ tot=1;all=0;ll tmp=0; memset(head,0,sizeof head); for(R ll i=1;i<=n;++i) for(R ll j=1;j<=m;++j) if((i+j)&1) add(S,id(i,j),now-hei[i][j]),tmp+=(now-hei[i][j]); else add(id(i,j),T,now-hei[i][j]); for(R ll i=1;i<=n;++i) for(R ll j=1;j<=m;++j) if((i+j)&1) for(R ll k=1;k<=4;++k) { ll nowx=i+tx[k],nowy=j+ty[k]; if(safe(nowx,nowy)) add(id(i,j),id(nowx,nowy),inf); }// printf("now is %lld but need is %lld\n",all,tmp); Dinic(); // printf("now is %lld but need is %lld\n",all,tmp); return (all==tmp);}IL void solve_cdy(){ ll le=maxn,ri=1e15,ans=-1; while(le<=ri) {// printf("%lld %lld\n",le,ri); ll mid=(le+ri)>>1; if(check(mid)) ans=mid,ri=mid-1; else le=mid+1; }// printf("%d\n",ans); if(ans==-1) puts("-1"); else printf("%lld\n",(ans*num1)-sum1);}IL void solve_wzy(){ if((sum1-sum2)%(num1-num2)==0) { ll tox=(sum1-sum2)/(num1-num2);// printf("tox si %d\n",tox); if(tox<1ll*maxn) {puts("-1");return;} if(check(tox)) printf("%lld\n",(tox*num1)-sum1); else puts("-1"); } else puts("-1");}int main(){// freopen("222.in","r",stdin);// freopen("222.out","w",stdout); read(opt); while(opt--) { maxn=0;sum1=sum2=num1=num2=0; read(n);read(m);S=n*m+1;T=n*m+2; for(R ll i=1;i<=n;++i) for(R ll j=1;j<=m;++j) read(hei[i][j]),maxn=max(maxn,hei[i][j]); for(R ll i=1;i<=n;++i) for(R ll j=1;j<=m;++j) { bel[i][j]=((i+j)&1); if(bel[i][j]) num1++,sum1+=hei[i][j]; else num2++,sum2+=hei[i][j]; }// printf("%lld %lld %lld %lld\n",num1,sum1,num2,sum2); if(num1==num2) solve_cdy(); else solve_wzy(); }// fclose(stdin);// fclose(stdout); return 0;}

HEOI 2019 RP++

转载于:https://www.cnblogs.com/LovToLZX/p/10648722.html

你可能感兴趣的文章