费用流好题
本题的建图很有意思
正常我们看到棋盘问题应该先对整个棋盘黑白染色构成一个二分图，然后再考虑建图的问题
但是本题题目中已经明确区分了不同的斜线，问题在于怎么保证一个"L"形
因此我们进一步分析：显然柱子应该放在有代价的位置，我们应该由这样的位置向上下左右连边，保证有两个就行
但是这样建图是有问题的，因为首先，难以保证选了两个位置，其次，上下/左右这种选两个的方式也是不合法的！
因此我们考虑进一步拆解这个图：我们把这个图分成三部分（请自动忽略坏点），一部分是产生代价的地方，一部分是行列号均为偶数的部分，一部分是行列号均为奇数的部分
然后我们这样建图：源点->二级源点->行列号均为偶数的部分->产生代价的部分->行列号均为奇数的部分->汇点
其中二级源点是为了限制流量不得大于$m$的
这样连边之后，就很好的保证了必须选两个且排除了选上下两个/左右两个的情况
中间的点需要拆点，拆出来两个点流量为1，费用给出
注意跑的是最大费用流，跑出来以后还要用总费用减去这个最大费用，同时我们并不需要让流量最大，因此如果费用为负直接跳出
贴代码：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; const int inf=0x3f3f3f3f; struct Edge { int nxt; int to; int val; int pri; }edge[5000005]; int lim[10005]; int to[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; bool vis[55][55]; bool used[10005]; int dis[10005]; int w[55][55]; int val[10005]; int head[10005]; int pre[10005],f[10005]; int tot=0,cnt=1; int n,m,k; int ans=0; int st,ed,eed; int idx(int x,int y) { return (x-1)*n+y; } int ide(int x) { return x&1?x+1:x-1; } bool check(int x,int y) { return x>0&&x<=n&&y>0&&y<=n&&!vis[x][y]; } void add(int l,int r,int z,int v) { edge[cnt].nxt=head[l]; edge[cnt].to=r; edge[cnt].val=z; edge[cnt].pri=v; head[l]=cnt++; } void dadd(int l,int r,int z,int v) { add(l,r,z,v),add(r,l,0,-v); } bool spfa() { memset(dis,-0x3f,sizeof(dis)); memset(pre,-1,sizeof(pre)); memset(f,0,sizeof(f)); dis[tot+1]=0; used[tot+1]=1; lim[tot+1]=inf; queue <int> M; M.push(tot+1); while(!M.empty()) { int u=M.front(); M.pop(); for(int i=head[u];i;i=edge[i].nxt) { int to=edge[i].to; if(edge[i].val&&dis[to]<dis[u]+edge[i].pri) { dis[to]=dis[u]+edge[i].pri; lim[to]=min(lim[u],edge[i].val); f[to]=u,pre[to]=i; if(!used[to])M.push(to),used[to]=1; } } used[u]=0; } return dis[tot+3]>0&&pre[tot+3]!=-1; } int EK() { int maxf=0,maxv=0; while(spfa()) { maxf+=lim[tot+3],maxv+=lim[tot+3]*dis[tot+3]; int temp=tot+3; while(temp!=tot+1) { edge[pre[temp]].val-=lim[tot+3]; edge[ide(pre[temp])].val+=lim[tot+3]; temp=f[temp]; } } return maxv; } int main() { scanf("%d%d%d",&n,&m,&k); tot=n*n*2; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&w[i][j]),ans+=w[i][j]; dadd(tot+1,tot+2,m,0); for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); vis[x][y]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(vis[i][j])continue; dadd((idx(i,j)<<1)-1,idx(i,j)<<1,1,w[i][j]); if((i&1)&&(j&1))dadd(idx(i,j)<<1,tot+3,1,0); else if(!(i&1)&&!(j&1)) { dadd(tot+2,(idx(i,j)<<1)-1,1,0); for(int t=0;t<4;t++) { int toi=i+to[t][0],toj=j+to[t][1]; if(!check(toi,toj))continue; dadd(idx(i,j)<<1,(idx(toi,toj)<<1)-1,1,0); } }else { for(int t=0;t<4;t++) { int toi=i+to[t][0],toj=j+to[t][1]; if(!check(toi,toj)||!(toi&1)||!(toj&1))continue; dadd(idx(i,j)<<1,(idx(toi,toj)<<1)-1,1,0); } } } } printf("%d ",ans-EK()); return 0; }