1210 마피아 https://www.acmicpc.net/problem/1210
3640 제독 https://www.acmicpc.net/problem/3640
9413 제주도 관광 https://www.acmicpc.net/problem/9413
1. 도시 왕복하기
1번도시와 2번도시 사이를 왕복하려한다.
이 두 도시를 제외하고 방문한 도시는 다시 방문하지 않고 최대로 왔다갔다 할 수 있는 횟수를 구하는 문제다.
처음에 풀었던 소스를 보니 이해가 가지않아 다시 풀었는데
얼마 지나지 않아 재채점되어 처음에 풀었던 소스는 잘못된 소스였던것을 알 수 있었다.
보통 network flow 문제에서 간선을 지나지 않는것은 쉽게 설정할 수 있지만 정점은 그렇지 않다.
물론 분할된 정점사이에 용량은 해당 정점을 방문가능한 횟수이다.
3번정점에서 4번정점으로 가는 예를 들면
간선의 종류가 방향성이 있는 간선이면 3'에서 4만 연결해주면 되고
양방향 간선이라면 위와같이 3'에서4, 4'에서 3을 연결해주면 된다.
그 후에 최대유량(1-src, 2'-sink)을 구해주면 풀 수 있다.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define INF 987654321
int N, M;
int C[811][811], f[811][811];
vector<int> adj[811];
int work[811];
int level[811];
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) {
f[here][next] += get;
f[next][here] -= get;
return get;
}
}
}
return 0;
}
int main() {
scanf("%d%d", &N, &M);
for (int m = 0;m < M;m++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(2 * u, 2 * v - 1, INF);
add_edge(2 * v, 2 * u - 1, INF);
}
for (int n = 1;n <= N;n++) {
if (n <= 2) {
add_edge(2 * n - 1, 2 * n, INF);
}
else {
add_edge(2 * n - 1, 2 * n, 1);
}
}
int src = 2 * 1 - 1, sink = 2 * 2;
int ans = 0;
while (bfs(src, sink)) {
memset(work, 0, sizeof work);
while (1) {
int flow = dfs(src, sink, INF);
if (flow == 0) break;
ans += flow;
}
}
printf("%d\n", ans);
return 0;
}
| cs |
정점을 몇개 정해서 마피아들의 움직임을 제한하려한다.
정점을 점령할때 비용이 드는데 비용을 최소화하며 마피아들의 움직임을 막을 수 있는 정점을 구하는 문제다.
정점을 점령하는 비용을 정점분할하여 그 사이에 흐르는 용량으로 나타내고
일반간선은 무한의 용량을 갖게 한다.
마피아들의 시작점에서 도착점까지 용량을 흘러보내 흘러지는 최대유량이 비용의 합이 되겠다.
하지만 진정한 문제는 비용의 합을 구하는것이 아니라 그 정점을 구해야한다.
이것은 http://koosaga.com/41 를 참고했는데 원리는 간단하다.
visit[In[i]] = true , visit[Out[i]] = false 인 이유는 i번 정점까지 flow가 흘렀지만
내부 잔여 유량이 0이므로 이 정점이 점령한 정점임을 알 수 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
#define INF ((ll)1e18)
int N, M;
ll C[444][444], f[444][444];
vector<int> adj[444];
int level[444];
int work[444];
void add_edge(int u, int v, ll 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;
}
ll dfs(int here, int const sink, ll 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) {
ll get = dfs(next, sink, min(C[here][next] - f[here][next], flow));
if (get) {
f[here][next] += get;
f[next][here] -= get;
return get;
}
}
}
return 0;
}
int main() {
scanf("%d%d", &N, &M);
int src, sink;
scanf("%d%d", &src, &sink);
for (int n = 1;n <= N;n++) {
int val;
scanf("%d", &val);
add_edge(2 * n - 1, 2 * n, val);
}
for (int m = 0;m < M;m++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(2 * u, 2 * v - 1, INF);
add_edge(2 * v, 2 * u - 1, INF);
}
ll maxflow = 0;
while (bfs(src * 2 - 1, sink * 2)) {
memset(work, 0, sizeof work);
while (1) {
ll get = dfs(src * 2 - 1, sink * 2, INF);
if (!get) break;
maxflow += get;
}
}
vector<bool> visit(444, false);
queue<int> q;
visit[src * 2 - 1] = true;
q.push(src * 2 - 1);
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[2 * n - 1] && !visit[2 * n]) printf("%d ", n);
}
return 0;
}
| cs |
3. 제독
1에서 겹치지 않는 두 경로로 N까지 도달했을 때 최소 cost를 구하는 문제이다.
이 문제에서의 핵심은 "같은 중간 지점이나 같은 뱃길을 이용하면 안된다"이다.
(1과 N에서는 예외이다. 당연히 중첩될 수밖에 없으므로)
뱃길은 하나의 간선으로 표현될 수 있고 중첩되면 안되므로 capacity가 1인 간선이 되겠다.
1과 N은 capacity가 2로 정점분할을 해주고 나머지는 1로 해준다.(cost 0)
입력 받는 경로들은 capacity가 1, 입력받은 cost로 설정해준다.
src와 1, N과 sink를 capacity가 2, cost가 0인 간선으로 연결해준다.
이제 mcmf를 구해주면 된다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
struct MCMF {
struct Edge {
int v, rev, cap, cost;
Edge(int vv, int rrev, int ccap, int ccost) :v(vv), rev(rrev), cap(ccap), cost(ccost) {}
};
int size;
vector<vector<Edge>> edge;
MCMF(int s) :size(s) { edge.resize(size); }
void add_edge(int u, int v, int cap, int cost) {
edge[u].emplace_back(Edge(v, edge[v].size(), cap, cost));
edge[v].emplace_back(Edge(u, edge[u].size() - 1, 0, -cost));
}
int get_mcmf(int src, int sink) {
int ret = 0;
while (1) {
queue<int> q;
vector<int> dist(size, INF), par(size, -1), paridx(size, -1);
vector<bool> inQ(size, false);
q.push(src);
dist[src] = 0;
inQ[src] = true;
while (!q.empty()) {
int here = q.front();
q.pop();
inQ[here] = false;
for (int n = 0;n < edge[here].size(); n++) {
int next = edge[here][n].v;
int cap = edge[here][n].cap;
if (cap && dist[next] > dist[here] + edge[here][n].cost) {
par[next] = here;
paridx[next] = n;
dist[next] = dist[here] + edge[here][n].cost;
if (!inQ[next]) {
inQ[next] = true;
q.push(next);
}
}
}
}
if (par[sink] == -1) break;
for (int i = sink; i != src; i = par[i]) {
edge[par[i]][paridx[i]].cap--;
edge[i][edge[par[i]][paridx[i]].rev].cap++;
ret += edge[par[i]][paridx[i]].cost;
}
}
return ret;
}
};
int N, M;
int main() {
while (scanf("%d%d", &N, &M) != EOF) {
MCMF mcmf(2 * N + 3);
const int src = 0, sink = 2 * N + 1;
for (int n = 1;n <= N;n++) {
if (n == 1 || n == N) mcmf.add_edge(n, n + N, 2, 0);
else mcmf.add_edge(n, n + N, 1, 0);
}
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
mcmf.add_edge(u + N, v, 1, d);
}
mcmf.add_edge(src, 1, 2, 0);
mcmf.add_edge(N, sink, 2, 0);
printf("%d\n", mcmf.get_mcmf(src, sink));
}
return 0;
}
| cs |
mcmf 구조체를 위와 같이 사용하는데 굉장히 편리하다.
칙칙폭폭에서 해당 구조체의 진가가 발휘된다.
https://github.com/lyzqm123/MCMF
4. 제주도 관광
두 그룹이 그래프에서 여행을 한다.
이 그룹들은 그래프에서 같은 정점을 공유하는 여행을 하면 안된다.
두 그룹의 경로상에 정점들의 최대값을 구하는 문제이다.
제독문제와 굉장히 유사하다.
다른점은 시작점과 끝점이 정해져있지 않은 점과 간선은 중복되도 된다는 점이다.
1번 입력을 모델링하면 위의 그림과 같다.
대괄호 사이에 첫번째값이 용량, 두번째값이 비용이다.
(maximum cost를 구해야하므로 음수값 넣어줬다.)
P,Q라는 중간정점을 넣어 시작과 끝이 지정되있지 않아도 최대유량, 최대비용을 구할 수 있다.
4. 제주도 관광
두 그룹이 그래프에서 여행을 한다.
이 그룹들은 그래프에서 같은 정점을 공유하는 여행을 하면 안된다.
두 그룹의 경로상에 정점들의 최대값을 구하는 문제이다.
제독문제와 굉장히 유사하다.
다른점은 시작점과 끝점이 정해져있지 않은 점과 간선은 중복되도 된다는 점이다.
대괄호 사이에 첫번째값이 용량, 두번째값이 비용이다.
(maximum cost를 구해야하므로 음수값 넣어줬다.)
P,Q라는 중간정점을 넣어 시작과 끝이 지정되있지 않아도 최대유량, 최대비용을 구할 수 있다.
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int src, sink, P, Q;
vector<vector<int>> adj;
int C[666][666], f[666][666], d[666][666];
void init() {
memset(C, 0, sizeof C);
memset(f, 0, sizeof f);
memset(d, 0, sizeof d);
src = 2 * (N + 1), sink = 2 * (N + 2);
P = 2 * (N + 3), Q = 2 * (N + 4);
adj = vector<vector<int>>(2 * (N + 5), vector<int>());
}
void add_edge(int u, int v, int c, int dd) {
adj[u].push_back(v);
adj[v].push_back(u);
C[u][v] = c;
d[u][v] = dd;
d[v][u] = -dd;
}
// (in) : 2*u-2
// (out) : 2*u-1
int mcmf() {
int ret = 0;
while (1) {
queue<int> q;
vector<int> dist(2 * (N + 5), 0x3f3f3f3f);
vector<int> par(2 * (N + 5), -1);
vector<bool> inQ(2 * (N + 5), false);
q.push(src);
inQ[src] = true;
dist[src] = 0;
while (!q.empty()) {
int here = q.front();
q.pop();
inQ[here] = false;
for (int next : adj[here]) {
if (C[here][next] - f[here][next] > 0 && dist[next] > dist[here] + d[here][next]) {
dist[next] = dist[here] + d[here][next];
par[next] = here;
if (!inQ[next]) {
inQ[next] = true;
q.push(next);
}
}
}
}
if (par[sink] == -1) break;
int flow = 0x3f3f3f3f;
for (int i = sink;i != src;i = par[i])
flow = min(flow, C[par[i]][i] - f[par[i]][i]);
for (int i = sink;i != src;i = par[i])
f[par[i]][i] += flow, f[i][par[i]] -= flow, ret += flow*d[par[i]][i];
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &M);
init();
for (int m = 0;m < M;m++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(2*u - 1, 2*v - 2, 1, 0);
}
for (int n = 1;n <= N;n++) {
add_edge(2 * n - 2, 2 * n - 1, 1, -1);
add_edge(P, 2 * n - 2, 1, 0);
add_edge(2 * n - 1, Q, 1, 0);
}
add_edge(src, P, 2, 0);
add_edge(Q, sink, 2, 0);
printf("%d\n", -mcmf());
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기