【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;

}

巴特西

【CF241E】Flights

【CF241E】Flights

题面

题解

代码

最新文章

热门文章