讲个鬼故事, 我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]

然后就随便跑就好啦…

沙茶的 代码

  • 不知道为啥我又在缩点的时候写上并查集了…
  • 这个题在缩完点之后可能有重边…注意判重
/**************************************************************
    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