Luogu-P3119

题面

很有意思的一道题

约翰有n块草场,编号1到n,这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家,她想到达尽可能多的草场>去品尝牧草。

贝西总是从1号草场出发,最后回到1号草场。她想经过尽可能多的草场,贝西在通一个草场只吃一次草,所以一个草场>可以经过多次。因为草场是单行道连接,这给贝西的品鉴工作带来了很大的不便,贝西想偷偷逆向行走一次,但最多只能有一次逆行。问,贝西最多能吃到多少个草场的牧草。

看到要尽量多的通过草场,且草场可以重复通过但不重复计数可以想到,在一个联通快内部的点都要走到(只有这样才能使得答案尽量的大)

那么我们找出所有的连通块然后缩点,问题就变成了在带点权DAG上找到一种路线使得在允许有一次走反向边且回到原点的最大路径(或者这么说,把任意一条边变成双向边使得包含点1的环尽可能的大)

对于缩点后的DAG

不妨这么考虑,把所有的点分为两类,一类是可以从点1直接到达的,还有一类是可以直接到达点1的
那么问题就变成了把两种不同的点间的某条边变成双向边使得环最大(仔细想想为什么)

那么这题就好写了, 只需要先跑联通分量缩点,然后对新图跑一遍spfa结果记录在dis1,然后对新图的反向图跑spfa结果记录在dis2(对反向图跑spfa计算从任意点到1的距离),然后答案就是max(dis1[u] + dis2[v] + 点1的连通块的点数)

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
#include <set>
5
#include <queue>
6
7
using namespace std;
8
9
const int maxn = 100005;
10
const int maxm  = maxn;
11
const int Inf = 0x3f3f3f3f;
12
13
vector<int> E[maxn];
14
vector<int> Eb[maxn];
15
bool vis[maxn];
16
vector<int> s;
17
set<int> En[maxn];
18
set<int> Enb[maxn];
19
int color[maxn];
20
int w[maxn];
21
int dis1[maxn];
22
int dis2[maxn];
23
24
auto spfa1(int n, int s, int e) -> void {
25
    std::fill(dis1, dis1 + 1 + maxn, -Inf);
26
    std::fill(vis, vis + 1 + maxn, false);
27
    queue<int> q;
28
    q.push(s);
29
    vis[s] = true;
30
    dis1[s] = 0;
31
    while(!q.empty()) {
32
        int now = q.front();
33
        q.pop();
34
        vis[now] = false;
35
        for (auto && v : En[now]) {
36
            //最长路改为 <
37
            if(dis1[v] < dis1[now] + w[v]) {
38
                dis1[v] = dis1[now] + w[v];
39
                if(vis[v]) continue;
40
                if(!vis[v]) {
41
                    vis[v] = true;
42
                    q.push(v);
43
                }
44
            }
45
        }
46
    }
47
}
48
49
auto spfa2(int n, int s, int e) -> void {
50
    std::fill(dis2, dis2 + 1 + maxn, -Inf);
51
    std::fill(vis, vis + 1 + maxn, false);
52
    queue<int> q;
53
    q.push(s);
54
    vis[s] = true;
55
    dis2[s] = 0;
56
    while(!q.empty()) {
57
        int now = q.front();
58
        q.pop();
59
        vis[now] = false;
60
        for (auto && v : Enb[now]) {
61
            if(dis2[v] < dis2[now] + w[v]) {
62
                dis2[v] = dis2[now] + w[v];
63
                if(vis[v]) continue;
64
                if(!vis[v]) {
65
                    vis[v] = true;
66
                    q.push(v);
67
                }
68
            }
69
        }
70
    }
71
}
72
73
74
auto dfs1(int u) -> void {
75
    vis[u] = true;
76
    for (auto &&p : E[u]) {
77
        if(!vis[p]) dfs1(p);
78
    }
79
    s.push_back(u);
80
}
81
82
auto dfs2(int u, int sccc) -> void {
83
    color[u] = sccc;
84
    ++w[sccc];
85
    for (auto && p : Eb[u]) {
86
        if(color[p] == 0) dfs2(p, sccc);
87
    }
88
}
89
90
auto kosaraju(int n) -> int {
91
    int sccc = 0;
92
    for (int i = 1; i <= n; ++i) {
93
        if(!vis[i]) dfs1(i);
94
    }
95
    for (int i = s.size() - 1; i >= 0; --i) {
96
        if(color[s[i]] == 0) {
97
            ++sccc;
98
            dfs2(s[i], sccc);
99
        }
100
    }
101
    return sccc;
102
}
103
104
int main() {
105
    ios::sync_with_stdio(false);
106
    cin.tie(nullptr);
107
    cout.tie(nullptr);
108
    int n, m;
109
    cin >> n >> m;
110
    for (int i = 1; i <= m; ++i) {
111
        int u, v;
112
        cin >> u >> v;
113
        if(u == v) continue;
114
        E[u].push_back(v);
115
        Eb[v].push_back(u);
116
    }
117
    int cn = kosaraju(n);
118
    for (int i = 1; i <= n; ++i) {
119
        for (auto &&p : E[i]) {
120
            if(color[i] == color[p]) continue;
121
            En[color[i]].insert(color[p]);
122
            Enb[color[p]].insert(color[i]);
123
        }
124
    }
125
    spfa1(cn, color[1], cn);
126
    spfa2(cn, color[1], cn);
127
    int ans = w[color[1]];
128
//    for (int i = 1; i <= n; ++i) {
129
//        cout << i << " " << color[i] << endl;
130
//    }
131
////    for_each(w + 1, w + 1 + cn, [](const int i) {
132
////        cout << i << " ";
133
////    });
134
//    cout << endl;
135
//    for (int i = 1; i <= cn; ++i) {
136
//        cout << i << ": ";
137
//        for_each(En[i].begin(), En[i].end(), [](const int & t) {
138
//            cout << t << " ";
139
//        });
140
//        cout << endl;
141
//    }
142
143
    for (int i = 1; i <= cn; ++i) {
144
//        cout << i << " " << dis1[i] << " " << dis2[i] << endl;
145
        for (auto &&p : Enb[i]) {
146
            if(dis1[i] != -Inf &&  dis2[p] != -Inf) ans = max(ans, dis1[i] + dis2[p] + w[color[1]]);
147
        }
148
    }
149
    cout << ans << endl;
150
    return 0;
151
}