백준 31483 (C++) Supporting everyone

최초 업로드: 2025-11-02 07:48:28

최근 수정 시간: 2025-11-02 07:55:55

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] Supporting everyone

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

## 문제 설명

Alice is attending a sport event with many national teams and one thing is important to her: supporting every country.

There are $N$ countries represented and she has two ways to support a country: either have the flag drawn on her or have a pin with the name of the country. Alice has a list containing, for each country, the colours needed to make its flag. A total of $M$ colours that may appear across all flags and, in Alice’s list, each colour is conveniently represented as an integer between $1$ and $M$.

Each crayon and pin cost $1$, but her budget is tight. . . Can you help her find the minimum she can spend to support everyone?

## 입력

The first line contains the two space-separated numbers $N$ and $M$. Then follow $2N$ lines, grouped in pairs; the $(2i - 1)$th and $2i$th lines represent the $i$th country. More precisely, the $(2i - 1)$th line contains a single integer $k_i$: the number of colours in the flag of the $i$th country. Then, the $2i$th line contains $k_i$ space-separated numbers $c_{i,1}, c_{i,2}, \dots , c_{i,k_i}$; these are the colours in the flag of the $i$th country.

## 출력

The output should contain a single line, consisting of a single number: the minimum amount Alice can spend on crayons and pins to represent every country.

## 풀이
쾨닉의 정리에 따르면 Maximum Bipartite Matching과 Minimum Vertex Cover이 같고, 최대 유량 최소 컷 정리에 따라 S -> 국기 -> 색 -> E로 그래프를 형성하고 유량을 흘려보내주면 최소 비용이 나온다. 만약 국기에 포함되는 색의 수만큼 색이 선택되지 않는다면 개별 국기를 사는 것으로 치환하여 생각하면 되고, 국기에 포함되는 색의 수만큼 전부 선택된다면 더 이상 그 색으론 플로우가 못 흐르기 때문에 선택되지 않아 cost가 늘지 않는다.

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

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

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

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

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

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=1;i<=m;i++) { // 색 -> E
 conn[i+n].push_back(E);
 conn[E].push_back(i+n);
 cap[i+n][E]=1;
 }
 for(int i=1;i<=n;i++) {
 // 국기 -> 색
 int k; cin >> k;
 while(k--) {
 int c; cin >> c;
 conn[i].push_back(c+n);
 conn[c+n].push_back(i);
 cap[i][c+n]=1;
 }

// S -> 국기
        conn[S].push_back(i);
        conn[i].push_back(S);
        cap[S][i]=1;
    }

int flow=0;
 while(bfs()) {
 memset(work, 0, sizeof work);
 while(true) {
 int curFlow = dfs();
 if(!curFlow) break;
 flow += curFlow;
 }
 }
 cout << flow;
}
```