题解：AT_abc407_g [ABC407G] Domino Covering SUM

· · 题解

本蒟蒻自己想出的第一道 G，写篇题解纪念一下，望管理员大大通过。

思路解析

很经典的题。
先考虑连边，先将图染为黑白两色，
将 S 向白点连一条容量为 1，费用为 0 的边，再将黑点向 T 连一条容量为 1，费用为 0 的边。
接着从白点向相邻的黑点连一条容量为 1，费用为两点权之和的边，割去相当于覆盖。
这样整个图就转化为了二分图，跑费用流，用总和减费用就行了。
但各位神犇眉头一皱，发现事情没那么简单。
如果只是如此，费用流会为了流量将正点权覆盖了。
所以在跑费用流时，如果费用为正，就直接退出即可。

AC CODE


#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5,inf=1e18;
int s,t,head[maxn],to[maxn*2],nxt[maxn*2],val[maxn*2],tot=1,pre[maxn];
int vis[maxn],n,m,a[5005][5005],dist[maxn],flow[maxn*2],dis[maxn];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},ans,sum,cnt;
queue<int>q;
void add(int a,int b,int v,int w){
    nxt[++tot]=head[a];
    to[tot]=b;
    flow[tot]=v;
    val[tot]=w;
    head[a]=tot;
    nxt[++tot]=head[b];
    to[tot]=a;
    val[tot]=-w;
    head[b]=tot;
}
int id(int x,int y){return x*(m+1)+y;}
bool spfa(){
    for(int i=0;i<=id(n,m)+3;i++) dis[i]=inf;
    memset(vis,0,sizeof vis);
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    dist[s]=inf;
    while(!q.empty()) {
        int x=q.front();
        vis[x]=0;
        q.pop();
        for(int i=head[x];i;i=nxt[i]) {
            int y=to[i];
            if(!flow[i]) continue;
            if(dis[y]>dis[x]+val[i]) {
                dis[y]=dis[x]+val[i];
                dist[y]=min(dist[x],flow[i]);
                pre[y]=i;
                if(!vis[y]) vis[y]=1,q.push(y);
            }
        }
    }
    if(dis[t]==inf) return 0;
    return 1;
}
bool update(){
    if(dis[t]>=0) return 0;
    int x=t;
    while(x!=s){
        int id=pre[x];
        flow[id]-=dist[t];
        flow[id^1]+=dist[t];
        x=to[id^1];
    }
    ans+=dist[t];
    sum+=dis[t];
    return 1;
}
signed main(){
    int num=0;
    cin>>n>>m;
    s=id(n,m)+1,t=id(n,m)+2; 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j],num+=a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i+j)%2==0) {
                add(s,id(i,j),1,0);
                for(int k=0;k<4;k++){
                    int nx=i+dx[k],ny=j+dy[k];
                    if (nx<1||nx>n||ny<1||ny>m) continue;
                    add(id(i,j),id(nx,ny),1,a[i][j]+a[nx][ny]);
                }
            }
            else add(id(i,j),t,1,0);
        }
    }
    while(spfa()){if(!update()) break;}
    cout<<num-sum;
    return 0;
}