MCMF

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11111 🧐 관찰 및 접근 # 대충봐도 격자그래프에서 MCMF같은데.. 덜끊어도 되니까 MaxFlow가 아닌가? 아하 뒤집으면 된다 아하, Flow 자체도 다 보내기 전이 최적일수도 있는것만 잊지 말자 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<vector<int>> costs = { {10, 8, 7, 5, 1}, {8, 6, 4, 3, 1}, {7, 4, 3, 2, 1}, {5, 3, 2, 2, 1}, {1, 1, 1, 1, 0} }; vector<vector<int>> board(N, vector<int>(M)); map<char, int> mp; mp['A'] = 0; mp['B'] = 1; mp['C'] = 2; mp['D'] = 3; mp['F'] = 4; rep(i, 0, N){ string S; cin >> S; rep(j, 0, M) board[i][j] = mp[S[j]]; } MinCostMaxFlow MCMF(N*M+2); MCMF.setST(N*M, N*M+1); vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; rep(i, 0, N) rep(j, 0, M){ if((i+j)%2){ MCMF.add(i*M+j, N*M+1, 1, 0); continue; } MCMF.add(N*M, i*M+j, 1, 0); rep(d, 0, 4){ int nx = i + dx[d], ny = j + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; MCMF.add(i*M + j, nx*M + ny, 1, -costs[board[i][j]][board[nx][ny]]); } } cout << max(0LL, -MCMF.match()); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11493 🧐 관찰 및 접근 # 동전들을 swap해서 잘 옮겨서 맞춰야한다.. 일단 색을 모두 신경쓰긴 싫으니까, 1의 위치를 맞춘다고만 생각하자. 뭔가 이분그래프적으로 생각할 수 있지 않을까? 이게 움직이는것만 신경쓰면 플로이드워셜 + 이분그래프 매칭 최소비용…으로 하면 되는거같은데? 근데 swap이다보니 이렇게 맘대로 하는것보다 효율적인 방법이 무시될 것 같다. 일단 이분그래프로 생각을 좀 해보긴 하자. 그림을 그려보자. ![[Drawing 2026-03-07 15.31.09.excalidraw.png]] 그림 1의 예시이다. 어우 난잡해 ㅋㅋ 뭔가 증가경로 맛처럼 할 수 있는거같기는 한데.. ….가 아니라 그냥 이상태로 최소비용 최대유량 아닌가? 끝이네? 이분그래프로 분할할 필요도 없이, 그냥 유량으로 달리면 된다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; MinCostMaxFlow MCMF(N+2); MCMF.setST(0, N+1); rep(i, 0, M){ int u, v; cin >> u >> v; MCMF.add(u, v, 1e9, 1); MCMF.add(v, u, 1e9, 1); } rep(i, 1, N+1){ int x; cin >> x; if(x == 1) MCMF.add(0, i, 1, 0); } rep(i, 1, N+1){ int x; cin >> x; if(x == 1) MCMF.add(i, N+1, 1, 0); } cout << MCMF.match() << '\n'; } 🔒 구현 코드 잠금