UVa

UVa11478 Halum (差分約束)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=550&problem=2473&mosmsg=Submission+received+with+ID+14137690
題意：給一張圖，邊有權重，有個操作X(s,v)，點s為起點的邊+v，點s為終點的邊-v，可以有無限次操作，在最後所有邊權重大於0的情況，最小的權重最大可以為多少。

解答：對於一條s到t的邊，他的權重增加Xsum(s)，減少了Xsum(t)(Xsum(s)為s操作的總值)，那麼我們可以二分搜答案x，Xsum(s)-Xsum(t)+w(s,t)>=x，Xsum(s)-Xsum(t)<=w(s,t)-x，這樣就可以轉化為差分約束了。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
struct Edge{
    int t, w;
};
int v, e;
int d[N], cnt[N];
bitset<N> inq;
queue<int>Q;
vector<Edge>G[N];

void addEdge(int from, int to, int w){
    G[from].push_back({to,w});
}

bool hasnegativeCycle(int x){
    while(!Q.empty())Q.pop();
    for(int i = 1; i <= v;i++){
        inq[i] = true;
        cnt[i] = d[i] = 0;
        Q.push(i);
    }
    while(!Q.empty()){
        int s = Q.front(); Q.pop();
        inq[s] = false;
        for(Edge it: G[s]){
            if(d[it.t] > d[s] + it.w - x){
                d[it.t] = d[s] + it.w - x;
                if(inq[it.t])continue;
                Q.push(it.t);
                inq[it.t] = true;
                if(++cnt[it.t] > v)return true;
            }
        }
    }
    return false;
}

void sol(int L, int R){
    if(hasnegativeCycle(1)){
        cout << "No Solution\n";
    }else if(!hasnegativeCycle(R + 1)){
        cout << "Infinite\n";
    }else {
        while(L != R){
            int M= (L + R + 1) >> 1;
            if(hasnegativeCycle(M))R = M - 1;
            else L = M;
        }
        cout << L << '\n';
    }
}

int main(){
    int mxw;
    while(cin >> v >> e){
        for(int i = 0; i <= v; i++)G[i].clear();
        mxw = 0;
        for(int i = 0, f, t, w; i < e; i++){
            cin >> f >> t >> w;
            addEdge(f, t, w);
            mxw = max(mxw, w);
        }
        sol(1, mxw);
    }
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts