[그래프] TIMETRIP 시간여행

1. 문제

 

이 문제는 

 

주어진 그래프에서

 

'사이클'을 찾는 문제이다.

 

특히 1번 정점을 지나는 '사이클' 만 찾으면된다는 것이다.

 

다른 곳에서 생기는 사이클은 전부 무시해도 된다는 것이다.

 

 

 

하지만 이 문제는 한번 꼬아서 최대와 최소 

 

즉 양의 무한대와 음의 무한대일 경우도 찾아야하는 것이다.

 

 

2. 벨만-포드 알고리즘

 

벨만-포드 알고리즘은 relax를 |V|번하게되면 그래프에 음수사이클의 여부를 알 수 있다.

 

이 알고리즘을 조금 변형하여

 

V번째 완화에서 만약 성공하면

 

시작점부터 완화가 발생한 지점까지 갈 수 있는지 확인하고

 

완화가 발생한 지점에서 목적지까지 갈 수 있는지 또 확인해야한다.

 

이는 0번에서 1번까지 도달하는것을 제외한 모든 사이클을 무시하게 해준다.

 

 

코드는 다음과 같다

 

이 코드는 최대 최소를 한번에 구한다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
 
using namespace std;
 
int G, W;
vector<vector<pair<pair<int, int> , int> > > adj;
 
 
bool findVertex(int here, int find, vector<bool>& visited)
{
      visited[here] = true;
    bool ret = false;
    if(visited[find]) 
    {
      visited = vector<bool>(G, false);
      return true;
    }
    for(int i = 0; i < adj[here].size(); i++)
    {
        if(visited[adj[here][i].second]) continue;
        ret = findVertex(adj[here][i].second, find, visited);
        if(ret) return ret;
    }
    return ret;
}
 
void bellman()
{
    vector<int> past = vector<int>(G, 2000*2000);
    vector<int> future = vector<int>(G, 2000*2000);
    past[0] = future[0] = 0;
    vector<bool> pvisited = vector<bool>(G, false);
    vector<bool> fvisited = vector<bool>(G, false);
 
    int pUpdated = false, fUpdated = false;;
    for(int i = 0; i < G; i++)
    {
        for(int here = 0; here < adj.size(); here++)
        {
            for(int k = 0; k < adj[here].size(); k++)
            {
                int max = adj[here][k].first.second;
                int min = adj[here][k].first.first;
                int there = adj[here][k].second;
 
                if(past[there] > past[here] + min)
                {
                    if(i == G-1 && !pUpdated && findVertex(here, 1, pvisited) && findVertex(0, here, pvisited))
                        pUpdated = true;
                    else
                        pvisited = vector<bool>(G, false);
                    
                    past[there] = past[here] + min;
                }
                if(future[there] > future[here] + max)
                {
                    if(i == G-1 && !fUpdated && findVertex(here, 1, fvisited) && findVertex(0,here,fvisited))
                        fUpdated = true;     
                    else
                        fvisited = vector<bool>(G, false);
                        
                    future[there] = future[here] + max;
                }
            }
        }
    }
 
    if(!findVertex(0,1, pvisited))
    {
        cout<<"UNREACHABLE\n";
        return;
    }
    if(pUpdated)
        cout<<"INFINITY";
    else
        cout<<past[1];
    cout<<" ";
    if(fUpdated)
        cout<<"INFINITY";
    else
        cout<<-future[1];
    cout<<"\n";
}
 
int main()
{
    int C;
    cin>>C;
    while(C--)
    {
        cin>>G;
        cin>>W;
        adj = vector<vector<pair<pair<int, int>, int> > >(G, vector<pair<pair<int, int> , int> >());
 
        for(int i = 0; i < W; i++)
        {
            int a, b, d;
            cin>>a>>b>>d;
            adj[a].push_back(make_pair(make_pair(d, -d), b));
        }
        bellman();
    }
}

• TIMETRIP