백준 1671 상어의 저녁식사

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

n마리의 상어를 복제해봅시다. x번 상어를 “먹는 상어” x, “먹히는 상어” x+n으로 두마리씩 복제할 수 있습니다. 그러면 이 문제는 이분매칭과 비슷한 꼴이 됩니다.

“먹는 상어”는 최대 2마리씩 먹을 수 있습니다. “먹히는 상어”는 최대 1번씩 먹힐 수 있죠. 따라서 src->먹는 상어 의 capacity를 2로, 먹히는 상어->snk 의 capacity를 1로 하는 최대유량 문제로 바꿀 수 있습니다. (생존할 수 있는 최소 상어의 수는 잡아먹히는 최대 상어의 수이기 때문입니다.)

ford_fulkerson 방식을 사용하겠습니다. 여기서 ford_fulkerson 알고리즘을 볼 수 있습니다.

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int SZ=205;
vector<int> graph[2*SZ];
int cf[2*SZ][2*SZ];
int vst[2*SZ];
int src,snk;
int n;
struct shark{
	int x,y,z;
};
shark arr[SZ];
int dfs(int x, int mnc){
	vst[x]=1;
	if(x==snk) return mnc;
	for(int nxt:graph[x]){
		if(vst[nxt]==1 || cf[x][nxt]<=0) continue;
		int f=dfs(nxt,min(cf[x][nxt],mnc));
		if(f>0){
			cf[x][nxt]-=f;
			cf[nxt][x]+=f;
			return f;			
		}
	}
	return 0;
}
int ford_fulkerson(){
	int ans=0;
	while(1){
		memset(vst,0,sizeof(vst));
		int f=dfs(src,INT_MAX);
		if(f==0) break;
		ans++;
	}
	return ans;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y,z; cin>>x>>y>>z;
		arr[i]={x,y,z};
	}
	src=0; snk=2*n+1;
	for(int i=1;i<=n;i++){
		graph[src].pb(i);
		cf[src][i]=2;
		graph[i].pb(src);
	}
	for(int i=n+1;i<=2*n;i++){
		graph[i].pb(snk);
		cf[i][snk]=1;
		graph[snk].pb(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			if(arr[i].x==arr[j].x && arr[i].y==arr[j].y && arr[i].z==arr[j].z && i>j) continue;
			else if(arr[i].x>=arr[j].x && arr[i].y>=arr[j].y && arr[i].z>=arr[j].z){
				graph[i].pb(n+j);
				cf[i][n+j]=1;
				graph[n+j].pb(i);
			}
		}
	}
	cout<<n-ford_fulkerson();
	return 0;
}