0%

Codeforces 241E 解题报告

题意简述

给定一张\(n\)个点,\(m\)条带权边的有向无环图,边权值都是\(1\),你可以调整其中的一些边的边权为\(2\),来满足任意一条从点\(1\)到达点\(n\)的路径上的边权和相等。如果无解输出"No",否则输出"Yes",然后输出调整后所有边的边权。

时间限制:2s 空间限制:256MB

题目链接

Codeforces 241E

题解

对题目所要求的条件进行转化: 对于任意一条经过其可以从\(1\)到达\(n\)的边,设边为\((u,v)\),必须满足以下条件: \(2 \geq dis[v] - dis[u] \geq 1\)

转化为约束条件: \[dis[v] - dis[u] \geq 1 \Leftrightarrow dis[u] + 1 \leq dis[v]\] \[dis[v] - dis[u] \leq 2 \Leftrightarrow dis[v] + (-2) \leq dis[u]\] 建图方式为:从点\(u\)向点\(v\)连一条权值为\(1\)的边,再从点\(v\)向点\(u\)连一条权值为\(-2\)的边。

由于题目只是要求可行解,所以最短路算法和最长路算法都可以。但以上建图方式是最短路建图方式。使用最长路解决该问题需要将不等式转化为\(dis[u] + w(u,v) <= dis[v]\)的形式。

需要注意的是只有有效的边才能影响答案,所以先dfs一次来哪些点的距离值不会影响到答案,在最短路算法中不转移。同时还要注意判断负环。最后对于每条有效边\((u,v)\),输出\(dis[v] - dis[u]\)的值,无效边输出\(1\)\(2\)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>

using namespace std;

const int MAXM = 10010;
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

template<typename T>
T read() {
T result = 0;int f = 1;char c = getchar();
while(c > '9' || c < '0') {if(c == '-') f *= -1;c = getchar();}
while(c <= '9' && c >= '0') {result = result * 10 + c - '0';c = getchar();}
return result * f;
}

struct Graph {
struct Edge {
int next,to,weight;
};
Edge edges[MAXM];
int tot,heads[MAXN];

Graph() : tot(0) {
memset(heads,-1,sizeof(heads));
}

void addEdge(int u,int v,int w) {
edges[tot].next = heads[u];
edges[tot].to = v;
edges[tot].weight = w;
heads[u] = tot++;
}
} graph;

int n,m;

int dis[MAXN],cnt[MAXN];
bool visit[MAXN],canVisit[MAXN];

void dfs(int now) {
if(now == n) {
canVisit[now] = true;
return;
}
visit[now] = true;
for(int i = graph.heads[now];i != -1;i = graph.edges[i].next) {
Graph::Edge &tmpEdge = graph.edges[i];
if(tmpEdge.weight < 0) continue;
if(!visit[tmpEdge.to]) {
dfs(tmpEdge.to);
}
if(canVisit[tmpEdge.to]) {
canVisit[now] = true;
}
}
}

bool spfa(int start) {
queue<int> que;
for(int i = 1;i <= n;i++) dis[i] = -INF;
que.push(start);
dis[start] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
visit[now] = false;
for(int i = graph.heads[now];i != -1;i = graph.edges[i].next) {
Graph::Edge &tmpEdge = graph.edges[i];
if(!canVisit[tmpEdge.to]) continue;
if(dis[tmpEdge.to] >= dis[now] + tmpEdge.weight) continue;
dis[tmpEdge.to] = dis[now] + tmpEdge.weight;
if(!visit[tmpEdge.to]) {
visit[tmpEdge.to] = true;
que.push(tmpEdge.to);
cnt[tmpEdge.to]++;
if(cnt[tmpEdge.to] > n) {
return false;
}
}
}
}
return true;
}

pair<int,int> values[MAXM];

int main() {
n = read<int>(); m = read<int>();
for(int i = 0;i < m;i++) {
int u = read<int>(),v = read<int>();
graph.addEdge(u,v,1);
graph.addEdge(v,u,-2);
values[i] = make_pair(u,v);
}
dfs(1);
memset(visit,0,sizeof(visit));
bool result = spfa(1);
if(result) {
printf("Yes\n");
for(int i = 0;i < m;i++) {
pair<int,int> &tmpValue = values[i];
if(!canVisit[tmpValue.second] || !canVisit[tmpValue.first]) {
printf("%d\n",1);
}else {
printf("%d\n",dis[tmpValue.second] - dis[tmpValue.first]);
}
}
}else {
printf("No\n");
}
return 0;
}