14904 이동하기2 https://www.acmicpc.net/problem/14904
1420 학교 가지마! https://www.acmicpc.net/problem/1420
1. 왕복 여행
양방향 간선을 가진 그래프가 존재한다.
1번정점에서 N번정점을 찍고 다시 1번정점으로 오려 하는데 간선을 중복되게 이용할 수 없다.
최소 시간을 구하는 문제다.
처음에 dijkstra로 풀려고했는데 마땅한 방법이 생각나지 않아서 mcmf로 모델링하였다.
근데 이 문제는 양방향 간선이다.
양방향 간선의 cost값이 동일한데 d[u][v] = -d[v][u]를 나타냄에 있어서 매우 곤란해진다.
이럴때도 정점분할로 해결할 수 있다.
정점사이의 capacity를 2(또는 INF)로 주고 in정점은 out정점, out정점은 in정점에 연결해주면 된다.
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 2006
int N, M;
vector<int> adj[MAX];
int C[MAX][MAX], f[MAX][MAX], d[MAX][MAX];
bool inQ[MAX];
int par[MAX];
int dist[MAX];
int src, sink;
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;
}
int mcmf() {
int ret = 0;
while (1) {
memset(inQ, false, sizeof inQ);
memset(par, -1, sizeof par);
memset(dist, 0x3f, sizeof dist);
queue<int> q;
inQ[src] = true;
dist[src] = 0;
q.push(src);
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() {
scanf("%d%d", &N, &M);
src = 0, sink = 2 * N - 1;
for (int n = 1;n <= N;n++)
add_edge(2 * n - 2, 2 * n - 1, 2, 0);
for (int m = 0;m < M;m++) {
int u, v, dd;
scanf("%d%d%d", &u, &v, &dd);
add_edge(2 * u - 1, 2 * v - 2, 1, dd);
add_edge(2 * v - 1, 2 * u - 2, 1, dd);
}
printf("%d\n", mcmf());
return 0;
}
| cs |
이 방법 외에도 mcmf구조체를 만들어주면 정점분할을 하지않고도 해결할 수 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct MCMF {
struct Edge {
int v, c, d;
int rev;
Edge() {}
Edge(int vv, int rr, int cc, int dd) :v(vv), rev(rr), c(cc), d(dd) {}
};
MCMF(int N) :size(N) { edge.resize(N); }
int size;
vector<vector<Edge>> edge;
void add_edge(int u, int v, int c, int d) {
edge[u].push_back(Edge(v, edge[v].size(), c, d));
edge[v].push_back(Edge(u, edge[u].size() - 1, 0, -d));
}
int solve(const int src, const int sink) {
int ret = 0;
while (1) {
queue<int> q;
vector<int> par(size, -1);
vector<int> paridx(size, -1);
vector<int> dist(size, 0x3f3f3f3f);
vector<bool> inQ(size, false);
dist[src] = 0;
inQ[src] = true;
q.push(src);
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;
if (edge[here][n].c && dist[next] > dist[here] + edge[here][n].d) {
dist[next] = dist[here] + edge[here][n].d;
par[next] = here;
paridx[next] = n;
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, edge[par[i]][paridx[i]].c);
}
for (int i = sink;i != src;i = par[i]) {
edge[par[i]][paridx[i]].c -= flow;
edge[i][edge[par[i]][paridx[i]].rev].c += flow;
ret += (flow * edge[par[i]][paridx[i]].d);
}
}
return ret;
}
};
int N, M;
int src, sink;
int main() {
scanf("%d%d", &N, &M);
src = 0, sink = N + 1;
MCMF mcmf(N + 2);
mcmf.add_edge(src, 1, 2, 0);
mcmf.add_edge(N, sink, 2, 0);
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
mcmf.add_edge(u, v, 1, d);
mcmf.add_edge(v, u, 1, d);
}
printf("%d\n", mcmf.solve(src, sink));
return 0;
}
| cs |
2. 이동하기2
N*N미로에서 준규는 [1,1]에 위치하고 있다.
각 미로방에는 사탕이 있으며 각 방을 방문하면 그 방에있는 모든 사탕을 가져간다.
준규는 오른쪽 또는 아래로 갈 수 있고 [N,N]으로 총 K번 이동하려고 한다.
이때 얻을 수 있는 사탕의 최대값을 구하는 문제다.
간단한 dp문제인줄 알고 [1,1]에서 [N,N]으로 가는 사탕의 최댓값을 구하고
최댓값을 얻은 길을 0으로 초기화하여 K번 반복하면 되겠구나
싶어 바로 구현하고 제출했더니 틀렸다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, K;
int dp[55][55];
int map[51][51];
int ans = 0;
int solve(int y, int x) {
if (y == N - 1 && x == N - 1) return dp[y][x] = map[y][x];
if (y < 0 || y >= N || x < 0 || x >= N) return -INF;
int &ret = dp[y][x];
if (ret != -1) return ret;
ret = max(solve(y + 1, x) + map[y][x], solve(y, x + 1) + map[y][x]);
return ret;
}
void reconstruct(int y, int x) {
map[y][x] = 0;
if (y == N - 1 && x == N - 1) return;
if (dp[y + 1][x] < dp[y][x + 1]) {
reconstruct(y, x + 1);
}
else {
reconstruct(y + 1, x);
}
}
int main() {
scanf("%d%d", &N, &K);
for (int n = 0;n < N;n++)for (int m = 0;m < N;m++) scanf("%d", &map[n][m]);
while (K--) {
memset(dp, -1, sizeof dp);
ans += solve(0, 0);
reconstruct(0, 0);
}
printf("%d\n", ans);
return 0;
}
| cs |
곰곰히 생각해보니 이러한 greedy방법은 어디선가 반례가 있을 것 같았다.
(예시 - K가 3이고 9, 7, 3 도합 19를 얻었지만 7, 7, 6로 20이 최댓값인 데이터)
마땅한 방법이 떠올리지 않을 찰라에 flow 모델링이 떠올려졌다.
최대유량만으로 구하기는 불가능할것같고 mcmf로 잘 모델링하면 될것같았다.
분할한 정점 사이에 용량 1, cost는 사탕값만큼 주고
이 정점에서 사탕을 먹었어도 유량이 흐를 수 있게 K-1만큼의 용량도 준다면 될것같았다.
(처음에 K의 용량을 주었는데 값이 제대로 안나와 틀린 모델링인줄 알았다. K-1로 해줘야한다)
오른쪽, 아래로 이동하는것을 정점끼리 연결해 주면 된다.(용량 K, cost 0)
그다음에 maximum cost를 구하면 된다.
여담이지만 최대로 들어오면 정점이 5000개 생기는데도 시간안에 잘 돌아간다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define INF 987654321
int N, K;
// 2*x , 2*x + 1
int src, sink;
int map[51][51];
struct MCMF {
struct Edge {
int v, rev, cost, cap;
Edge(int vv, int rr, int ccost, int ccap) :v(vv), rev(rr), cost(ccost), cap(ccap) {}
};
int s;
vector<vector<Edge>> edge;
MCMF(int size) :s(size + 2) { edge.resize(s + 1); }
void add_edge(int u, int v, int cost, int cap) {
edge[u].emplace_back(Edge(v, edge[v].size(), cost, cap));
edge[v].emplace_back(Edge(u, edge[u].size() - 1, -cost, 0));
}
int getMCMF(int src, int sink) {
int ret = 0;
while (1) {
queue<int> q;
vector<bool> inQ(s + 1, false);
vector<int> dist(s + 1, INF);
vector<int> par(s + 1, -1), paridx(s + 1, -1);
dist[src] = 0;
inQ[src] = true;
q.push(src);
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) {
dist[next] = dist[here] + edge[here][n].cost;
par[next] = here;
paridx[next] = n;
if (!inQ[next]) {
inQ[next] = true;
q.push(next);
}
}
}
}
if (par[sink] == -1) break;
int flow = INF;
for (int i = sink;i != src;i = par[i]) {
int prev = par[i];
int idx = paridx[i];
flow = min(flow, edge[prev][idx].cap);
}
for (int i = sink; i != src; i = par[i]) {
int prev = par[i];
int idx = paridx[i];
edge[prev][idx].cap -= flow;
edge[i][edge[prev][idx].rev].cap += flow;
ret += flow * edge[prev][idx].cost;
}
}
return ret;
}
};
int change(int x, bool isIn) {
if (isIn) return 2 * x;
else return 2 * x + 1;
}
int main() {
scanf("%d%d", &N, &K);
src = change(0, true), sink = change(N*N - 1, false);
MCMF mcmf(2*N*N);
for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) {
int cost;
scanf("%d", &cost);
mcmf.add_edge(change(n*N + m, true), change(n*N + m, false), -cost, 1);
mcmf.add_edge(change(n*N + m, true), change(n*N + m, false), 0, K - 1);
}
for (int n = 0;n < N;n++) {
for (int m = 0;m < N;m++) {
if (n + 1 < N) {
mcmf.add_edge(change(n*N + m, false), change((n + 1)*N + m, true), 0, K);
}
if (m + 1 < N) {
mcmf.add_edge(change(n*N + m, false), change(n*N + m + 1, true), 0, K);
}
}
}
printf("%d\n", -mcmf.getMCMF(src, sink));
return 0;
}
| cs |
3. 학교 가지마!
지도가 주어진다.
K위치에서 H위치로 이동할 때 벽을 최소로 막아서 이동할 수 없도록 만드는 문제이다.
마피아문제와 비슷하다. (오히려 조금 더 쉽다)
벽을 막는다는 행위는 src에서 sink로 갈 때 용량에 제한을 주어 모델링 할 수 있다.
정점분할을 통해서 아래와 같이 나타 낼 수 있다.
src와 sink는 정점간의 용량을 INF로 해야 한다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321
int N, M;
char map[101][101];
int sy, sx;
int ey, ex;
const int dy[] = { 0, 1, 0, -1 };
const int dx[] = { 1, 0, -1, 0 };
struct Mincut{
struct Edge{
int v, c, rev;
Edge(){}
Edge(int vv, int cc, int rrev) :v(vv), c(cc), rev(rrev){}
};
Mincut(){}
Mincut(int s) : size(s){ edge.resize(s); }
int size;
vector<vector<Edge>> edge;
void add_edge(int u, int v, int c){
edge[u].push_back(Edge(v, c, edge[v].size()));
edge[v].push_back(Edge(u, 0, edge[u].size() - 1));
}
int solve(int src, int sink){
int ret = 0;
while (1){
queue<int> q;
vector<int> par(size, -1);
vector<int> paridx(size, -1);
q.push(src);
while (!q.empty()){
int here = q.front();
q.pop();
for (int n = 0; n < edge[here].size(); ++n){
int next = edge[here][n].v;
int cap = edge[here][n].c;
if (cap > 0 && par[next] == -1){
par[next] = here;
paridx[next] = n;
q.push(next);
if (next == sink) break;
}
}
}
if (par[sink] == -1) break;
int flow = INF;
for (int i = sink; i != src; i = par[i]){
flow = min(flow, edge[par[i]][paridx[i]].c);
}
for (int i = sink; i != src; i = par[i]){
edge[par[i]][paridx[i]].c -= flow;
edge[i][edge[par[i]][paridx[i]].rev].c += flow;
}
ret += flow;
}
return ret;
}
};
int main(){
scanf("%d%d", &N, &M);
for (int n = 0; n < N; n++) scanf("%s", &map[n]);
for (int n = 0; n < N; n++) for (int m = 0; m < M; m++){
if (map[n][m] == 'K'){
sy = n, sx = m;
}
else if (map[n][m] == 'H'){
ey = n, ex = m;
}
}
Mincut mincut(N*M * 4 + 10);
for (int n = 0; n < N; n++) for (int m = 0; m < M; m++){
// in - 2*x, out - 2*x + 1
if (map[n][m] == '#') continue;
if ((n == sy && m == sx) || (n == ey && m == ex)) mincut.add_edge((n*M + m) * 2, (n*M + m) * 2 + 1, INF);
else mincut.add_edge((n*M + m) * 2, (n*M + m) * 2 + 1, 1);
for (int i = 0; i < 4; i++){
int ny = n + dy[i], nx = m + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || map[ny][nx] == '#') continue;
mincut.add_edge((n*M + m) * 2 + 1, (ny*M + nx) * 2, INF);
mincut.add_edge((ny*M + nx) * 2 + 1, (n*M + m) * 2, INF);
}
}
int ans = mincut.solve((sy*M + sx) * 2, (ey * M + ex) * 2 + 1);
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기