【CF241E】Flights

题面

洛谷

题解

对于原来的图，如果一条边不出现在\(1\)到\(n\)的路径上面，直接\(ban\)掉即可。

那么考虑一条边\(u\rightarrow v\)，一定满足\(1\leq dis_v-dis_u\leq 2\)，其中\(dis_u,dis_v\)表示\(1\)到\(u,v\)的最短路。直接根据这个性质跑差分约束即可，一条边的答案即为\(dis_v-dis_u\)。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') w = -1, ch = getchar();
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
    return w * data;
}
const int INF = 1e9;
const int MAX_N = 1e3 + 5, MAX_M = 5e3 + 5;
struct Edge { int u, v; } a[MAX_M];
struct Graph { int to, cost; } ;
vector<Graph> G[MAX_N];
vector<int> E[MAX_N];
int N, M, vis[MAX_N];
void bfs(int s, int op) {
    queue<int> que;
    que.push(s), ++vis[s];
    while (!que.empty()) {
        int x = que.front(); que.pop();
        for (auto v : E[x])
            if (vis[v] == op) ++vis[v], que.push(v);
    }
}
int dis[MAX_N];
bool inq[MAX_N];
bool spfa() {
    static int cnt[MAX_N];
    queue<int> que; que.push(1), inq[1] = 1, ++cnt[1];
    for (int i = 2; i <= N; i++) dis[i] = INF;
    while (!que.empty()) {
        int x = que.front(); que.pop();
        for (auto e : G[x]) {
            int v = e.to, w = e.cost;
            if (dis[x] + w < dis[v]) {
                dis[v] = dis[x] + w;
                if (!inq[v]) ++cnt[v], inq[v] = 1, que.push(v);
                if (cnt[v] >= N) return 0;
            }
        }
        inq[x] = 0;
    }
    return 1;
}
int main () {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin);
#endif
    N = gi(), M = gi();
    for (int i = 1; i <= M; i++) {
        a[i].u = gi(), a[i].v = gi();
        E[a[i].u].push_back(a[i].v);
    }
    bfs(1, 0);
    for (int i = 1; i <= N; i++) E[i].clear();
    for (int i = 1; i <= M; i++) E[a[i].v].push_back(a[i].u);
    bfs(N, 1);
    for (int i = 1; i <= M; i++) {
        int u = a[i].u, v = a[i].v;
        if (vis[u] != 2 || vis[v] != 2) continue;
        G[u].push_back((Graph){v, 2});
        G[v].push_back((Graph){u, -1});
    }
    if (spfa()) puts("Yes");
    else return puts("No") & 0;
    for (int i = 1; i <= M; i++) {
        int u = a[i].u, v = a[i].v;
        if (vis[u] != 2 || vis[v] != 2) puts("1");
        else printf("%d\n", dis[v] - dis[u]);
    }
    return 0;
}