글 읽기 - 열혈강호 문제 질문입니다.

moonsoo5522 7년 전 0

네트워크 플로우 공부를 어제 처음 시작하고 포드 풀커슨의 유량 알고리즘을 이 문제에 적용해 봤습니다.

dfs를 이용해 source노드부터 sink노드까지 탐색하고, 유량을 계산하는 방식으로 풀었을 땐 시간이 약 1초정도 나왔었는데요

bfs방법을 쓰니까 0%에서 바로 시간초과가 나오네요..

이 문제에서는 bfs가 느린게 맞는건지, 아니면 코드에 잘못된 부분이 있는건지 잘 모르겠습니다..

#include <stdio.h>
#include <queue>
#include <string.h>
 
using namespace std;
 
int N, M;
int v[2001][2001];
int sink;
int parent[2001];
int visited[2001];
int cnt;
 
int solve(int p)
{
    parent[sink] = 0;
     
    queue<int> q;
    q.push(p);
     
    while(!q.empty() && !parent[sink])
    {
        int node = q.front();
        q.pop();
         
        for(int i=1; i<=N+M+1; i++)
        {
            if(v[node][i] > 0)
            {
                q.push(i);
                parent[i] = node;
            }
        }
    }
     
    if(parent[sink]) return 1;
     
    return 0;
}
void update(int n)
{
    while(n > 0)
    {
        int par = parent[n];
        v[par][n]--;
        v[n][par]++;
         
        n = par;
    }
}
int main()
{
    scanf("%d %d", &N, &M);
    int t;
    int a;
    for(int i=1; i<=N; i++)
    {
        scanf("%d", &t);
        for(int j=0; j<t; j++)
        {
            scanf("%d", &a);
            v[i][N+a] = 1;
        }
    }
    for(int i=1; i<=N; i++)
        v[0][i] = 1;
     
    sink = N+M+1;
    for(int i=N+1; i<=N+M; i++)
        v[i][sink] = 1;
     
    while(solve(0))
    {
        cnt++;
        update(sink);
        memset(visited, 0, sizeof(visited));
    }
    printf("%d", cnt);
    return 0;
}

koosaga 7년 전 0

인접행렬 말고 리스트로 관리하시는 걸 추천드려요. 아마 그러면 나올거에요

koosaga 7년 전 1

.. 아 그것도 문제긴 한데 visited 배열이 없어서 무한루프가 돌거같네요

moonsoo5522 7년 전 0

으악 맞다 visited.... 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

열혈강호 문제 질문입니다.

moonsoo5522 7년 전 0

koosaga 7년 전 0

koosaga 7년 전 1

moonsoo5522 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말