TIOJ 2253：C. 街頭藝人

TIOJ 2253：C. 街頭藝人

題目大意：給你一個 $n$ 城市 $m$ 邊 $k\times m$ 村莊的有向圖，城市編號 $1\sim n$，村莊編號 $n + 1\sim n + k\times m$，且第 $i$ 條邊中間的村莊為 $n + k\times(i - 1) + 1\sim n + k\times i$，城市和村莊都有一個值 $c_i$，要找到一個回路 $v_1\sim v_t, v_1 = v_t$，使得 $s_i = \sum\limits_{j = 1}^i c_{v_j}\geq 0$，並輸出此回路有多少城市和村莊可以當作出發的起點。

解法：首先找得到合法的出發點若且為若有非負環：假設有合法的出發點，那一定就是非負環，假設是非負環，我們先以隨便的出發點找出 $s_0 \sim s_t$，找到最小的 $s_{i - 1}$，那 $i$ 就可以當出發點，因為當 $j\geq i$，$s_j - s_{i - 1}\geq 0$，當 $j<i$，$s_t - s_{i - 1} + s_j\geq 0$。那如果要判斷環上的點是否能當起點，可以找到前綴和前綴最小值 $pm_i = \min(s_0\sim s_i)$、前綴和後綴最小值 $sm_i = \min(s_i\sim s_t)$，然後只要 $sm_i - s_{i - 1}\geq 0, s_t - s_{i - 1} + pm_i\geq 0$ 就可以了。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2005;
const int MSIZ = 8005;

int n, m, k;
ll w[MSIZ], dis[SIZE];
vector<int> adj[SIZE];
pair<int, int> e[MSIZ];
int a[SIZE], c[MSIZ][SIZE];

queue<int> q;
bool inq[SIZE];
int pre[SIZE], cnt[SIZE];

vector<int> st, cycle, node;
vector<ll> sum, pm, sm;

void cal (int pos) {
    fill (inq, inq + n + 1, 0);
    while (inq[pos] == 0) {
        st.pb (pre[pos]);
        inq[pos] = 1;
        pos = e[pre[pos]].F;
    }
    while (1) {
        auto [x, y] = e[st.back()];
        cycle.pb (st.back());
        st.pop_back();
        if (y == pos) break;
    }
}

void solve() {
    cin >> n >> m >> k;
    FOR (i, 1, n) cin >> a[i];
    FOR (i, 1, m) {
        auto &[x, y] = e[i];
        cin >> x >> y;
        w[i] = a[y];
        adj[x].pb (i);
        FOR (j, 1, k) {
            cin >> c[i][j];
            w[i] += c[i][j];
        }
    }
    FOR (i, 1, n) q.push (i), inq[i] = 1;
    bool f = 0;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        inq[pos] = 0;
        for (int id : adj[pos]) {
            int np = e[id].S;
            if (dis[pos] + w[id] >= dis[np]) {
                dis[np] = dis[pos] + w[id];
                pre[np] = id;
                cnt[np] = cnt[pos] + 1;
                if (inq[np] == 0) {
                    inq[np] = 1;
                    q.push (np);
                }
                if (cnt[np] >= n) {
                    f = 1;
                    cal (np);
                    break;
                }
            }
        }
        if (f) break;
    }
    if (f == 0) {cout << "0\n"; return;}
    node.pb (0), sum.pb (0);
    for (int id : cycle) {
        node.pb (e[id].F);
        sum.pb (sum.back() + a[e[id].F]);
        FOR (i, 1, k) {
            node.pb (n + (id - 1) * k + i);
            sum.pb (sum.back() + c[id][i]);
        }
    }
    pm = sm = vector<ll> (sum.size());
    for (int i = 1; i < pm.size(); i++) pm[i] = min (pm[i - 1], sum[i]);
    sm.end()[-1] = sum.back();
    for (int i = sm.size() - 2; i >= 0; i--) sm[i] = min (sm[i + 1], sum[i]);
    f = 0;
    int city = 0, village = 0;
    for (int i = 1; i < sum.size(); i++) {
        if (sm[i] >= sum[i - 1] && sum.back() - sum[i - 1] + pm[i] >= 0) {
            (i % (k + 1) == 1 ? city : village)++;
            if (f == 0) {
                f = 1;
                cout << sum.size() << '\n';
                for (int j = i; j < sum.size(); j++) cout << node[j] << ' ';
                for (int j = 1; j < i; j++) cout << node[j] << ' ';
                cout << node[i] << '\n';
            }
        }
    }
    cout << city << ' ' << village << '\n';
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！