水题笔记_ [ZJOI2007]最大半连通子图 [tarjan, dp, 翻车]

讲个鬼故事, 我bzoj刚过百

懵逼的 题目

qwq

扯淡的 题解

这题是补去年的tarjan坑…

我们冷静分析一波发现其实是找最长的路径, 和最长路径的条数

因为有环我们不能直接dp, 所以要tarjan缩一波点

f[i]为当前在第i个节点的, 最大的半联通子图的大小

f[i] = max{f[j]} + a[i], e[i][j] = true

c[i]为当前在第i个节点, 联通子图大小为f[i]的种类数

c[i] = \sum {c[j]}, e[i][j] = true && f[j] + a[i] == f[i]

然后就随便跑就好啦…

沙茶的 代码

  • 不知道为啥我又在缩点的时候写上并查集了…
  • 这个题在缩完点之后可能有重边…注意判重
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
118
119
120
121
122
123
124
/**************************************************************
Problem: 1093
User: Cansult
Language: C++
Result: Accepted
Time:2424 ms
Memory:48960 kb
****************************************************************/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#define MAXN (100000 + 5)
#define MAXM (1000000 + 5)
#define LL long long
using namespace std;
struct edg
{
int from, to, next;
}b[MAXM], bn[MAXM];
int g[MAXN], gn[MAXN], cntb, cntn, n, m, a[MAXN], Refun, dfn[MAXN], low[MAXN], belong[MAXN], cntdfn, f[MAXN], du[MAXN];
LL c[MAXN];
bool ins[MAXN];
stack<int> gary;
void tarjan(int dq)
{
low[dq] = dfn[dq] = ++cntdfn;
gary.push(dq);
ins[dq] = true;
for (int i = g[dq]; i; i = b[i].next)
if (!dfn[b[i].to])
{
tarjan(b[i].to);
low[dq] = min(low[dq], low[b[i].to]);
}
else if (ins[b[i].to])
low[dq] = min(low[dq], dfn[b[i].to]);
if (low[dq] == dfn[dq])
{
while (!gary.empty() && gary.top() != dq)
belong[gary.top()] = dq, ins[gary.top()] = false, gary.pop();
if (!gary.empty())
gary.pop();
belong[dq] = dq;
ins[dq] = false;
}
}
void adn(edg *bx, int& cntx, int *gx, int from, int to)
{
bx[++cntx].next = gx[from];
bx[cntx].from = from, bx[cntx].to = to;
gx[from] = cntx;
}
void init()
{
memset(ins, false, sizeof(ins));
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
set<int> hedg[MAXN];
for (int i = 1; i <= n; i++)
{
++a[belong[i]];
for (int j = g[i]; j; j = b[j].next)
if (belong[i] != belong[b[j].to] && hedg[belong[i]].find(belong[b[j].to]) == hedg[belong[i]].end())
++du[belong[b[j].to]], adn(bn, cntn, gn, belong[i], belong[b[j].to]), hedg[belong[i]].insert(belong[b[j].to]);
}
}

// c[i] = \sum {c[j]}, e[i][j] = true && f[j] == f[another j]
// f[i] = max{f[j]} + a[i], e[i][j] = true

int dfs(int dq)
{
if (f[dq])
return f[dq];
f[dq] = a[dq];
c[dq] = 1;
int qwq = 0;
LL qwqc = 0;
for (int i = gn[dq]; i; i = bn[i].next)
qwq = max(qwq, dfs(bn[i].to));
f[dq] += qwq;
for (int i = gn[dq]; i; i = bn[i].next)
if (dfs(bn[i].to) == qwq)
qwqc = (qwqc + c[bn[i].to]) % Refun;
if (qwqc)
c[dq] = qwqc;
return f[dq];
}
void solve()
{
vector<int> q;
bool vis[MAXN];
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++)
if (!du[belong[i]] && !vis[belong[i]])
q.push_back(belong[i]), vis[belong[i]] = true;
int ans = 0;
LL ansc = 0;
for (int i = 0; i < q.size(); i++)
ans = max(ans, dfs(q[i]));
for (int i = 0; i < q.size(); i++)
if (dfs(q[i]) == ans)
ansc = (ansc + c[q[i]]) % Refun;
printf("%d\n%lld", ans, ansc);
}
int main()
{
scanf("%d%d%d", &n, &m, &Refun);
for (int i = 1, srx, sry; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(b, cntb, g, srx, sry);
}
init();
solve();
return 0;
}

By 被吊打的 Cansult