【bzoj2127】happiness

xiaoxiao2021-02-27  134

题解过长,于是丢lych_cys题解跑

#include <bits/stdc++.h> #define gc getchar() #define ll long long #define mid (l+r>>1) #define N 109 #define inf 0x3f3f3f3f using namespace std; int n,m,a[N][N],b[N][N],sum; int number=1,pos,cur[N*N],dis[N*N]; bool vis[N*N]; vector<int> G[N*N]; struct edge { int from,to,flow,cap; int rest() { return cap-flow; } void add(int x,int y,int z) { from=x,to=y,cap=z,flow=0; } }e[N*N<<4]; void add(int x,int y,int z,int zz=0) { e[++number].add(x,y,z); G[x].push_back(number); e[++number].add(y,x,zz); G[y].push_back(number); } #define E e[G[x][i]] bool bfs(int s,int t) { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); dis[s]=0; vis[s]=1; while (!Q.empty()) { int x=Q.front(); Q.pop(); for (int i=0;i<(int)G[x].size();i++) if (!vis[E.to]&&E.rest()>0) { vis[E.to]=1; dis[E.to]=dis[x]+1; Q.push(E.to); } } return vis[t]; } int dfs(int x,int a,int t) { if (x==t||a==0) return a; int flow=0,f; for (int &i=cur[x];i<(int)G[x].size();i++) if (dis[x]+1==dis[E.to]&&(f=dfs(E.to,min(a,E.rest()),t))>0) { E.flow+=f; e[G[x][i]^1].flow-=f; flow+=f; a-=f; if (!a) break; } return flow; } int Maxflow(int s,int t) { int flow=0; while (bfs(s,t)) { memset(cur,0,sizeof(cur)); flow+=dfs(s,inf,t); } return flow; } #undef E int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0'; return s*x; } int main() { n=read(),m=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int x=read(); add(0,(i-1)*m+j,2*x); sum+=x; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int x=read(); add((i-1)*m+j,n*m+1,2*x); sum+=x; } for (int i=1;i<=n-1;i++) for (int j=1;j<=m;j++) a[i][j]=read(),sum+=a[i][j]; for (int i=1;i<=n-1;i++) for (int j=1;j<=m;j++) b[i][j]=read(),sum+=b[i][j]; for (int i=1;i<=n-1;i++) for (int j=1;j<=m;j++) { int x=(i-1)*m+j,y=i*m+j; e[x<<1].cap+=a[i][j]; e[y<<1].cap+=a[i][j]; e[(n*m+x)<<1].cap+=b[i][j]; e[(n*m+y)<<1].cap+=b[i][j]; add(x,y,a[i][j]+b[i][j],a[i][j]+b[i][j]); } for (int i=1;i<=n;i++) for (int j=1;j<=m-1;j++) a[i][j]=read(),sum+=a[i][j]; for (int i=1;i<=n;i++) for (int j=1;j<=m-1;j++) b[i][j]=read(),sum+=b[i][j]; for (int i=1;i<=n;i++) for (int j=1;j<=m-1;j++) { int x=(i-1)*m+j,y=(i-1)*m+j+1; e[x<<1].cap+=a[i][j]; e[y<<1].cap+=a[i][j]; e[(n*m+x)<<1].cap+=b[i][j]; e[(n*m+y)<<1].cap+=b[i][j]; add(x,y,a[i][j]+b[i][j],a[i][j]+b[i][j]); } printf("%d\n",sum-Maxflow(0,n*m+1)/2); return 0; }
转载请注明原文地址: https://www.6miu.com/read-13848.html

最新回复(0)