글 읽기 - c++) 1420번 학교가지마! (네트워크 플로우)

ehddml3 6년 전 0

32퍼 정도에서 자꾸 틀리는데 뭐가 잘못된 걸까요ㅠㅠ

1. 학교 옆이면 -1 출력.

2. map으로 id 얻어서 변형 그래프의 정점 번호로 사용.

3. 정점에서는 flow를 못 흘리기 때문에 해당 정점을 두개로 분할함. ex) here->here2로 나눔.

4. here->here2, next2->here, here->next2 연결. (next는 현재 위치에서 오른쪽, 아래 부분)

5. 연결 끝나면 src2 부분부터 sink까지 ford-fulkerson 알고리즘으로 네트워크 플로우 계산

문제가 있다면 변형 그래프 만드는 부분에서 있을 것 같긴한데.. 아무리 봐도 잘 모르겠네요ㅠ

#include <cstdio>
#include <vector>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <cassert>

using namespace std;

vector<vector<char> > board;
map<pair<int,int>,int> mm;
vector<vector<int> > adj;
vector<vector<int> > flow,capacity;

int xshift[4]={0,1,0,-1};
int yshift[4]={1,0,-1,0};

void clear(queue<int> &q){
    queue<int> empty;
    swap(q,empty);
}

int main(){

    int n,m;
    scanf("%d %d",&n,&m);

    board = vector<vector<char> >(n+2,vector<char>(m+2,'#'));

    int id=1;
    char c;
    int Kx,Ky,Hx,Hy;
    int ccc=0;
    for(int i=1;i<=n;i++){
        getchar();
        for(int j=1;j<=m;j++){
            c = getchar();
            board[i][j]=c;
            if(c=='K'){ Kx=i; Ky=j; }
            if(c=='H'){ Hx=i; Hy=j; ccc++;}
            mm.insert(make_pair(make_pair(i,j),id++));
        }
    }
    assert(ccc==1);
    id++;   

    // 학교 옆에 있을 때.
    if(abs(Kx-Hx+Ky-Hy)==1){
        printf("-1\n");
        return 0;
    }

    adj = vector<vector<int> >(2*id+10);
    flow = capacity = vector<vector<int> >(2*id+10,vector<int>(2*id+10,0));

    // adj 생성.
    int src,sink;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(board[i][j]!='#'){
                int here = mm.find(make_pair(i,j))->second;
                int here2 = here+id+1;
                adj[here].push_back(here2);
                adj[here2].push_back(here);
                capacity[here][here2]=1;
                
                for(int k=0;k<2;k++){
                    int I = i+xshift[k];
                    int J = j+yshift[k];
                    if(board[I][J]!='#'){
                        int next = mm.find(make_pair(I,J))->second;
                        int next2 = next+id+1;
                        
                        adj[here2].push_back(next);
                        adj[next].push_back(here2);
                        capacity[here2][next]=1;

                        adj[next2].push_back(here);
                        adj[here].push_back(next2);
                        capacity[next2][here]=1;
                    }
                }
            }
            if(board[i][j]=='K') src = mm.find(make_pair(i,j))->second;
            else if(board[i][j]=='H') sink = mm.find(make_pair(i,j))->second;
        }
    }

    // ford-fulkerson.
    src += id+1;
    int result=0;
    while(1){

        vector<int> parent(2*id+10,-1);
        parent[src]=src;

        queue<int> q;
        q.push(src);

        while(!q.empty()&&parent[sink]==-1){

            int here = q.front(); q.pop();

            for(int i=0;i<adj[here].size();i++){
                int next = adj[here][i];
                if(parent[next]==-1&&capacity[here][next]-flow[here][next]>0){
                    q.push(next);
                    parent[next] = here;
                }
            }
        }

        if(parent[sink]==-1) break;

        int amount=1;
        // for(int p=sink;p!=parent[p];p=parent[p]){
        //     amount = min(amount,capacity[parent[p]][p]-flow[parent[p]][p]);
        // }
        result+=amount;
        for(int p=sink;p!=parent[p];p=parent[p]){
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }

        clear(q);
    }

    printf("%d\n", result);
    return 0;
}

ehddml3 6년 전 0

// 학교 옆에 있을 때.

if(abs(Kx-Hx+Ky-Hy)==1){
printf("-1\n");
return 0;
}

위 부분이 문제였습니다.ㅂㄷㅂㄷ..

https://www.acmicpc.net/board/... 에서 kks227님의 댓글 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

c++) 1420번 학교가지마! (네트워크 플로우)

ehddml3 6년 전 0

ehddml3 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말