# 图论-教授Szu(BZOJ1512)

2018/06/18 15:42

 1 #include <stdio.h>
2 #include <algorithm>
3 #include <queue>
4 #include <stack>
5 #include <vector>
6
7 using namespace std;
8
9 const int _N = 110000;
10 const int P = 36500;
11
12 int N, M, TimeStamp, V_cnt, ans_mx, ans_cnt;
13 int low[_N], dfn[_N], Bel[_N], Ind[_N], f[_N];
14 bool mk[_N], flag[_N];
15 vector<int> G[_N], TG[_N];
16 queue<int> Q;
17 stack<int> S;
18
19 void Ins(int t1, int t2) { G[t1].push_back(t2); return; }
20
21 void Tarjan(int node)
22 {
23     low[node] = dfn[node] = ++TimeStamp;
24     S.push(node), mk[node] = true;
25     for (int i = G[node].size()-1; i >= 0; --i) {
26         int v = G[node][i];
27         if (!dfn[v]) {
28             Tarjan(v);
29             low[node] = min(low[node], low[v]);
30         } else if (mk[v]) {
31             low[node] = min(low[node], dfn[v]);
32         }
33     }
34     if (dfn[node] == low[node]) {
35         int tmp;
36         ++V_cnt;
37         do mk[tmp = S.top()] = false, Bel[tmp] = V_cnt, S.pop();
38         while (tmp != node);
39     }
40     return;
41 }
42
43 int main()
44 {
45     int i, j, t1, t2;
46     scanf("%d%d", &N, &M), ++N;
47     for (i = 1; i <= M; ++i)
48         scanf("%d%d", &t1, &t2), Ins(t2, t1);
49     for (i = 1; i <= N; ++i)
50         if (!dfn[i]) Tarjan(i);
51     for (i = 1; i <= N; ++i) {
52         for (j = G[i].size()-1; j >= 0; --j) {
53             int v = G[i][j];
54             if (Bel[v] == Bel[i]) flag[Bel[v]] = true;
55             else TG[Bel[i]].push_back(Bel[v]), ++Ind[Bel[v]];
56         }
57     }
58     f[Bel[N]] = flag[Bel[N]] ? P+1 : 1;
59     ans_mx = max(ans_mx, f[Bel[N]]);
60     for (i = 1; i <= V_cnt; ++i)
61         if (!Ind[i]) Q.push(i);
62     while (!Q.empty()) {
63         int p = Q.front(); Q.pop();
64         for (j = TG[p].size()-1; j >= 0; --j) {
65             int v = TG[p][j];
66             if (f[v] != P+1) {
67                 if (flag[v]) {
68                     if (f[p] > 0) f[v] = P+1;
69                 } else {
70                     if ((f[v] += f[p]) > P) f[v] = P+1;
71                 }
72             }
73             ans_mx = max(ans_mx, f[v]);
74             if (!--Ind[v]) Q.push(v);
75         }
76     }
77     if (ans_mx == P+1) printf("zawsze\n");
78     else printf("%d\n", ans_mx);
79     ans_cnt = 0;
80     for (i = 1; i < N; ++i)
81         if (f[Bel[i]] == ans_mx) ++ans_cnt;
82     printf("%d\n", ans_cnt);
83     for (i = 1; i < N; ++i)
84         if (f[Bel[i]] == ans_mx) printf("%d ", i);
85     return 0;
86 }
View Code

 时间限制 : - MS   空间限制 : - KB 评测说明 : 1s,128m
###### 问题描述

Byteotian 大学由一幢主建筑和n个小别墅组成. 它们之间许多单向的道路连接,任意两个建筑之间可能有多条单向路,也有可能一条路从自己出发并回到自己.任意两个建筑之间都是连通的(即要么可以从A走到B,要么可以从B走到A).

###### 输入格式

1：所有方案数超过36500的点都是等价的
2：本题可能有自环

3 5
1 2
1 3
2 3
3 4
3 4

4
1
1

4 7
1 2
2 2
3 2
2 3
3 4
4 5
3 4

zawsze
3
1 2 3

0
0 收藏

0 评论
0 收藏
0