CF360E Levko and Game

05 October 2019 | duanyll | Tags: OI 题解 贪心

题意

$n$个点, $m+k$条边的有向图, 其中给定$k$条边可以在给定$[l_i, r_i]$范围内任意修改边权, 判断并输出是否存在一种方案使$s_1\rightarrow f$的最短路比$s_2\rightarrow f$短.

分析

先令所有的边权都取到$r_i$, 然后从$s_1,s_2$开始单源最短路. 然后每次考虑一条边$(u,v)$满足$dis_1[u] < dis_2[u]$, 将他的边权设为$l_i$后再跑最短路, 直到不存在这样的边, 然后判断结果并输出.

因为对于$dis_1[u] < dis_2[u]$的情况, 假如$(u, v)$在最短路上, 一定有$dis_1[v] < dis_2[v]$, 所以现在修改了边权, 一定会使后面的$dis_1[u]$更小, 即答案更优.

允许平局的情况, 改为$dis_1[u] \leq dis_2[u]$即可.

代码

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e4 + 110;

class lfs {
   public:
    lfs(int N) {
        memset(head, -1, sizeof head);
        memset(l, 0, sizeof l);
        memset(r, 0, sizeof r);
        ecnt = 0;
        n = N;
    }
    void adde(int from, int to, int L, int R) {
        u[ecnt] = from;
        l[ecnt] = L;
        r[ecnt] = R;
        e[ecnt].to = to;
        e[ecnt].w = R;
        e[ecnt].next = head[from];
        head[from] = ecnt++;
    }

    struct Edge {
        int to, next, w;
    } e[MAXN * 2];
    int head[MAXN];
    int ecnt;
    int n;

    int u[MAXN], l[MAXN], r[MAXN];
};

class dijkstra : public lfs {
   public:
    dijkstra(int n) : lfs(n) {}
    int64 dis1[MAXN], dis2[MAXN];
    void solve(int s, int64* dis) {
        priority_queue<pair<int64, int>, vector<pair<int64, int>>,
                       greater<pair<int64, int>>>
            que;
        dis[s] = 0;
        que.push(pair<int64, int>(0, s));
        while (!que.empty()) {
            pair<int64, int> p = que.top();
            que.pop();
            int v = p.second;
            if (dis[v] < p.first) continue;
            for (int i = head[v]; ~i; i = e[i].next) {
                Edge now = e[i];
                if (now.w + dis[v] < dis[now.to]) {
                    dis[now.to] = now.w + dis[v];
                    que.push(pair<int64, int>(dis[now.to], now.to));
                }
            }
        }
    }

    bool check(int s1, int s2, int f, bool can_draw, int m, int k) {
        bool updated;
        do {
            updated = false;
            memset(dis1, INF, sizeof dis1);
            memset(dis2, INF, sizeof dis2);
            solve(s1, dis1);
            solve(s2, dis2);
            if (dis1[f] < dis2[f] + can_draw) {
                cout << (can_draw ? "DRAW" : "WIN") << endl;
                for (int i = m; i < m + k; i++) {
                    cout << e[i].w << ' ';
                }
                cout << endl;
                return true;
            }
            for (int i = m; i < m + k; i++) {
                if (dis1[u[i]] < dis2[u[i]] + can_draw) {
                    if (e[i].w > l[i]) {
                        e[i].w = l[i];
                        updated = true;
                        break;
                    }
                }
            }
        } while (updated);
        return false;
    }
};

#include <cctype>
#include <cstdio>

template <typename T = int>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    int s1, s2, f;
    cin >> s1 >> s2 >> f;
    dijkstra* graph = new dijkstra(n);
    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        int w = read();
        graph->adde(u, v, w, w);
    }
    for (int i = 1; i <= k; i++) {
        int u = read();
        int v = read();
        graph->l[i] = read();
        graph->r[i] = read();
        graph->adde(u, v, graph->l[i], graph->r[i]);
    }
    if (!graph->check(s1, s2, f, false, m, k)) {
        if (!graph->check(s1, s2, f, true, m, k)) {
            cout << "LOSE" << endl;
        }
    }
}