알고리즘/백준
[백준] 1258 - 문제 할당
래울
2024. 7. 27. 14:22
잡담
대회나갈건 아니고, 취미로만 푸는 거라 대충대충 푸는데, 문제 맞힌 사람이 적어지니 다양한 풀이를 참고가 힘든게 단점 같다.
틀렸을 때 잘못된 부분 찾는게 시간이 너무 걸리는 듯
가끔 이왜틀 당하면 한 두 시간 훌쩍 감...
심심할 때 마다 알고리즘 폭을 넓이고 싶은데,
현생 이슈들도 있고, 싸피 프젝에 영어도 해야해서 시간이 없어서 평일 스트릭은 실버-골드로 연명하는 중
문제
https://www.acmicpc.net/problem/1258
네트워크 플로우, MCMF 문제
그래도 이 문제는 쉬운편
source와 sink에 대해 간선 용량을 잘 설정해주고, 유량 돌려주면 된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <unordered_map>
using namespace std;
int N, M;
int capacity[222][222];
int flow[222][222];
int cost[222][222];
int check[222];
int answer[222];
int sink = 201;
int source = 0;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 1; i <= N; ++i)
{
capacity[source][i] = 1;
capacity[100 + i][sink] = 1;
for(int j = 1; j <= N; ++j)
{
int a;
cin >> a;
cost[i][j + 100] = a;
cost[j + 100][i] = -a;
capacity[i][j + 100] = 99999999;
}
}
int r = 0;
int rcost = 0;
while (true)
{
int parent[222];
memset(parent, -1, sizeof(parent));
memset(check, 0, sizeof(check));
int answer[222];
for (int i = 0; i <= sink; ++i) answer[i] = 987654321;
queue<int> q;
answer[source] = 0;
q.push(source);
parent[source] = source;
check[source] = 1;
while (!q.empty())
{
int now = q.front();
q.pop();
check[now] = 0;
for (int i = 0; i <= sink; ++i)
{
if (capacity[now][i] - flow[now][i] <= 0) continue;
int nxtCost = cost[now][i] + answer[now];
if (nxtCost >= answer[i]) continue;
answer[i] = nxtCost;
parent[i] = now;
if (check[i] == 0)
{
check[i] = 1;
q.push(i);
}
}
}
if (parent[sink] == -1) break;
int mv = 987654321;
for (int i = sink; i != source; i = parent[i])
{
//cout << i << " ";
mv = min(mv, capacity[parent[i]][i] - flow[parent[i]][i]);
}
//cout << "\n";
for (int i = sink; i != source; i = parent[i])
{
flow[parent[i]][i] += mv;
flow[i][parent[i]] -= mv;
rcost += mv * cost[parent[i]][i];
}
r += mv;
}
cout << rcost;
return 0;
}