글 읽기 - 벨만 포드만 이용시 음수 사이클 존재여부 질문 입니다.

jja08111 3년 전 0

밸만 포드만을 이용하여 해결했습니다. 그런데 궁금한 것이 있습니다.

아래에 주석으로 표시된 조건문을 보시면 here이 시작 지점과 끝 지점으로 가는 경로에 있어야 음수 사이클이 경로에 있다고 판단합니다.

그런데 there로 하면 틀렸습니다. 를 받습니다. 어짜피 here과 there은 음수 사이클로 연결되어 있는것 아닌가요?

웃긴것은 iter내부를 아래와 같이 작성하면 통과되는 것입니다. (주석에도 달아놓았습니다.)

```cpp

for(int iter=0;itercost+upper[here])
{
// 음수 사이클 존재 여부 판단
if(iter==V-1 && reachable[start][there] && reachable[there][target])
return -LONG_MAX;
upper[there]=cost+upper[here];
}
}

```

#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;

const int MAX_V=100;

int V;
vector<pair<int,int> > adj[MAX_V];
bool reachable[MAX_V][MAX_V];
int sales[MAX_V];

long long bellmanFord(const int start, const int target)
{
    vector<long long> upper(V,LONG_MAX);
    upper[start]=-sales[start];
    for(int iter=0;iter<V-1;++iter)
        for(int here=0;here<V;++here)
            if(upper[here]<LONG_MAX)
                for(int i=0;i<adj[here].size();++i)
                {
                    int there=adj[here][i].first;
                    int cost=adj[here][i].second-sales[there];
                    upper[there]=min(upper[there],cost+upper[here]);
                }
    // 음수 사이클 존재 여부 판단 
    for(int here=0;here<V;++here)
        for(int i=0;i<adj[here].size();++i)
        {
            int there=adj[here][i].first;
            int cost=adj[here][i].second-sales[there];
            if(upper[there]>cost+upper[here])
                // there로 경로에 있는 지 판단하면 틀립니다.
                //if(reachable[start][there] && reachable[there][target])
                if(reachable[start][here] && reachable[here][target])
                    return -LONG_MAX;
        }
    return upper[target];
}

/* 이것 또한 중간이 there인데 위에는 안되고 아래 처럼 작성하면 통과합니다.
long long bellmanFord(const int start, const int target)
{
    vector<long long> upper(V,LONG_MAX);
    // 시작 위치의 이득을 얻고 시작 
    upper[start]=-sales[start];
    // updated 없앰!!
    for(int iter=0;iter<V;++iter)
        for(int here=0;here<V;++here)
            if(upper[here]<LONG_MAX)
                for(int i=0;i<adj[here].size();++i)
                {
                    int there=adj[here][i].first;
                    int cost=adj[here][i].second-sales[there];
                    if(upper[there]>cost+upper[here])
                    {
                        // 음수 사이클 존재 여부 판단 
                        if(iter==V-1 && reachable[start][there] && reachable[there][target])
                            return -LONG_MAX;
                        upper[there]=cost+upper[here];
                    }
                }
    return upper[target];
}
*/

int main()
{
    int start, target, m;
    cin>>V>>start>>target>>m;
    
    memset(reachable,false,sizeof(reachable));
    for(int i=0;i<V;++i)
        reachable[i][i]=true;
    
    for(int i=0;i<m;++i)
    {
        int a,b,c;
        cin>>a>>b>>c;
        // 비용의 최소 값을 얻어야 하니 양수로 
        adj[a].push_back(make_pair(b,c));
        reachable[a][b]=true;
    }
    for(int i=0;i<V;++i)
        cin>>sales[i];
    
    for(int k=0;k<V;++k)
        for(int i=0;i<V;++i)
            for(int j=0;j<V;++j)
                reachable[i][j]|=reachable[i][k]&&reachable[k][j];
    
    long long ret=bellmanFord(start,target);
    if(ret==-LONG_MAX)
        cout<<"Gee"<<endl;
    else if(ret==LONG_MAX)
        cout<<"gg"<<endl;
    else
        cout<<(-ret)<<endl;
    
    return 0;
}

jja08111 3년 전 0

반례를 찾았습니다.

5 0 2 5

0 1 2

1 2 2

3 1 1

3 4 1

4 3 1

0 0 0 1 8

답: -4

출력: Gee

경로에 있지 않은데 경로에 있는것으로 판단하네요

그 이유는 20번째 줄에 있는 if(upper[here] < LONG_MAX) 이 없어서 였습니다.

그래서 값이 무한대인 정점을 완화하여 발생한 버그였습니다.

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

문제

문제

출처

ICPC

벨만 포드만 이용시 음수 사이클 존재여부 질문 입니다.

jja08111 3년 전 0

jja08111 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말