글 읽기 - 삽질 좀 한 문제입니다.. 왜 틀렸을 까요 !!

cokcjswo 7년 전 0

의식의 흐름은 다음과 같습니다.

1. 기존의 종만북 바탕의 네트워크 플로우 작성 -> 어 capacity, flow 배열이 못잡을 정도로 겁나 커지네 구조체로 간선 만들어야겠다.

2. kks님 블로그 참조해서 구조체 edge 기준으로 maxflow 재작성 -> 어 알고보니 cut이 정점에 생기는거니까 정점을 쪼개 줬어야 했네.

3. (i,j) 정점 쪼개서 in 정점은 i*m+j 값의 인덱스 가지게, out 정점은 i*m+j + 10000 값의 인덱스 가지게 매핑.

4. 아무리 벽 놓아도 K, H가 이어지지 않는 경우는 처음에 K,H가 인접해 있는 경우구나 !! 이거 맨 먼저 걸러줘야지

아무래도 3번에 문제가 있는 것 같은데요... 고수님들의 도움 바랍니다 ㅜㅜ

오랫만에 유량 개념 감좀 잡을려고 했는데 어렵네유 ㅜㅜ

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXV 40100
using namespace std;


struct Edge {
    int f,c,to;
    Edge *dual;
    Edge() : Edge(-1,0) {}
    Edge(int to, int c) : to(to), c(c), f(0) {}
    int spare() {
        return c-f;
    }
    void addFlow(int f1) {
        f += f1;
        dual->f -= f1;
    }
};
 
 
int n,m;
int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
vector<Edge*> adj[MAXV];

bool ok(int y, int x) {
    return y>=0 && y<n && x>=0 && x<m;
}

int MaxFlow(int source, int sink) {
    int totalFlow = 0;
    while(1) {
        int amount = INF;
        queue<int> q;
        vector<int> parent(MAXV, -1);
        parent[source] = source;
        q.push(source);
        Edge *path[MAXV] = {};
        while(!q.empty() && parent[sink] == -1) {
            int here = q.front();
            q.pop();
            for(int i=0;i<adj[here].size();i++) {
                Edge *e = adj[here][i];
                int next = e->to;
                if(e->spare() > 0 && parent[next] == -1) {
                    parent[next] = here;
                    path[next] = e;
                    q.push(next);
                }
            }
        }

        if(parent[sink] == -1)  break;
        for(int i=sink; i!= source; i=parent[i])            amount = min(amount, path[i]->spare());
        for(int i=sink; i!= source; i=parent[i])            path[i]->addFlow(amount);
        totalFlow += amount;
    }
    return totalFlow;
}
 
int main () {
    scanf("%d%d",&n,&m);
    char a[111][111];

    for(int i=0;i<n;i++)    scanf("%s",a[i]);

    bool no = false;
    int kp, hp;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i][j] == 'K') { 
                kp = i*m + j;
                for(int k=0;k<4;k++) {
                    int ny = i + dy[k], nx = j + dx[k];
                    if(ok(ny,nx) && a[ny][nx] == 'H')
                        no = true;
                }
            }
            if(a[i][j] == 'H')
                hp = i*m + j;
        }
    }

    if(no) {
        printf("-1\n");
        return 0;
    }

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            for(int k=0;k<2;k++) {
                int ny = i + dy[k], nx = j + dx[k];
                if(ok(ny,nx) && a[i][j] != '#' && a[ny][nx] != '#') {
                    Edge *e1 = new Edge(ny*m + nx, 1), *e2 = new Edge(i*m + j, 1);
                    Edge *e3 = new Edge(ny*m + nx + 10000, 1), *e4 = new Edge(i*m + j + 10000, 1);
                    e1 -> dual = e4;                    e2 -> dual = e3;
                    e4 -> dual = e1;                    e3 -> dual = e2;
                    adj[i*m + j + 10000].push_back(e1);     adj[ny*m + nx].push_back(e4);
                    adj[ny*m + nx + 10000].push_back(e2);   adj[i*m + j].push_back(e3);
                }
            }
        }
    }

    printf("%d\n",MaxFlow(kp,hp));
}

zlzmsrhak 7년 전 1

1. 제 컴퓨터에서는 예제가 0이 나오는데 잘못된건가요?

2. dual 변수가 역간선인 것 같은데 e1의 역간선이 e4인 것은 이해가 잘 되지 않습니다.

cokcjswo 7년 전 0

답변 감사합니다.

1. 잦은 수정으로 잘못된 버전의 소스를 올렸네요 죄송합니다 !

고친 소스를 댓글에 첨부합니다.

이렇게 좌표로 주어진 정점을 네트워크 플로우에 많이 활용 해보지 않아 실수 한 것 같습니다

다음과 같이 수정해보았는데 어떤지요?

주석 참고해주시면 감사하겠습니다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXV 40100
using namespace std;


