CF-567F(President and Roads)

題目鏈接

題意

$S?>E$的$DAG$中求:

$DAG$中必經(jīng)邊輸出"$YES$"

$DAG$中非必經(jīng)邊求這條邊最少降低多少可以使這條邊變成必經(jīng)邊

思路

判斷必經(jīng)邊可以用方案數(shù)判斷,對于一條邊$\{u,v\}$,如果$way[u]?rway[v]==way[E]$則該邊為必經(jīng)邊.

這題$mod$ = 1e9+7會被卡…

$mod$ = 258280327, 1610612741可以用,或者取兩次模

#include <bits/stdc++.h> const int maxn = 1e5 + 5; const long long inf = 1e18; const int mod = 258280327; using namespace std; struct ac{long long v, c, id;bool operator < (const ac &t) const{return t.c < c;} }; vector<ac> g[maxn], rg[maxn]; long long dis[maxn], rdis[maxn], vis[maxn], way[maxn], rway[maxn], ans[maxn]; void Dijkstra(int s, int e, long long* dis, long long* way, vector<ac> *edge) {fill(dis, dis+maxn, inf);fill(vis, vis+maxn, 0);dis[s] = 0;way[s] = 1;priority_queue<ac> que;que.push({s, 0});while (!que.empty()) {ac f = que.top();que.pop();int u = f.v;if (dis[u] < f.c || vis[u]) continue;vis[u] = 1;for (auto it : edge[u]) {int v = it.v;long long c = f.c + it.c;if (dis[v] > c) {dis[v] = c;way[v] = way[u];que.push({v, c});}else if (dis[v] == c) (way[v] += way[u]) %= mod;}} } int main() {int n, m, s, e;scanf("%d %d %d %d", &n, &m, &s, &e);for (int i = 0, u,v,c; i < m; ++i) {scanf("%d %d %d", &u, &v, &c);g[u].push_back({v, c, i});rg[v].push_back({u, c, i});}Dijkstra(s, e, dis, way, g);Dijkstra(e, s, rdis, rway, rg);for (int i = 1; i <= n; ++i) {for (auto it : g[i]) {int v = it.v;int c = it.c;long long tmp = c + dis[i] + rdis[v] - dis[e] + 1;if (dis[i] + c + rdis[v] == dis[e] && (way[i] * rway[v]) % mod == way[e]) ans[it.id] = -1;else if (tmp < c) ans[it.id] = tmp;else ans[it.id] = -2;}}for (int i = 0; i < m; ++i) {if (ans[i] == -1) puts("YES");else if (ans[i] == -2) puts("NO");else printf("CAN %lld\n", ans[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF-567F(President and Roads) DAG必经边的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。