1.二分+网络流+各种判。
2.网上很多程序都是错的。
3.一个%lld打成%d调了一年。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define maxn 45 #define maxv 1700 #define maxe 1000500 #define inf (1LL<<50) using namespace std; long long tt,n,m,map[maxn][maxn],col[maxn][maxn],n1=0,n2=0,s1=0,s2=0,mx=0; long long dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0}; long long dis[maxv],nume=1,g[maxv],s,t; queue <long long> q; bool vis[maxv]; struct edge { long long v,f,nxt; }e[maxe]; long long p(long long x,long long y) { return (x-1)*m+y; } void addedge(long long u,long long v,long long f) { e[++nume].v=v;e[nume].f=f;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; } bool checks(long long x,long long y) { if ((x>=1) && (x<=n) && (y>=1) && (y<=m)) return true; return false; } void build(long long x) { nume=1;memset(g,0,sizeof(g)); s=0;t=n1+n2+1; for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) { long long now=p(i,j); if (col[i][j]) addedge(s,now,x-map[i][j]); else addedge(now,t,x-map[i][j]); if (col[i][j]) { for (long long k=1;k<=4;k++) { long long a=i+dx[k],b=j+dy[k],ret=p(a,b); if (checks(a,b)) addedge(now,ret,inf); } } } } bool bfs() { for (long long i=s;i<=t;i++) {dis[i]=inf;vis[i]=false;} q.push(s);dis[s]=0;vis[s]=true; while (!q.empty()) { long long head=q.front();q.pop(); for (long long i=g[head];i;i=e[i].nxt) { long long v=e[i].v; if ((e[i].f) && (dis[v]>dis[head]+1)) { dis[v]=dis[head]+1; if (!vis[v]) {q.push(v);vis[v]=true;} } } } if (dis[t]==inf) return false; return true; } long long dinic(long long x,long long low) { if (x==t) return low; long long ret=0; for (long long i=g[x];i && low;i=e[i].nxt) { long long v=e[i].v; if ((e[i].f) && (dis[v]==dis[x]+1)) { long long dd=dinic(v,min(e[i].f,low)); e[i].f-=dd;e[i^1].f+=dd; ret+=dd;low-=dd; } } if (!ret) dis[x]=inf; return ret; } bool check(long long x) { build(x); long long max_flow=0,ret=0; while (bfs()) max_flow+=dinic(s,inf); for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) if (col[i][j]) ret+=(x-map[i][j]); if (ret==max_flow) return true; return false; } void work1() { long long x=(s1-s2)/(n1-n2); if (x>=mx) if (check(x)) { long long ret=x*(n1+n2)-s1-s2; printf("%lld ",(x*(n1+n2)-s1-s2)/2); return; } printf("-1 "); } void work2() { if (s1!=s2) {printf("-1 ");return;} long long l=mx,r=inf,ans=inf; while (l<=r) { long long mid=l+r>>1; if (check(mid)) {ans=mid;r=mid-1;} else l=mid+1; } if (ans==inf) printf("-1 "); else printf("%lld ",(ans*(n1+n2)-s1-s2)/2); return; } void work() { n1=0;n2=0;s1=0;s2=0;mx=0; scanf("%lld%lld",&n,&m); for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) { scanf("%lld",&map[i][j]); mx=max(mx,map[i][j]); } if ((n==1) && (m==1)) { printf("0 "); return; } col[1][1]=1; for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) for (long long k=1;k<=4;k++) col[i+dx[k]][j+dy[k]]=col[i][j]^1; for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) { if (col[i][j]) {n1++;s1+=map[i][j];} else {n2++;s2+=map[i][j];} } if (n1!=n2) work1(); else work2(); } int main() { scanf("%lld",&tt); for (long long i=1;i<=tt;i++) work(); return 0; }