【tarjan缩点+分层图】草鉴定Grass Cownoisseur

P3119 [USACO15JAN] 草鉴定Grass Cownoisseur

tarjan缩点+建分层图

缩点：单向边+可重复走一个牧场

缩完点后，对于不在原图中的一条边(u, v), if(sd[u] != sd[v]) 连边，建立新图编号为1~tot//sd[] 该点属于哪个强连通分量， tot是强连通的数量

分层图：可逆向走一次，分层图顶点编号为 tot+1 ~ 2 * n；对于缩点后新图中的一条边(u, v), 将该边终点与分层图的起点连边，达到逆向走一次的目的add(v, u+tot)

分层图自身也要连边，对于缩点后的新图(u, v) ，分层图连相应的边add(u+tot, v+tot)

记得分层图上的点权值与缩点后新图权值相同！！

因为最后会走回1号点，会加上1号点所在强连通的权值，所以开始初始dis只可以为0

自信代码姹紫嫣红竟因忘删注释？！数组开的正好re两个点，开大十倍就好了QAQ

 1 #include<queue>
 2 #include<cstdio>
 3 #include<iostream>
 4 using namespace std;
 5 const int sz = 1000010;
 6 int n, m, tim = 0, top = 0, num = 0, num2 = 0, tot = 0;
 7 int h[sz], dfn[sz], low[sz], sta[sz], x[sz], y[sz], sd[sz];
 8 int h2[sz], dis[sz ], node[sz];
 9 bool vis[sz], book[sz ];
10 struct Egde {
11     int nxt, to, dis;
12 }e[sz], e2[sz << 1];
13 int read() {
14     char ch = getchar(); int x = 0, f = 1;
15     while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
16     while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
17     return x * f;
18 }
19 void add(int from, int to) {
20     e[++num].nxt = h[from];
21     e[num].to = to;
22     h[from] = num;
23 }
24 void add2(int from, int to) {
25     e2[++num2].nxt = h2[from];
26     e2[num2].to = to;
27      h2[from] = num2;
28 }
29 void tarjan(int u) {
30     low[u] = dfn[u] = ++tim;
31     sta[++top] = u;
32     vis[u] = 1;
33     for(int i = h[u]; i; i = e[i].nxt) {
34         int v = e[i].to;
35         if(!dfn[v]) {
36             tarjan(v);
37             low[u] = min(low[v], low[u]);
38         }
39         else if(vis[v]) low[u] = min(low[u], dfn[v]);
40     }
41     if(dfn[u] == low[u]) {
42             tot++;
43         while(u != sta[top+1]) {
44             sd[sta[top]] = tot;
45             node[tot]++;
46             vis[sta[top]] = 0;
47             top--;
48         }
49     }
50 }
51 void spfa(int s) {
52     queue<int>q;
53     for(int i = 1; i <= (n<<1); i++) {
54         dis[i] = 0;
55         book[i] = 0;
56     }
57     book[s] = 1;
58     q.push(s);
59     while(!q.empty()) {
60         int u = q.front();
61         q.pop();
62         book[u] = 0;
63         for(int i = h2[u]; i; i = e2[i].nxt) {
64             int v = e2[i].to;
65             if(dis[v] < dis[u] + node[v]) {
66                 dis[v] = dis[u] + node[v];
67                 if(!book[v]) {
68                     book[v] = 1;
69                     q.push(v);
70                 }
71             }
72         }
73     }
74 }
75 int main() {
76     scanf("%d%d", &n, &m);
77     for(int i = 1; i <= m; i++) {
78         x[i] = read(), y[i] = read();
79         add(x[i], y[i]);
80     }    
81     for(int i = 1; i <= n; i++)
82         if(!dfn[i]) tarjan(i);
83     for(int i = 1; i <= m; i++) {
84         int u = sd[x[i]], v = sd[y[i]];
85         if(u != v) {
86             add2(u, v);
87             add2(v, u+tot);
88             add2(u+tot, v+tot);
89         }    
90     }
91     for(int i=1;i<=tot;i++) node[i+tot]=node[i];
92     spfa(sd[1]);
93     printf("%d", dis[sd[1]+tot]);
94     return 0;
95 }

和aq重学了个缩点QAQ