ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - J Rooks Game

問題

問題概要

の盤面に、個の駒が配置されています。それぞれの駒は、縦か横方向に好きなだけ移動させることができ、他の駒にぶつかったら、その時点で停止してぶつかった駒を獲得することができます。ただし、他の駒が存在しない方向へ動かすことはできません。この操作を、駒が獲得できなくなるまで行います。
最適な操作をして、駒の獲得数を最小化、および最大化してその個数を求めてください、というものです。

解法

駒を最大化する方法の方が個人的には楽です。駒を頂点とみなし、縦、および横の座標が一致している2つの駒に辺を張ります。すると、どこか適当な駒を根とすると、葉から根に駒を順番にぶつけていくことで、獲得できる駒が最大化できます。
よって、答えは(グラフの連結成分-1)の総和になります(グラフが複数になる場合に注意します)。これはUnion-Findでよしなに連結していくことで簡単に求まります。
最小化するパターンは、最終的な盤面に着目すると、それぞれの行、もしくは列にたかだか1つの駒しか存在しません。
そこで、最終的に駒が存在する地点の行、列のペアを上手く組み合わせて最大化すると、それが最適なパターンになります。
実際に操作する場合は、残すと決めた駒に他の駒をぶつけていけばよいので、これで最適解がもとまります(もしこの方法で残すと決めた以外の駒が残ってしまった場合、そもそも残すと決めた駒のパターンが間違っています)。
ということで、行と列の二部マッチングを考えることになり、個の駒の行と列のペアに辺を張り、フローを流すことで、最終的に残る駒の個数が求まります。あとは、これをから引けばよいです。

感想

最終的に残る駒の個数を最大化、フローっぽい、まではいけたのですが二部マッチングに帰着させることができませんでした…
よく見るような形の問題な気がするので、おさえておきたいです。

提出コード

#include <bits/stdc++.h>
#define fi first
#define se second
#define inf (long long)1e8
using namespace std;
using p = pair<long long,long long>;

struct Unionfind{
    vector<int> par;
    vector<int> treerank;
    Unionfind(int n = 1){stree(n+1);}
    void stree(int n = 1){
        par.assign(n,-1);
        treerank.assign(n,0);
    }
    int root(int x){
        if(par[x] < 0)return x;
        return par[x] = root(par[x]);
    }
    bool issame(int x,int y){return root(x) == root(y);}
    bool uni(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return 0;
        if(treerank[x] > treerank[y])swap(x,y);
        if(treerank[x] == treerank[y])++treerank[y];
        par[y] -= size(x);
        par[x] = y;
        return 1;
    }
    int size(int x){return -par[root(x)];}
};

template<class T>
struct Dinic{
    struct edge{
        int to;
        T cap;
        int rev;
    };
    vector<vector<edge>> lst;
    vector<int> completed;
    vector<int> dist;
    Dinic(int n = 1){
        lst.resize(n);
        completed.resize(n);
        dist.resize(n);
    }
    bool add(int start,int goal,T capacity){
        lst[start].push_back((edge){goal,capacity,(int)lst[goal].size()});
        lst[goal].push_back((edge{start,0,(int)lst[start].size()-1}));
        return 1;
    }
    void distbfs(int start){
        fill(dist.begin(),dist.end(),-1);
        queue<int> bfsqu;
        dist[start] = 0;
        bfsqu.push(start);
        while(bfsqu.size() > 0){
            int now = bfsqu.front();
            bfsqu.pop();
            for(int i=0;i < lst[now].size();++i){
                edge* nowe = &lst[now][i];
                if(nowe->cap > 0 && dist[nowe->to]<0){
                    dist[nowe->to] = dist[now] + 1;
                    bfsqu.push(nowe->to);
                }
            }
        }
    }
    T pathdfs(int now,int goal,T nf){
        if(now == goal)return nf;
        for(int& i= completed[now];i < lst[now].size();++i){
            edge* e = &lst[now][i];
            if(e->cap > 0 && dist[now] < dist[e->to]){
                T ans = pathdfs(e->to,goal,min(nf,e->cap));
                if(ans > 0){
                    e->cap -= ans;
                    lst[e->to][e->rev].cap += ans;
                    return ans;
                }
            }
        }
        return 0;
    }
    T solve(int start,int goal){
        T ans=0,nf = 0;
        while(1){
            distbfs(start);
            if(dist[goal]<0)return ans;
            fill(completed.begin(),completed.end(),0);
            while((nf=pathdfs(start,goal,inf))>0)ans += nf;
        }
        return -1;
    }
};

long long n,m;
long long dp[1005][1005][2][2] = {0};
vector<long long> lstx[1005],lsty[1005];
vector<p> v;
Unionfind uf;
set<p> st;

long long solve();

int main() {
    cin >> n >> m;
    v.resize(m);
    for (int i = 0; i < m; ++i){
        cin >> v[i].fi >> v[i].se;
        --v[i].fi;
        --v[i].se;
        st.insert(v[i]);
    }
    cout << solve() << endl;
    return 0;
}

long long solve(){
    long long ans = 0;
    uf = Unionfind(m);
    sort(v.begin(),v.end());
    for(int i = 0;i < m;++i){
        lstx[v[i].fi].push_back(i);
        lsty[v[i].se].push_back(i);
    }
    for(int i=0;i<n;++i){
        for(int j=1;j<lstx[i].size();++j)
            uf.uni(lstx[i][j],lstx[i][j-1]);
        for(int j=1;j<lsty[i].size();++j)
            uf.uni(lsty[i][j],lsty[i][j-1]);
    }
    //min
    Dinic<int> din(2 * n +2);
    for(int i = 0;i < m;++i)
        din.add(v[i].fi,v[i].se + n,1);
    for(int i = 0;i < n;++i){
        din.add(2 * n,i,1);
        din.add(i + n,2 * n + 1,1);
    }
    cout << m - din.solve(2 * n,2 * n+1)<< " ";
    // max
    ans = 0;
    vector<bool> ch(m,0);
    for(int i = 0;i < m;++i)
        if(!ch[uf.root(i)]) {
            ans += uf.size(uf.root(i)) - 1;
            ch[uf.root(i)] = 1;
        }
    return ans;
}