CF1773D 题解

· · 题解

my blog

Solution

首先将棋盘黑白染色，是一个二分图。

由于题目保证初始状态一定能密铺，因此这个二分图一定有完美匹配。

现在要铺 2 个地方，显然分两种情况：

显然此时并不能产生完美匹配，因此这些情况都是答案，即 2 \times \binom{cnt}{2}。

枚举黑色点删哪个，考察哪些白色点删了之后二分图就不存在完美匹配了，即求新图最大匹配的必经点。

这篇写的是必经边，这里换成了必经点，处理有所不同。

首先，如果流量不是白色点-1，就说明无论选什么白色点，都无法达到完美匹配，答案加上白色点个数。

否则，考虑从汇点 T 反向走，每次走满流的点，如果当前点是白色点，就标记。最后统计没标记的点就是必经点。

为什么是对的呢？

首先，考虑 T 到某个白色点的反向边，反向边由于容量为 0，满流则说明其对应的正向边的流量也为 0，也就是这个白色点没有参加匹配。

从这个白色点开始，走反向边到黑色点，意味着这个黑点到这个白点没有匹配，可以作为备选。

然后从黑色点开始走，满流走到下一个白色点，意味着这个黑点和下一个白色点匹配上了，这时，我们发现可以将这个黑点和上一个白点匹配，也就是下一个白点不是必选点。这样递归下去我们就得到了所有非必选点，反过来就是必经点了。

代码：

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 3005;

int n,m,a[1005][1005];
struct ed{
    LL from,to,cap,flow,rev;
    ed(){}
    ed(LL from,LL to,LL cap,LL flow,LL rev):from(from),to(to),cap(cap),flow(flow),rev(rev){}
};
vector<ed>g[maxn];

const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
inline int in(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;} 
inline int ind(int x,int y){return (x-1)*m+y;}

struct netflow{
    int cur[maxn]; 
    int d[maxn], q[maxn], hd, tl;
    int s, t;   // 源 汇 

    netflow(){s=t=-1;}

    void init(int s0,int t0){
        s = s0, t = t0;
    }

    void add(int x,int y,LL v){
        g[x].push_back(ed(x,y,v,0,g[y].size()));
        g[y].push_back(ed(y,x,0,0,g[x].size() - 1));
    }

    int bfs(){
        memset(d,0, sizeof d);
        hd = tl = 0;
        q[tl ++] = s;
        d[s] = 1;
        while(hd != tl){
            int now = q[hd ++];
            for(int i = 0;i<g[now].size();i++){
                ed &e = g[now][i];
                if(!d[e.to] && e.cap > e.flow)d[e.to] = d[now] + 1, q[tl ++] = e.to;
            }
        }
        return d[t];
    }

    LL dfs(int now,LL rem){ // rem 当前流量 
        if(now == t || !rem)return rem;
        LL flow = 0;
        for(int &i = cur[now]; i < g[now].size();i ++){
            ed &e = g[now][i];
                // 分层图 & 残量不为0 
            if(d[e.to] == d[now] + 1 && e.cap > e.flow){
                LL f = dfs(e.to, min(rem, e.cap - e.flow));
                rem -= f, flow += f, e.flow += f, g[e.to][e.rev].flow -= f;
            }
            if(!rem)break;
        }
        if(rem)d[now] = -1;
        return flow;
    }

    LL dinic(){
        assert(s!=-1);
        LL flow = 0;
        while(bfs()){
            memset(cur, 0, sizeof cur);
            flow += dfs(s, 1ll << 62);
        }
        return flow;
    }
}nf;
vector<pii>ed;
vector<int>lft,rgt; 
int vis[maxn];

void dfs(int x){
    vis[x] = 1;
    for(int i=0;i<g[x].size();i++){
        struct ed e = g[x][i];
        if(!vis[e.to] && e.flow == e.cap)dfs(e.to);
    }
}

map<int,int>mp;
int cc;

signed main(){
//  freopen("CF1773D.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        char s[1005];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            if(s[j] == '#')a[i][j] = 0;
            else a[i][j] = 1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(a[i][j] == 1)mp[ind(i, j)] = ++cc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(a[i][j]){
            if((i%2 + j) & 1){
                for(int k=0;k<4;k++){
                    int fi = i+dx[k], fj = j+dy[k];
                    if(!in(fi, fj) || !a[fi][fj])continue;
                    ed.pb(mpr(mp[ind(i, j)], mp[ind(fi, fj)]));
                }
            }
        }

    int cnt0=0, cnt1=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(a[i][j]){
            if((i%2 + j) & 1)++ cnt0, lft.pb(mp[ind(i, j)]);
            else ++cnt1, rgt.pb(mp[ind(i, j)]);
        }

    ll ans = 1ll*cnt0*(cnt0-1)/2 + 1ll*cnt1*(cnt1-1)/2;
    if(ans >= (ll)1e6)return printf("%d\n",(int)1e6), 0;

    int s = 2*cnt0+1, t = s+1;
    nf.init(s, t);
    for(int u : lft){
        for(int i : lft)g[i].clear(), vis[i] = 0;
        for(int i : rgt)g[i].clear(), vis[i] = 0;
        g[s].clear(), g[t].clear();
        vis[s] = vis[t] = 0;

        for(pii e : ed){
            if(e.first ^ u){
                nf.add(e.first, e.second, 1);
            }
        }
        for(int v : lft)if(u^v)nf.add(s, v, 1);
        for(int v : rgt)nf.add(v, t, 1);

        ll res = nf.dinic(), r=0;
        if(res != cnt0-1){
            ans += cnt1;
            continue;
        }
        dfs(t);
        for(int v : rgt)if(!vis[v])++ r;
        ans += r;
    }
    cout << min(ans, (ll)1e6) << '\n';

    return 0;
}