NC21855. Problem M. Wpremig和Jhadgre的藏宝图
描述
Jhadgre在生日那天收到了一张神秘的藏宝图，于是他决定和Wpremig分享这张藏宝图，并且去寻宝！
这张藏宝图上总共有N行，每行有M个格子，共N*M个格子，每个格子上写了一个数字。
藏宝图上写了一段字：神秘的有缘人啊，这些格子已经被其他人挖过了，我已经替你标出了所有格子被挖到的深度，并且在这个宝藏上加了一个魔法，只要你把所有格子都挖到同一个深度，宝藏自然就会出现。
这看似是一个很简单的问题，只要知道现在最深的那个格子，其他格子都挖到这个深度，就是最快的方式了。然而Wpremig和Jhadgre却发现，还有一句话：我知道你们有两个人，所以你们在挖的时候必须两个人同时各挖一个格子，并且这两个格子必须相邻！
这就比较尴尬了，Wpremig和Jhadgre很不高兴，这是送礼呢还是膈应人呢？不挖了！
虽然这样说，但是人总是会遵循“真香定理”。在几天后Wpremig和Jhadgre还是决定去挖宝藏，现在他们在出发前想知道，最少需要挖多少次才能获得宝藏呢？（假设每次一个人挖一个格子可以将这个格子的深度+1）
输入描述
第一行一个整数T表示数据组数（T<=10）
对于每组数据，第一行两个整数N,M。
接下去N行每行M个整数。
保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000
输出描述
对于每组数据输出最少的挖掘次数，若无论如何都不能获得宝藏，则输出-1；
示例1
输入:
1 2 2 1 2 2 3
输出:
2
C++14(g++5.4) 解法, 执行用时: 1169ms, 内存消耗: 732K, 提交时间: 2019-01-04 14:53:05
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int s=1690,t=1691;
const LL oo2=1e17,oo1=1e13,oo3=1e15;
int a[50][50],num[50][50],xx[]={0,0,1,-1},yy[]={1,-1,0,0},
fir[1700],ne[10010],to[10010],que[1700],f[1700],
m,n,tot;
LL w[10010];
bool ok(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
void init()
{
int i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
void add(int u,int v,LL x)
{
tot++;
ne[tot*2]=fir[u];
fir[u]=tot*2;
to[tot*2]=v;
w[tot*2]=x;
ne[tot*2+1]=fir[v];
fir[v]=tot*2+1;
to[tot*2+1]=u;
w[tot*2+1]=0;
}
bool find()
{
int hd=1,tl=1,i,u,v;
que[1]=s;
memset(f,0,sizeof(f));
f[s]=1;
while (hd<=tl)
{
u=que[hd++];
for (i=fir[u];i;i=ne[i])
if (w[i]&&!f[v=to[i]])
{
f[v]=f[u]+1;
que[++tl]=v;
}
}
return f[t];
}
LL dfs(int u,LL lim)
{
int i,v;
LL ret=0,x;
if (u==t) return lim;
for (i=fir[u];i&&ret<lim;i=ne[i])
if (w[i]&&f[v=to[i]]==f[u]+1)
{
x=dfs(v,min(lim-ret,w[i]));
ret+=x;
w[i]-=x;
w[i^1]+=x;
}
if (!ret) f[u]=0;
return ret;
}
bool ok(LL x)
{
int i,j,kk,x1,y1;
tot=0;
memset(fir,0,sizeof(fir));
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (i+j&1) add(s,num[i][j],x-a[i][j]);
else add(num[i][j],t,x-a[i][j]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (i+j&1)
for (kk=0;kk<4;kk++)
if (ok(x1=i+xx[kk],y1=j+yy[kk]))
add(num[i][j],num[x1][y1],oo3);
while (find())
{
int xxx;
xxx=1;
while (dfs(s,oo2));
}
for (i=fir[s];i;i=ne[i])
if (w[i]) return 0;
return 1;
}
void solve1()
{
int i,j;
LL s0=0,s1=0,x;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (i+j&1) s1+=a[i][j];
else s0+=a[i][j];
x=s0-s1;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (a[i][j]>x)
{
printf("-1\n");
return;
}
if (!ok(x)) printf("-1\n");
else printf("%lld\n",(x*m*n-s0-s1)/2);
}
void solve0()
{
int i,j;
LL s0=0,s1=0,x,l,r,mid;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (i+j&1) s1+=a[i][j];
else s0+=a[i][j];
if (s0!=s1)
{
printf("-1\n");
return;
}
l=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
l=max(l,(LL)a[i][j]);
r=oo1;
while (l<r)
{
mid=(l+r)/2;
if (ok(mid)) r=mid;
else l=mid+1;
}
if (l==oo1) printf("-1\n");
else printf("%lld\n",(l*m*n-s0-s1)/2);
}
int main()
{
int T,i,j;
for (i=1;i<=40;i++)
for (j=1;j<=40;j++)
num[i][j]=i*40+j;
scanf("%d",&T);
while (T--)
{
init();
if (m*n&1) solve1();
else solve0();
}
}
C++11(clang++ 3.9) 解法, 执行用时: 1619ms, 内存消耗: 1628K, 提交时间: 2018-12-24 10:29:28
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int edgenum,head[200005],nex[200005],vet[200005],dep[200005],q[200005],cur[200005];
int n,m,S,T,D;
long long w[105][105],val[200005],sx,sy,mx;
inline void addedge(int u,int v,long long co)
{
edgenum++,vet[edgenum]=v,val[edgenum]=co,nex[edgenum]=head[u],head[u]=edgenum;
edgenum++,vet[edgenum]=u,val[edgenum]=0,nex[edgenum]=head[v],head[v]=edgenum;
}
inline int id(int i,int j)
{
return (i-1)*m+j;
}
bool bfs(int s,int t)
{
for (int i=1;i<=D;i++) dep[i]=-1;
int he=1,ta=1;
q[1]=s;dep[s]=0;
while (he<=ta)
{
int u=q[he];
for (int e=head[u];e!=0;e=nex[e])
{
int v=vet[e];
if (dep[v]==-1 && val[e]>0)
dep[v]=dep[u]+1,ta++,q[ta]=v;
}
he++;
}
return dep[t]!=-1;
}
long long dfs(int s,int t,long long f)
{
if (s==t) return f;
long long used=0;
for (int &e=cur[s];e!=0;e=nex[e])
{
int v=vet[e];
if (dep[v]==dep[s]+1 && val[e]>0)
{
long long d=dfs(v,t,min(f-used,val[e]));
val[e]-=d,val[e^1]+=d,used+=d;
if (used==f) return used;
}
}
return used;
}
long long dinic(int s,int t)
{
long long ans=0;
while (bfs(s,t))
{
memcpy(cur,head,sizeof(cur));
ans+=dfs(s,t,10000000000000ll);
}
return ans;
}
bool check(long long mid)
{
S=n*m+1,T=n*m+2,D=n*m+2;
edgenum=1;for (int i=1;i<=D;i++) head[i]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if ((i+j)&1)
{
addedge(S,id(i,j),mid-w[i][j]);
if (i>1) addedge(id(i,j),id(i-1,j),mid-w[i][j]);
if (j>1) addedge(id(i,j),id(i,j-1),mid-w[i][j]);
if (i<n) addedge(id(i,j),id(i+1,j),mid-w[i][j]);
if (j<m) addedge(id(i,j),id(i,j+1),mid-w[i][j]);
}
else addedge(id(i,j),T,mid-w[i][j]);
}
return (dinic(S,T)==(mid*n*m-sx-sy)/2);
}
int main()
{
int cas;
scanf("%d",&cas);
while (cas--)
{
sx=sy=mx=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%lld",&w[i][j]);
if ((i+j)&1) sy+=w[i][j]; else sx+=w[i][j];
mx=max(w[i][j],mx);
}
if (n&1 && m&1)
{
if (sx-sy<mx) {printf("-1\n");continue;}
if (check(sx-sy)) printf("%lld\n",((sx-sy)*n*m-sx-sy)/2);
else printf("-1\n");
}
else
{
if (sx!=sy) {printf("-1\n");continue;}
long long l=mx,r=mx+mx,ans=-1;
while (l<=r)
{
long long mid=(l+r)>>1;
if (check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
if (ans==-1) printf("-1\n");
else printf("%lld\n",(ans*n*m-sx-sy)/2);
}
}
return 0;
}