struct Edge {
    int f,c,to;
    Edge *dual;
    Edge() : Edge(-1,0) {}
    Edge(int to, int c) : to(to), c(c), f(0) {}
    int spare() {
        return c-f;
    }
    void addFlow(int f1) {
        f += f1;
        dual->f -= f1;
    }
};
 
 
int n,m;
int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
vector<Edge*> adj[MAXV];

bool ok(int y, int x) {
    return y>=0 && y<n && x>=0 && x<m;
}

int MaxFlow(int source, int sink) {
    int totalFlow = 0;
    while(1) {
        int amount = INF;
        queue<int> q;
        vector<int> parent(MAXV, -1);
        parent[source] = source;
        q.push(source);
        Edge *path[MAXV] = {};
        while(!q.empty() && parent[sink] == -1) {
            int here = q.front();
            q.pop();
            for(int i=0;i<adj[here].size();i++) {
                Edge *e = adj[here][i];
                int next = e->to;
                if(e->spare() > 0 && parent[next] == -1) {
                    parent[next] = here;
                    path[next] = e;
                    q.push(next);
                }
            }
        }

        if(parent[sink] == -1)  break;
        for(int i=sink; i!= source; i=parent[i])		amount = min(amount, path[i]->spare());
        for(int i=sink; i!= source; i=parent[i])		path[i]->addFlow(amount);
        totalFlow += amount;
    }
    return totalFlow;
}
 
int main () {
    scanf("%d%d",&n,&m);
    char a[111][111];

    for(int i=0;i<n;i++)    scanf("%s",a[i]);

    bool no = false;
    int kp, hp;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i][j] == 'K') { 
                kp = i*m + j;
                for(int k=0;k<4;k++) {
                    int ny = i + dy[k], nx = j + dx[k];
                    // K에서 주위 4방향으로의 간선 세팅입니다.
                    if(ok(ny,nx)) {
	                    Edge *e5 = new Edge(i*m+j, 1), *e6 = new Edge(ny*m+nx+10000, 1);
	                    e5 -> dual = e6;	e6 -> dual = e5;
	                    adj[i*m + j].push_back(e6);		adj[ny*m + nx + 10000].push_back(e5);
	              		if(a[ny][nx] == 'H')	no = true;
	              }
                }
            }
            if(a[i][j] == 'H') {
                hp = i*m + j;
                for(int k=0;k<4;k++) {
                		int ny = i + dy[k], nx = j + dx[k];
                        // H에서 주위 4방향으로의 간선 세팅입니다.
                		if(ok(ny,nx)) {
                    		Edge *e5 = new Edge(i*m+j, 1), *e6 = new Edge(ny*m+nx+10000, 1);
                    		e5 -> dual = e6;	e6 -> dual = e5;
                    		adj[i*m + j].push_back(e6);		adj[ny*m + nx + 10000].push_back(e5);
                		}
                }
            }
        }
    }

    if(no) {
        printf("-1\n");
        return 0;
    }

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            Edge *e1 = new Edge(i*m+j, 1), *e2 = new Edge(i*m+j + 10000, 1);
            e1 -> dual = e2;	e2 -> dual = e1;
            adj[i*m + j].push_back(e2);		adj[i*m + j + 10000].push_back(e1);
            //좌상에서 우하로 훑고 내려오므로 중복되는 간선 세팅을 막기 위해 2방향으로만 간선을 세팅합니다.
            for(int k=0;k<2;k++) {
                int ny = i + dy[k], nx = j + dx[k];
                if(ok(ny,nx) && a[i][j] == '.' && a[ny][nx] == '.') {
                        //현재 점에서 2방향으로의 간선 세팅입니다.
	                	Edge *e5 = new Edge(i*m+j, 1), *e6 = new Edge(ny*m+nx+10000, 1);
	                	e5 -> dual = e6;	e6 -> dual = e5;
	                	adj[i*m + j].push_back(e6);		adj[ny*m + nx + 10000].push_back(e5);
                }
            }
        }
    }

    printf("%d\n",MaxFlow(kp,hp));
}

cokcjswo 7년 전 0

맞았습니다 !!

이것저것 구글링 하며 찾아보니

유향 간선으로 처리해야 하더군요 !! (왜인지는 잘 모르겠지만...)

정점을 컷하면 유향으로 처리해줘야하는건가? 라는 생각도 듭니다.

아니면 정점 컷 과 상관 없이 문제에서 유향간선을 요구하고 있는건가요?

하... 어렵네요...

cokcjswo 7년 전 0

아는 분께 물어서 해결했습니다 !!

무향간선을 어떻게 쪼갤지 얕게 알고만 있어서 문제가 생겼었네요 !!

도움주신

zlzmsrhak

님 감사합니다 !

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

삽질 좀 한 문제입니다.. 왜 틀렸을 까요 !!

cokcjswo 7년 전 0

zlzmsrhak 7년 전 1

cokcjswo 7년 전 0

cokcjswo 7년 전 0

cokcjswo 7년 전 0

zlzmsrhak

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말