icpc.me 11014 - CyberFlower Algorithm

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

이분 매칭(플로우) 문제입니다. 최근에 Dinic 을 정리했으니 Dinic으로 풀어보도록 하겠습니다.

이분매칭에서 Maximum independent set 의 개수는 total-maximum matching의 개수와 같음(Konig의 정리,시간끌기) 을 이용하여 시간끌기라는 문제를 푼 적이 있습니다. 이 문제도 이와 동일하게 maxmimum independent set의 크기를 구하는 문제입니다.

이제 남은 건 그래프 모델링 뿐입니다.

그래프

위 그림처럼 하얀색, 파란색으로 이분그래프를 나타낼 수 있습니다. 이렇게 나타내면, 하얀색 정점에 대하여 인접한 6개의 파란색 정점에는 학생이 동시에 앉을 수 없게 됩니다.

#include<bits/stdc++.h>
#define pb push_back
#define INF (int)1e9
using namespace std;
const int SZ=85;
char grid[SZ][SZ];
struct Edge{
	int to,cap,rev;
	Edge(int to, int cap, int rev){
		this->to=to;
		this->cap=cap;
		this->rev=rev;
	}
};
struct Dinic{
	int n,src,dst;
	vector<vector<Edge>> graph;
	vector<int> crt;
	vector<int> lv;
	Dinic(int n, int src, int dst){
		this->n=n;
		this->src=src;
		this->dst=dst;
		graph.resize(n+5);
		crt.resize(n+5);
		lv.resize(n+5);
	}
	void push_edge(int a, int b, int capa){
		graph[a].pb(Edge(b,capa,graph[b].size()));
		graph[b].pb(Edge(a,0,graph[a].size()-1));
	}
	bool bfs(){
		for(int i=0;i<n+5;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(nxt.cap<=0 || lv[nxt.to]) 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 ans=0;
		while(bfs()){
			for(int i=0;i<n+5;i++) crt[i]=0;
			int f;
			while((f=dfs(src,INF))>0){
				ans+=f;
			}
		}
		return ans;
	}
};
#define myf(i,j) (i*m+j+1)
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t; cin>>t;
	while(t--){
		int n,m; cin>>n>>m;
		for(int i=0;i<n;i++) cin>>grid[i];
		Dinic dn=Dinic(n*m,0,n*m+1);
		int dx[6]={-1,-1,0,0,1,1};
		int dy[6]={-1,1,-1,1,-1,1};
		int tot=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(grid[i][j]=='.'){
					tot++;
					if(j%2==0) dn.push_edge(dn.src,myf(i,j),1);
					else dn.push_edge(myf(i,j),dn.dst,1);
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j+=2){
				if(grid[i][j]=='x') continue;
				for(int k=0;k<6;k++){
					int nx=i+dx[k];
					int ny=j+dy[k];
					if(nx<0 || nx>=n) continue;
					if(ny<0 || ny>=m) continue;
					if(grid[nx][ny]=='x') continue;
					dn.push_edge(myf(i,j),myf(nx,ny),1);
				}
			}
		}
		cout<<tot-dn.flow()<<'\n';
	}
	return 0;
}

백준 11014 컨닝2