Codeforces241E Flights

差分约束

首先很显然对于任意在点 $1$ 到点 $n$ 路径上的点 $t$，所有从 $1$ 到 $t$ 的路径大小都是一样的。那么设 $dis(x)$ 表示这个唯一的路径大小，对于每条合法边（两个端点都在 $1$ 到 $n$ 的路径上）有不等式：$1\leq dis(v)-dis(u) \leq 2$。
看出来了吗？差分约束就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
const int MAXN = 1000;
const int MAXM = 5000;
int n, m, edge;
int U[MAXM | 1], V[MAXM | 1], fst[MAXN | 1], dist[MAXN | 1], cnt[MAXN | 1], flag[MAXN | 1];
bool vis[MAXN | 1];
struct Edge {
  int to, w, nxt;
  Edge() : to(0), w(0), nxt(0) {}
  Edge(int a, int b, int c) : to(b), w(c), nxt(fst[a]) {}
} e[MAXM << 1 | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void add_edge(int a, int b, int c) {
  e[++edge] = Edge(a, b, c);
  fst[a] = edge;
}
void dfs1(int x) {
  if (vis[x]) return;
  vis[x] = 1;
  flag[x] = 1;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (e[k].w == 1) continue;
    dfs1(to);
  }
}
void dfs2(int x) {
  if (vis[x]) return;
  ++flag[x];
  vis[x] = 1;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (e[k].w == 0) continue;
    dfs2(to);
  }
}
void SPFA() {
  std::queue < int > q;
  q.push(1);
  memset(dist, 0x3f, sizeof(dist));
  dist[1] = 0;
  do {
    int from = q.front();
    q.pop();
    vis[from] = 0;
    for (int k = fst[from]; k; k = e[k].nxt) {
      int to = e[k].to, w = e[k].w;
      if (dist[to] > dist[from] + w) {
        dist[to] = dist[from] + w;
        cnt[to] = cnt[from] + 1;
        if (cnt[to] > n) {
          puts("No");
          exit(0);
        }
        if (!vis[to]) {
          q.push(to);
          vis[to] = 1;
        }
      }
    }
  } while (!q.empty());
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    U[i] = read();
    V[i] = read();
    add_edge(V[i], U[i], 0);
    add_edge(U[i], V[i], 1);
  }
  dfs1(n);
  memset(vis, 0, sizeof(vis));
  dfs2(1);
  memset(vis, 0, sizeof(vis));
  edge = 0;
  memset(fst, 0, sizeof(fst));
  for (int i = 1; i <= m; ++i) {
    if (flag[U[i]] != 2 || flag[V[i]] != 2) continue;
    add_edge(U[i], V[i], 2);
    add_edge(V[i], U[i], -1);
  }
  SPFA();
  puts("Yes");
  for (int i = 1; i <= m; ++i) {
    if (flag[U[i]] != 2 || flag[V[i]] != 2) printf("1\n");
    else printf("%d\n", dist[V[i]] - dist[U[i]]);
  }
  return 0;
}