最小点权覆盖集
二分图最小点权覆盖集解决的是这样一个问题：
在二分图中，对于每条边，两个端点至少选一个，求所选取的点最小权值和。
方法：
1、先对图二分染色，对于每条边两端点的颜色不同
2、然后建立源点S，向其中一种颜色的点连一条容量为该点权值的边
3、建立汇点T，由另一种颜色的点向T连一条容量为该点权值的边
4、对于二分图中原有的边，改为由与S相连的点连向与T相连的点的一条容量为INF的边
跑一遍最大流，其结果就是最小点权和。
原理：
实际为最小割。建好图后，对整张图求最小割，那么不可能割INF的边，所以每对点中连向源汇点边权最小的边被割断，整体来看，就是对于任意一对端点，都选了一个较小权值，得到我们要的结果。
最大点权独立集
与最小点权覆盖集相似：
在二分图中，对于每条边，两个端点至多选一条边，求所选取的点的最大权值和。
方法：
先求一次最小点权覆盖集，再用总权值减去它，就得到了最大点权独立集。
原理：
在最小点权独立集中，是每对点至少选择了一个的最小方案，反过来，就是每对点至多选择了一个的最大方案。
洛谷P2274 方格取数问题
方格取数问题就是很经典的最大点权独立集问题：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn=100005,maxm=10000005,INF=2000000000; inline int read(){
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
return out*flag;
} int head[maxn],nedge=0;
struct EDGE{
int to,f,next;
}edge[maxm]; inline void build(int a,int b,int w){
edge[nedge]=(EDGE){b,w,head[a]};
head[a]=nedge++;
edge[nedge]=(EDGE){a,0,head[b]};
head[b]=nedge++;
} int color[105][105],N,M,S,T,X[4]={0,0,-1,1},Y[4]={1,-1,0,0}; bool vis[maxn];
int d[maxn],cur[maxn]; bool bfs(){
fill(vis,vis+maxn,false);
queue<int> q;
q.push(S);
vis[S]=true;
d[S]=0;
int u,to;
while(!q.empty()){
u=q.front();
q.pop();
for(int k=head[u];k!=-1;k=edge[k].next)
if(!vis[to=edge[k].to]&&edge[k].f){
d[to]=d[u]+1;
vis[to]=true;
q.push(to);
}
}
return vis[T];
} int dfs(int u,int minf){
if(u==T||!minf) return minf;
int flow=0,f,to;
if(cur[u]==-2) cur[u]=head[u];
for(int& k=cur[u];k!=-1;k=edge[k].next)
if(d[to=edge[k].to]==d[u]+1&&(f=dfs(to,min(edge[k].f,minf)))){
edge[k].f-=f;
edge[k^1].f+=f;
flow+=f;
minf-=f;
if(!minf) break;
}
return flow;
} int maxflow(){
int flow=0;
while(bfs()){
fill(cur,cur+maxn,-2);
flow+=dfs(S,INF);
}
return flow;
} int main()
{
fill(head,head+maxn,-1);
N=read();
M=read();
S=0;
T=N*M+1;
color[0][0]=1;
int x;
LL tot=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
if((i%2&&j%2)||(i%2==0&&j%2==0)) color[i][j]=1;
else color[i][j]=0;
}
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
x=read();
tot+=x;
if(color[i][j]) build(M*(i-1)+j,T,x);
else{
build(S,M*(i-1)+j,x);
for(int k=0;k<4;k++){
int nx=i+X[k],ny=j+Y[k];
if(nx>0&&ny>0&&nx<=N&&ny<=M) build(M*(i-1)+j,M*(nx-1)+ny,INF);
}
}
}
cout<<tot-maxflow()<<endl;
return 0;
}