http://acm.hdu.edu.cn/showproblem.php?pid=1569
思路：找到要剔除的格子；相邻的连一条INF容量的边，最大流量就是相邻的最小的值了；
总结：最大流；
#include <iostream> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <cstdio> #include <map> //#include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) #define sfl(i) scanf("%lld",&i) #define sfs(i) scanf("%s",(i)) #define pri(i) printf("%d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) #define lowbit(x) ((x)&(-x)) #define zero(x) (((x)>0?(x):-(x))<eps) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) /* //--------------------------------------------------------- #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; */ //gp_hash_table<string,int>mp2; //__gnu_pbds::priority_queue<int>q;//因为放置和std重复，故需要带上命名空间 //__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;//最快 //---------------------------------------------------------- /* //---------------------------------------------------------- const int BufferSize = 1 << 16; char buffer[BufferSize], *_head, *_tail; inline char Getchar() { if (_head == _tail) { int l = fread(buffer, 1, BufferSize, stdin); _tail = (_head = buffer) + l; } return *_head++; } inline int read() { int x = 0, f = 1;char c = Getchar(); for (;!isdigit(c);c = Getchar()) if (c == '-') f = -1; for (;isdigit(c);c = Getchar()) x = x * 10 + c - '0'; return x * f; } //---------------------------------------------------------- */ const int maxn=1e5+9; const int maxm=4e5+9; const int mod=1e9+7; struct E { int to,nex,cap,flow; }edge[maxm]; int head[maxn]; int tot; int gap[maxn],dep[maxn],cur[maxn]; void init() { tot=0; mem(head,-1); } void addedge(int u,int v,int w,int rw=0) { edge[tot].to=v; edge[tot].cap=w; edge[tot].flow=0; edge[tot].nex=head[u]; head[u]=tot++; edge[tot].to=u; edge[tot].cap=rw; edge[tot].flow=0; edge[tot].nex=head[v]; head[v]=tot++; } int Q[maxn]; void bfs(int st,int ed) { mem(dep,-1); mem(gap,0); gap[0]=1; int fr=0,re=0; dep[ed]=0; Q[re++]=ed; while(fr!=re) { int u=Q[fr++]; for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(dep[v]!=-1) continue; Q[re++]=v; dep[v]=dep[u]+1; gap[dep[v]]++; } } } int S[maxn]; int sap(int st,int ed,int n) { bfs(st,ed); memcpy(cur,head,sizeof(head)); int top=0; int u=st; int ans=0; while(dep[st]<n) { if(u==ed) { int Min=INF; int inser; for(int i=0;i<top;i++) { if(Min>edge[S[i]].cap-edge[S[i]].flow) { Min=edge[S[i]].cap-edge[S[i]].flow; inser=i; } } for(int i=0;i<top;i++) { edge[S[i]].flow+=Min; edge[S[i]^1].flow-=Min; } ans+=Min; top=inser; u=edge[S[top]^1].to; continue; } bool flag=false; int v; for(int i=cur[u];i!=-1;i=edge[i].nex) { v=edge[i].to; if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]) { flag=true; cur[u]=i; break; } } if(flag) { S[top++]=cur[u]; u=v; continue; } int Min=n; for(int i=head[u];i!=-1;i=edge[i].nex) { if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min) { Min=dep[edge[i].to]; cur[u]=i; } } gap[dep[u]]--; if(!gap[dep[u]]) return ans; dep[u]=Min+1; gap[dep[u]]++; if(u!=st) u=edge[S[--top]^1].to; } return ans; } int main() { //FAST_IO; //freopen("input.txt","r",stdin); int n,m; while(~scanf("%d%d",&n,&m)) { init(); int s,t; s=0; t=(n-1)*m+m+1; int sum=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int a; sfi(a); sum+=a; if((i+j)%2==0) { addedge(s,(i-1)*m+j,a); if(i-1>=1) addedge((i-1)*m+j,(i-1-1)*m+j,INF); if(i+1<=n) addedge((i-1)*m+j,i*m+j,INF); if(j-1>=1) addedge((i-1)*m+j,(i-1)*m+(j-1),INF); if(j+1<=m) addedge((i-1)*m+j,(i-1)*m+j+1,INF); } else if((i+j)%2==1) { addedge((i-1)*m+j,t,a); } } } int ans=sap(s,t,n*m+2); printf("%d\n",sum-ans); } return 0; }
