13161 분단의 슬픔 https://www.acmicpc.net/problem/13161
1. 가구 공장
SCPC 2회 예선에 나왔던 "구두제작"이라는 문제와 거의 비슷한 문제다.
다만 여기서는 Edmonds Karp algorithm을 사용하면 TLE가 나므로 dinic algorithm으로 풀고
제작 스케줄 또한 구해야 한다.
구두제작에서 풀었던것과 같이 모델링하는것은 변함없다.
src ↔ 직원 ↔ 시간 ↔ 가구 ↔ sink
최대 유량이 흘러지면 가구를 만들 수 있는것이다.
그리고 스케줄을 구해야하는데 문제를 잘못읽어 뻘짓을 좀 했다.
중첩되는 부분이있으면 그 부분을 통일 시켜주면 된다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
struct Save {
int l, r;
int man;
Save(int ll, int rr, int mm) :l(ll), r(rr), man(mm) {}
};
int N, M; //직원, 가구
int C[666][666], f[666][666];
int level[666];
int work[666];
vector<vector<int>> adj;
void add_edge(int u, int v, int c) {
adj[u].push_back(v);
adj[v].push_back(u);
C[u][v] = c;
}
bool bfs(int src, int sink) {
memset(level, -1, sizeof level);
queue<int> q;
level[src] = 0;
q.push(src);
while (!q.empty()) {
int here = q.front();
q.pop();
for (int next : adj[here]) {
if (level[next] == -1 && C[here][next] - f[here][next] > 0) {
level[next] = level[here] + 1;
q.push(next);
}
}
}
return level[sink] != -1;
}
int dfs(int here, int const sink, int flow) {
if (here == sink) return flow;
for (int &n = work[here];n < adj[here].size();n++) {
int next = adj[here][n];
if (level[next] == level[here] + 1 && C[here][next] - f[here][next] > 0) {
int get = dfs(next, sink, min(C[here][next] - f[here][next], flow));
if (get > 0) {
f[here][next] += get;
f[next][here] -= get;
return get;
}
}
}
return 0;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(C, 0, sizeof C);
memset(f, 0, sizeof f);
int sum = 0, src = 0, sink = 665;
scanf("%d%d", &N, &M);
adj = vector<vector<int>>(666, vector<int>());
int minS = 0x3f3f3f3f, maxD = 0;
for (int m = 1;m <= M;m++) {
int s, w, d;
scanf("%d%d%d", &s, &w, &d);
sum += w;
minS = min(minS, s);
maxD = max(maxD, d);
for (int i = s;i < d;i++)
add_edge(i, 500 + m, 1); //시간 <-> 가구
add_edge(500 + m, sink, w); //가구 <-> sink
}
for (int n = 1;n <= N;n++) {
add_edge(src, 500 + M + n, maxD - minS); //src <-> 직원
for (int i = minS;i < maxD;i++)
add_edge(500 + M + n, i, 1); //직원 <-> 시간
}
int maxflow = 0;
while (bfs(src, sink)) {
memset(work, 0, sizeof work);
while (1) {
int flow = dfs(src, sink, INF);
if (flow == 0) break;
maxflow += flow;
}
}
if (maxflow == sum) {
vector<vector<Save>> tmp(M + 1, vector<Save>());
for (int m = 1;m <= M;m++) {
for (int t = minS;t < maxD;t++) {
if (f[t][500 + m]) {
f[t][500 + m] = 0;
tmp[m].push_back(Save(t, t + 1, -1));
}
}
}
vector<vector<Save>> ans(M + 1, vector<Save>());
for (int m = 1;m <= M;m++) {
if (tmp[m].size() == 1) {
ans[m].push_back(tmp[m][0]);
}
else if(!tmp[m].empty()){
int l = tmp[m][0].l;
int Size = (int)tmp[m].size();
for (int n = 1;n < Size;++n) {
Save &here = tmp[m][n], &prev = tmp[m][n - 1];
if (n == Size - 1) {
if (here.l != prev.r) {
ans[m].push_back(Save(l, prev.r, prev.man));
ans[m].push_back(Save(here.l, here.r, here.man));
}
else ans[m].push_back(Save(l, here.r, here.man));
break;
}
if (here.l == prev.r) continue;
else {
ans[m].push_back(Save(l, prev.r, prev.man));
l = here.l;
}
}
}
}
for (int m = 1;m <= M;m++) {
printf("%d ", (int)ans[m].size());
for (int n = 0;n < ans[m].size();n++) {
printf("%d %d ", ans[m][n].l, ans[m][n].r);
}
printf("\n");
}
}
else printf("0\n");
}
return 0;
}
| cs |
2. 분단의 슬픔
최소 컷을 구해야하는 문제이다.
완전 그래프를 만들고 src에서 bfs를 돌리며
유량을 더 보낼 수 있는 쪽이 A진영에 포함되있는 것이다.
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define INF 987654321
int N;
vector<int> adj[503];
int C[503][503], f[503][503];
int level[503];
int work[503];
bool bfs(int src, int sink) {
queue<int> q;
memset(level, -1, sizeof level);
level[src] = 0;
q.push(src);
while (!q.empty()) {
int here = q.front();
q.pop();
for (int &next : adj[here]) {
if (level[next] == -1 && C[here][next] - f[here][next] > 0) {
level[next] = level[here] + 1;
q.push(next);
}
}
}
return level[sink] != -1;
}
int dfs(int here, int const sink, int flow) {
if (here == sink) return flow;
for (int &i = work[here]; i < adj[here].size(); i++) {
int next = adj[here][i];
if (level[next] == level[here] + 1 && C[here][next] - f[here][next] > 0) {
int get = dfs(next, sink, min(C[here][next] - f[here][next], flow));
if (get > 0) {
f[here][next] += get;
f[next][here] -= get;
return get;
}
}
}
return 0;
}
int main() {
scanf("%d", &N);
int src = 0, sink = N + 1;
for (int n = 1;n <= N;n++) {
int tmp;
scanf("%d", &tmp);
if (tmp == 1) {
C[src][n] = INF;
adj[src].push_back(n);
adj[n].push_back(src);
}
else if (tmp == 2) {
C[n][sink] = INF;
adj[n].push_back(sink);
adj[sink].push_back(n);
}
}
for (int n = 1;n <= N;n++) {
for (int m = 1;m <= N;m++) {
scanf("%d", &C[n][m]);
if (n != m) adj[n].push_back(m);
}
}
int maxflow = 0;
while (bfs(src,sink)) {
memset(work, 0, sizeof work);
while (1) {
int flow = dfs(src, sink, INF);
if (flow == 0) break;
maxflow += flow;
}
}
printf("%d\n", maxflow);
vector<bool> visit(503, false);
queue<int> q;
q.push(src);
visit[src] = true;
while (!q.empty()) {
int here = q.front();
q.pop();
for (int next : adj[here]) {
if (!visit[next] && C[here][next] - f[here][next] > 0) {
visit[next] = true;
q.push(next);
}
}
}
for (int n = 1;n <= N;n++) if (visit[n]) printf("%d ", n);
printf("\n");
for (int n = 1;n <= N;n++) if (!visit[n]) printf("%d ", n);
printf("\n");
return 0;
}
| cs |
