洛谷P7231 题解
写了一下午……终于过了。是我太菜了吧……
题意
在 $N\times N$ 的正方形中放 $k$ 个 $1\times2$ 的骨牌，不能重叠，使得覆盖的数字和最大。
暴力思路
很容易想到，用费用流来跑。
首先从源点向零号点连一条容量为 $k$ 的边，限制骨牌个数。
对于横纵坐标之和为奇数的点，从零号点向该点连容量为1费用为权值的边；对于横纵坐标之和为偶数的点，从该点向汇点连容量为1费用为权值的边。
对于每个横纵坐标之和为奇数的点，向四周连容量为1费用为0的边。
可是这样建图有一个问题：点数是平方级，边数大概在32000000左右，于时间空间都不可行。
正解
考虑到有很多边其实根本没有存在的必要，我们其实不用建那么多边。
首先我们预处理出每个点放一块横着的骨牌或竖着的骨牌所能覆盖的两个点的权值和。
然后我们选出权值和最大的50组点集，显然在放置8块以内的骨牌时一定会选择的是这50组最大的点集。
然后在这50组点集中建图跑费用流即可。
丑陋的代码
#define ll long long
#define int long long
using namespace std;
int n,k,s,t,cnt=1,lst[4000005],sum[2005][2005],flow[4000005],dis[4000005],fa[4000005],bian[4000005],inf=0x3f3f3f3f,dl;
ll su,xf;
int x[205],y[205],dian,donex[205],chk[205],tp[205];
bool fl[4000005];
struct edge{
int f,t,val,cst,lst;
edge(int f=0,int t=0,int val=0,int cst=0,int lst=0):
f(f),t(t),val(val),cst(cst),lst(lst){};
}e[8000005];
struct node{
int x,y,val,id;
bool operator<(node b)const{
return val<b.val;
}
};
priority_queue<node> q;
void add(int u,int v,int val,int cst){
e[++cnt]=edge(u,v,val,cst,lst[u]);
lst[u]=cnt;
e[++cnt]=edge(v,u,0,-cst,lst[v]);
lst[v]=cnt;
}
bool spfa(){
memset(dis,inf,sizeof(dis));
memset(flow,inf,sizeof(flow));
memset(fl,0,sizeof(fl));
queue<int> q;
q.push(s),dis[s]=0,fa[t]=-1;
while(!q.empty()){
int u=q.front();
q.pop(),fl[u]=0;
for(int i=lst[u];i;i=e[i].lst){
int v=e[i].t;
if(e[i].val&&dis[v]>dis[u]+e[i].cst){
dis[v]=dis[u]+e[i].cst;
fa[v]=u;
bian[v]=i;
flow[v]=min(flow[u],e[i].val);
if(!fl[v]){
fl[v]=1;
q.push(v);
}
}
}
}
return fa[t]!=-1;
}
void MCMF(){
while(spfa()){
xf+=dis[t]*flow[t];
dl+=flow[t];
int now=t;
while(now!=s){
e[bian[now]].val-=flow[t];
e[bian[now]^1].val+=flow[t];
now=fa[now];
}
}
}
map<pair<int,int>,int> mp;
signed main(){
cin>>n>>k;
s=n*n+1,t=n*n+2;
add(s,0,k,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>sum[i][j];
su+=sum[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i<n){
int val=sum[i][j]+sum[i+1][j];
for(int r=1;r<=50;r++){
if(val>chk[r]){
for(int c=50;c>r;c--){
chk[c]=chk[c-1];
x[c]=x[c-1],y[c]=y[c-1],tp[c]=tp[c-1];
}
chk[r]=val,x[r]=i,y[r]=j,tp[r]=0;
break;
}
}
}
if(j<n){
int val=sum[i][j]+sum[i][j+1];
for(int r=1;r<=50;r++){
if(val>chk[r]){
for(int c=50;c>r;c--){
chk[c]=chk[c-1];
x[c]=x[c-1],y[c]=y[c-1],tp[c]=tp[c-1];
}
chk[r]=val,x[r]=i,y[r]=j,tp[r]=1;
break;
}
}
}
}
}
for(int i=1;i<=50;i++){
if(!chk[i])break;
int i1=x[i],j1=y[i];
if(tp[i]){
int i2=x[i],j2=y[i]+1;
if(!((i1+j1)&1))swap(i1,i2),swap(j1,j2);
add((i1-1)*n+j1,(i2-1)*n+j2,1,0);
if(!mp[{i1,j1}]){
add(0,(i1-1)*n+j1,1,-sum[i1][j1]);
mp[{i1,j1}]=1;
}
if(!mp[{i2,j2}]){
add((i2-1)*n+j2,t,1,-sum[i2][j2]);
mp[{i2,j2}]=1;
}
}
else{
int i2=x[i]+1,j2=y[i];
if(!((i1+j1)&1))swap(i1,i2),swap(j1,j2);
add((i1-1)*n+j1,(i2-1)*n+j2,1,0);
if(!mp[{i1,j1}]){
add(0,(i1-1)*n+j1,1,-sum[i1][j1]);
mp[{i1,j1}]=1;
}
if(!mp[{i2,j2}]){
add((i2-1)*n+j2,t,1,-sum[i2][j2]);
mp[{i2,j2}]=1;
}
}
}
MCMF();
cout<<su+xf;
return 0;
}