글 읽기 - 시간초과

keh0711 7년 전 0

network flow로 짜는데 시간초과가 나네요. 어디를 개선해야 해결가능할까요??

#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
#include <memory.h>
using namespace std;

int c[301][301], f[301][301], N, M, S=0, T, totalFlow, parent[301];

int main(int argc, const char * argv[]) {
    //데이터받는 것은 생략함//
    while(true)
    {
        memset(parent, -1, sizeof(parent));
        queue<int> q;
        parent[S]=S; q.push(S);
        while(!q.empty() && parent[T]==-1)
        {
            int here=q.front(); q.pop();
            for(int there=1;there<=N+M+1;there++)
            {
                if(c[here][there]-f[here][there]>0 && parent[there]==-1)
                {
                    q.push(there);
                    parent[there]=here;
                }
            }
        }
        if(parent[T]==-1)
            break;
        for(int i=T;i!=S;i=parent[i])
        {
            f[parent[i]][i]+=1;
            f[i][parent[i]]-=1;
        }
        totalFlow+=1;
    }
    cout<<totalFlow<<endl;
    return 0;
}

yohan5050 7년 전 3

1<=N<=200, 1<=M<=200 이고 src, sink 를 포함하기 때문에 c, f 배열의 크기를 402*402로 해주셔야 합니다.
그리고 이 문제는 이분 매칭 문제이기도 해서 위의 최대유량을 구하는 알고리즘과 이분 매칭의 특성을 이용해 구현한 (종만북 1018페이지 참조)
좀 더 간단한 코드를 이용하는 게 편합니다.

keh0711 7년 전 1

감사합니다 배열의 크기를 작게 잡은 것이 원인이었습니다 덕분에 잘 해결할 수 있었습니다

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

문제

문제

출처

ICPC

시간초과

keh0711 7년 전 0

yohan5050 7년 전 3

keh0711 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말