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