Algoogle

Algorithm for Programming Contest

PKU 3169 Layout

Category: PKU Tag: bellman-ford

Layout

問題概要


仲の良い牛の組とよくない牛の組があり, 仲の良い牛とは一定以上(DL)離れたくないし, 嫌いな牛とは一定以上(DD)離れたい.
また, 牛は番号順に並んでいる.
そのとき1番の牛とN番の牛の距離の最大はいくらか.

解法


蟻本初級に載ってるけど絶対初級じゃないよなあ.

条件を式に直す.
牛iと牛j(i < j)が仲がいい時
dist[j] - dist[i] <= DL(i, j)
仲が悪い時
dist[j] - dist[i] >= DD(i, j)
また番号順に並んでいることより
dist[i] <= dist[i+1]

最短路問題において, 有向辺e(i, j)の長さl(i, j)のときその辺に依る距離の関係は
dist[i] + l(i, j) >= dist[j]

このことを利用すると上の条件を以下のように変形してグラフ上の最短路問題に帰着することができる.
仲がいい時: dist[i] + DL(i, j) >= dist[j]
仲が悪い時: dist[j] + (-DD(i, j)) >= dist[i]
番号順: dist[i+1] + 0 >= dist[i]

これにより, N番目の牛までの最短距離が求められる. またこれは配置可能な中でN番目までの距離の最大の値になる.
なぜならDLによってでしか各牛の距離は増加せず, DLは各関係の最大になっているから.
またそのことから, もしそのような辺によって値が更新されないとき, その牛と0番目の牛の距離は無限に大きくできることがわかる.

また負閉路が存在するとき, その閉路によって無限に値が小さくなり, それより前の牛の位置もどんどん小さくなるはず(番号順).
よって0番目の牛の位置が負のとき負閉路が存在する.
負閉路が存在するということは, 距離の関係に矛盾が生じている.
なぜならその区間の増やせる距離の大きさより大きく距離をとっていることになるからである.

コード


(3169.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <vector>
#include <map>

using namespace std;
typedef pair<int,int> pii;

const int inf = 1e9;
int N, ML, MD;
vector<pii> edge[1024];
int dist[1024]; // distance between 0 and i

int solve(){
    for(int cnt = 0; cnt < N; cnt++){
        for(int i = 0; i < N; i++)
            for(int j = 0; j < edge[i].size(); j++)
                if(dist[edge[i][j].first] > dist[i]+edge[i][j].second)
                    dist[edge[i][j].first] = dist[i] + edge[i][j].second;
        if(dist[0] < 0) return -1;
    }
    if(dist[N-1] == inf) return -2;
    return dist[N-1];
}

int main(){
    scanf("%d%d%d", &N, &ML, &MD);
    for(int i = N-1; i > 0; i--){
        edge[i].push_back(pii(i-1, 0));
        dist[i] = inf;
    }
    for(int i = 0; i < ML; i++){
        int a, b, d; scanf("%d%d%d", &a, &b, &d);
        a--; b--;
        edge[a].push_back(pii(b, d));
    }
    for(int i = 0; i < MD; i++){
        int a, b, d; scanf("%d%d%d", &a, &b, &d);
        a--; b--;
        edge[b].push_back(pii(a,-d));
    }
    printf("%d\n", solve());
    return 0;
}

Comments