轰炸

Posted on Edited on In

题目大意：n 个点，m 条边的有向图，每次选择若干点将其标记，不能存在两个不同的点 i,j 满足可以从 i 到达 j。问最少取几次可以使所有点都被标记过。

缩完点之后跑DAG的最长路

傻逼的错误示范：

1
2
3
4
5
6
7
8
9
10
11
12
inline void dfs(int x)
{
    val[x] = siz[x];
    for (int i = heads[x]; i; i = nexs[i])
    {
        int y = vers[i];
        if (val[y]) return;
        dfs(y);
        val[x] += val[y];
    }
    return;
}

归根结底还是思路没有捋清楚，或者说，经过将近一个半小时的思考，思路混乱了，在最接近正解的时候挂掉了

代码如下：

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
#define int long long
using namespace std;

const int N = 1e6 + 66;

int ver[N << 1], nex[N << 1], head[N], cnt;

inline void add_edge(int x, int y)
{
    ver[++ cnt] = y;
    nex[cnt] = head[x];
    return (void)(head[x] = cnt);
}

int n, m, res, ret;
int num, top, tot;
int dfn[N], low[N], in[N], sta[N], tar[N], siz[N];

inline void tarjan(int x)
{
    dfn[x] = low[x] = ++ tot; in[x] = 1, sta[++ top] = x;
    for (int i = head[x]; i; i = nex[i])
    {
        int y = ver[i];
        if (! dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (in[y]) low[x] = min(low[x], dfn[y]);
    }
    if (low[x] == dfn[x])
    {
        ++ num;
        int y;
        do
        {
            y = sta[top --]; in[y] = 0;
            tar[y] = num;
            ++ siz[num];
        }while (x != y);
    }
    return;
}

queue<int>q; int rd[N], cd[N];

int vers[N], nexs[N], heads[N], cnts;

inline void add(int x, int y)
{
    vers[++ cnts] = y;
    nexs[cnts] = heads[x];
    ++ rd[y], ++ cd[x];
    return (void)(heads[x] = cnts);
}

int val[N];

inline int dfs(int x)
{
    if (val[x]) return val[x];
    int now = siz[x];
    for (int i = heads[x]; i; i = nexs[i])
    {
        int y = vers[i];
        now = max(now, dfs(y) + siz[x]);
    }
    return val[x] = now;
}

signed main()
{
//	freopen("t2.in", "r", stdin), freopen("t2.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= m; ++ i)
    {
        int x = read(), y = read();
        add_edge(x, y);
    }

    for (int i = 1; i <= n; ++ i) if (! dfn[i]) tarjan(i);

    for (int x = 1; x <= n; ++ x)
    {
        for (int i = head[x]; i; i = nex[i])
        {
            int y = ver[i];
            if (tar[x] == tar[y]) continue;
//cout << "x->" << x << " y->" << y << '\n';
//cout << "tar[x]->" << tar[x] << " tar[y]->" << tar[y] << '\n';
            add(tar[x], tar[y]);
        }
    }
//cout << "num---->" << num << '\n';
    for (int i = 1; i <= num; ++ i) res = max(res, dfs(i));
    put(res);
    return 0;
}

总结：

真的好难受，本以为A掉的题结果挂了，就差那么一点啊，真的就一点啊

期望得分：100+100+30pts

实际得分：0+20+30pts

第一题纯属傻逼，看不出来是壮压

第二题真可惜

第三题，放弃了，打暴力就走了

虎瘦雄心在，人穷志不短，无论落魄到何种地步，都要坚守做人的底线，心怀勇气的走下去，只有这样才会慢慢好起来

我相信我自己没有问题，我一定会起来的！