icpc.me 9525 - CyberFlower Algorithm

https://www.acmicpc.net/problem/9525

이분매칭 문제입니다. 체스판에 폰을 하나 추가할 때 마다 놓을 수 있는 룩의 개수가 하나 증가합니다. 이를 이용하면 이분매칭 모델링을 할 수 있습니다.

modeling

예제를 모델링한 사진입니다. 룩에 의해서 생기는 가로선을 왼쪽으로, 세로선을 오른쪽으로 하는 이분 그래프를 모델링 할 수 있습니다. 가로선과 세로선이 만나는 경우에는 두 선분 중 하나만을 선택해야 하므로 간선을 이어주면 됩니다.

#include<bits/stdc++.h>
#define pb push_back
#define INF (int)1e9+5
using namespace std;
const int SZ=105;
char chess[SZ][SZ];
int row[SZ][SZ];
int col[SZ][SZ];
struct Dinic{
    struct Edge{
        int to,rev,cap;
        Edge(int to, int rev, int cap):to(to),rev(rev),cap(cap){

        }
    };
    int n,m,src,dst;
    vector<vector<Edge>> graph;
    vector<int> crt;
    vector<int> lv;
    Dinic(int n, int m, int src, int dst):n(n),m(m),src(src),dst(dst){
        graph.resize(n+m+5);
        crt.resize(n+m+5);
        lv.resize(n+m+5);
    }
    void push_edge(int a, int b, int capa){
        graph[a].pb(Edge(b,graph[b].size(),capa));
        graph[b].pb(Edge(a,graph[a].size()-1,0));
    }
    bool bfs(){
        for(int i=0;i<=n+m+1;i++) lv[i]=0;
        queue<int> q;
        q.push(src); lv[src]=1;
        while(!q.empty()){
            int f=q.front(); q.pop();
            for(auto nxt:graph[f]){
                if(lv[nxt.to] || nxt.cap<=0) continue;
                q.push(nxt.to); lv[nxt.to]=lv[f]+1;
            }
        }
        return lv[dst]!=0;
    }
    int dfs(int x, int mnc){
        if(x==dst) return mnc;
        for(int &i=crt[x];i<(int)graph[x].size();i++){
            auto &e=graph[x][i];
            if(lv[x]>=lv[e.to] || e.cap<=0) continue;
            int f=dfs(e.to,min(mnc,e.cap));
            if(f>0){
                e.cap-=f;
                graph[e.to][e.rev].cap+=f;
                return f;
            }
        }
        return 0;
    }
    int flow(){
        int res=0;
        while(bfs()){
            for(int i=0;i<=n+m+1;i++) crt[i]=0;
            int f;
            while((f=dfs(src,INF))>0){
                res+=f;
            }
        }
        return res;
    }
};
void go_left(int x, int y, int n, int c){
    for(int i=y;i<n;i++){
        if(chess[x][i]=='X') return;
        row[x][i]=c;
    }
}
void go_down(int x, int y, int n, int c){
    for(int i=x;i<n;i++){
        if(chess[i][y]=='X') return;
        col[i][y]=c;
    }
}
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin>>n;
    for(int i=0;i<n;i++) cin>>chess[i];
    int lft=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(chess[i][j]=='X' || row[i][j]) continue;
            go_left(i,j,n,++lft);
        }
    }
    int rht=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(chess[j][i]=='X' || col[j][i]) continue;
            go_down(j,i,n,++rht);
        }
    }
    Dinic dn=Dinic(lft,rht,0,lft+rht+1);
    for(int i=1;i<=lft;i++) dn.push_edge(0,i,1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(chess[i][j]=='X') continue;
            dn.push_edge(row[i][j],lft+col[i][j],1);
        }
    }
    for(int i=lft+1;i<=lft+rht;i++) dn.push_edge(i,lft+rht+1,1);
    cout<<dn.flow();
    return 0;
}

백준 9525 룩 배치하기