洛谷P2774方格取数问题二分图最大独立点集最小割

#include
using namespace std;
#define ll long long/* dinic begin */const int MAXN&＃61;10100;
const int MAXM&＃61;100010;
const int INF&＃61;0x3f3f3f3f;
struct Edge{int to,next,cap,flow;
}edge[MAXM];int tol;
int head[MAXN];void init(){tol&＃61;2;memset(head,-1,sizeof(head));
}void addedge(int u,int v,int w){edge[tol].to&＃61;v;edge[tol].cap&＃61;w;edge[tol].flow&＃61;0;edge[tol].next&＃61;head[u];head[u]&＃61;tol&＃43;&＃43;;edge[tol].to&＃61;u;edge[tol].cap&＃61;0;edge[tol].flow&＃61;0;edge[tol].next&＃61;head[v];head[v]&＃61;tol&＃43;&＃43;;
}int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n){int front&＃61;0,tail&＃61;0;memset(dep,-1,sizeof(dep[0])*(n&＃43;1));dep[s]&＃61;0;Q[tail&＃43;&＃43;]&＃61;s;while(front<tail){int u&＃61;Q[front&＃43;&＃43;];for(int i&＃61;head[u];i!&＃61;-1;i&＃61;edge[i].next){int v&＃61;edge[i].to;if(edge[i].cap>edge[i].flow&&dep[v]&＃61;&＃61;-1){dep[v]&＃61;dep[u]&＃43;1;if(v&＃61;&＃61;t)return true;Q[tail&＃43;&＃43;]&＃61;v;}}}return false;
}int dinic(int s,int t,int n){//n最后一个节点的编号的下一个编号int maxflow&＃61;0;while(bfs(s,t,n)){for(int i&＃61;0;ihead[i];int u&＃61;s,tail&＃61;0;while(cur[s]!&＃61;-1){if(u&＃61;&＃61;t){int tp&＃61;INF;for(int i&＃61;tail-1;i>&＃61;0;i--){tp&＃61;min(tp,edge[sta[i]].cap-edge[sta[i]].flow);}maxflow&＃43;&＃61;tp;for(int i&＃61;tail-1;i>&＃61;0;i--){edge[sta[i]].flow&＃43;&＃61;tp;edge[sta[i]^1].flow-&＃61;tp;if(edge[sta[i]].cap-edge[sta[i]].flow&＃61;&＃61;0)tail&＃61;i;}u&＃61;edge[sta[tail]^1].to;}else if(cur[u]!&＃61;-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]&＃43;1&＃61;&＃61;dep[edge[cur[u]].to]){sta[tail&＃43;&＃43;]&＃61;cur[u];u&＃61;edge[cur[u]].to;}else{while(u!&＃61;s&&cur[u]&＃61;&＃61;-1){u&＃61;edge[sta[--tail]^1].to;}cur[u]&＃61;edge[cur[u]].next;}}}return maxflow;
}/* dinic end */int c[105][105];int n,m;
int id(int i,int j){return (i-1)*m&＃43;j;
}int main(){init();scanf("%d%d",&n,&m);ll sum&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){scanf("%d",&c[i][j]);sum&＃43;&＃61;c[i][j];}}int s&＃61;0,t&＃61;4*n*m&＃43;1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){if((i&＃43;j)%2&＃61;&＃61;1){//黑点
addedge(s,id(i,j),c[i][j]);}else{addedge(id(i,j),t,c[i][j]);}}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){if((i&＃43;j)%2&＃61;&＃61;1){//黑点if(i>1){addedge(id(i,j),id(i-1,j),INF);}if(j>1){addedge(id(i,j),id(i,j-1),INF);}if(i&＃43;1<&＃61;n){addedge(id(i,j),id(i&＃43;1,j),INF);}if(j&＃43;1<&＃61;m){addedge(id(i,j),id(i,j&＃43;1),INF);}}}}int maxflow&＃61;dinic(s,t,t&＃43;1);printf("%lld\n",sum-maxflow);}