백준 13161 (C++) 분단의 슬픔

최초 업로드: 2025-04-21 20:51:52

최근 수정 시간: 2025-07-25 09:23:54

게시자: rlatjwls3333

카테고리: 백준

# [Platinum I] 분단의 슬픔

#### [문제 링크](https://www.acmicpc.net/problem/13161)

## 문제 설명

UCPC에는 N명의 사람이 있다. 먼 옛날 쇼킹핫치킨에 대한 논쟁에서 시작된 이념의 대립으로 UCPC에는 kriii를 따르는 쇼킹핫진보 진영 A와, august14를 따르는 쇼킹핫보수 진영 B의 두 진영이 존재한다. 모든 사람은 둘 중 한 진영에 소속되어 있으며, 두 진영에 동시에 들어가는 것은 불가능하다.

i번 사람과 j번 사람에 대해 서로 다른 진영에 들어가게 될 경우 슬픈 정도 w[i, j]가 주어진다. 일부 사람들은 쇼킹핫에 관한 자신의 철학이 강해 무조건 A진영에 들어가는 사람도 있고, 무조건 B진영에 들어가는 사람도 있다. 물론 치킨은 무엇이든 옳으므로 두 진영 어디에 가든 상관없는 사람도 있다.

N명의 사람들이 적절히 두 진영에 나누어 들어갈 때, 슬픔 정도의 합이 최소가 되게 하라.

## 입력

첫 번째 줄에는 UCPC 구성원의 수 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, i번째 수가 1이면 i번 사람은 무조건 A진영에 들어가야 함을, 2라면 무조건 B진영에 들어가야 함을, 0이면 어느 진영에 들어가든지 상관 없다는 것을 의미한다.

세 번째 줄부터 N개의 줄에 걸쳐 i번 사람과 j번 사람이 다른 진영에 들어갈 때의 슬픔 정도 w[i, j]가 주어진다. (i+2)번째 줄에 j번째 수는 w[i, j]를 의미한다. 주어지는 입력은 항상 w[i, j]=w[j, i]를 만족하고, w[i, i]=0이다. w[i, j]는 1,000보다 크지 않은 음이 아닌 정수이다.

## 출력

첫 줄에 N명의 사람이 A, B 두 진영에 적절히 들어가 슬픈 정도의 합이 최소가 될 때의 슬픔 정도의 합을 출력한다. 두 번째 줄에는 슬픈 정도의 합이 최소가 될 때 A진영에 들어가는 사람들의 번호를 공백으로 구분하여 출력하고, 세 번째 줄에는 슬픈 정도의 합이 최소가 될 때 B진영에 들어가는 사람들의 번호를 공백으로 구분하여 출력한다. 만약 한 진영에 사람이 한 명도 들어가지 않은 경우 빈 줄을 출력한다. 가능한 경우가 여러 가지인 경우 그중 아무거나 하나 출력한다.

## 풀이
#### N이 작고 E가 커서 디닉 알고리즘으로 풀어야 한다. A진형에 들어가야만 하는 사람을 source에 연결하고, B진형에 들어가야만 하는 사람을 sink에 연결하여 최대 유량을 흐르게 하여 최대 컷을 찾으면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 502;
const int S = MAX-2, E = MAX-1;
const int INF = 0x3f3f3f3f;

int c[MAX][MAX], f[MAX][MAX], level[MAX], work[MAX];
vector<vector<int>> conn(MAX);

bool bfs() {
 queue<int> q; q.push(S);
 memset(level, -1, sizeof level);
 level[S]=0;
 while(!q.empty()) {
 int cur = q.front(); q.pop();
 for(int next:conn[cur]) {
 if(level[next]==-1 && c[cur][next]-f[cur][next]>0) {
 level[next] = level[cur]+1;
 q.push(next);
 }
 }
 }
 return level[E]!=-1;
}

int dfs(int cur, int curFlow) {
 if(cur==E) return curFlow;
 for(int &i=work[cur];i<conn[cur].size();i++) {
 int next = conn[cur][i];
 if(level[next]==level[cur]+1 && c[cur][next]-f[cur][next]>0) {
 int flow = dfs(next, min(curFlow, c[cur][next]-f[cur][next]));
 if(flow>0) {
 f[cur][next] += flow;
 f[next][cur] -= flow;
 return flow;
 }
 }
 }
 return 0;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n;i++) {
 int type; cin >> type;
 if(type==1) {
 conn[S].push_back(i);
 conn[i].push_back(S);
 c[S][i]=INF;
 } else if(type==2) {
 conn[E].push_back(i);
 conn[i].push_back(E);
 c[i][E]=INF;
 }
 }

for(int i=0;i<n;i++) {
 for(int j=0;j<n;j++) {
 cin >> c[i][j];
 if(i!=j) conn[i].push_back(j);
 }
 }

int totalFlow=0;
    while(bfs()) {
        memset(work, 0, sizeof work);
        while(true) {
            int flow = dfs(S, INF);
            if(flow==0) break;
            totalFlow += flow;
        }
    }

bfs();
 vector<int> A, B;
 for(int i=0;i<n;i++) {
 if(level[i]==-1) B.push_back(i+1);
 else A.push_back(i+1);
 }

cout << totalFlow << '\n';
 for(int e:A) cout << e << ' '; cout << '\n';
 for(int e:B) cout << e << ' '; cout << '\n';
}
```