题目大意

　　给出一个有向图，问将图中的哪一个边翻转，会使节点1所在的强连通分量内的节点数最多。输出这个节点数。

题解

　　让我们看看暴力怎么做，即枚举每一条边，将其翻转，然后求节点1所在强连通分量节点数，然后取最大值。我们看到如果一条边连接的两个节点位于同一个强连通分量中，那么将这条边翻转只可能拆解已有的强连通分量，并使结果变差。因此，我们对强连通分量进行缩点（点权为强连通分量的节点个数）构成一个新图。

　　所以我们要在新图中暴力吗？不可以。怎样能达到“反向边只走一次”这个限制条件呢呢？分层图就能解决这个问题。原图复制一份得到上层图。把反向边起点连在原图上，终点连在上层图上，我们要求一个原图上的1节点走向上层图1节点的点权最长路径，它只会从原图走向上层图，不会从上层图走向下层图，这样就满足限制条件了。因为是点权，故我们拆点为边（以后简称“拆点边”）。

　　另外，这么做满足除了1节点外，在原图1节点到上层图1节点的路径上，不存在原图和上层图对应的拆点边计算两次的情况，因为如果计算了两次，那么在下层图上也会存在一条和整条路径在上层图上的部分相同的一条路径返回1节点，这样的路径构成了一个环，不满足强连通分量的定义。

　　另外注意，当有拆点、分层图时，开的空间要写到纸上。总共100000个点，分层图*2，拆点*2，故总共*4。原先我忘了拆点还要*2。。。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <stack>

#include <cassert>

using namespace std;

const int MAX_NODE = 100010, MAX_EDGE = 100010, MINF = 0xcfcfcfcf;

struct TarjanGraph

{

public:

    struct Block

    {

        int Size;

        vector<int> Next;

    }_blocks[MAX_NODE];

    int BlockCnt;

private:

    struct Node

    {

        vector<Node*> Next;

        int DfsN, Low, BlockIn;

        bool InStack;

    }_nodes[MAX_NODE];

    int DfsCnt, TotNode;

    stack<Node*> St;

    void Destack(Node *cur)

    {

        BlockCnt++;

        Node *temp;

        do {

            temp = St.top();

            St.pop();

            temp->BlockIn = BlockCnt;

            temp->InStack = false;

            _blocks[BlockCnt].Size++;

        } while (temp != cur);

    }

    void Dfs(Node *cur)

    {

        cur->Low = cur->DfsN = ++DfsCnt;

        cur->InStack = true;

        St.push(cur);

        for (unsigned int i = 0; i < cur->Next.size(); i++)

        {

            if (!cur->Next[i]->DfsN)

            {

                Dfs(cur->Next[i]);

                cur->Low = min(cur->Low, cur->Next[i]->Low);

            }

            else if (cur->Next[i]->InStack)

                cur->Low = min(cur->Low, cur->Next[i]->DfsN);

        }

        if (cur->Low == cur->DfsN)

            Destack(cur);

    }

public:

    void Init(int totNode)

    {

        TotNode = totNode;

    }

    void AddEdge(int u, int v)

    {

        _nodes[u].Next.push_back(_nodes + v);

    }

    void GetBlock()

    {

        for (int i = 1; i <= TotNode; i++)

            if (!_nodes[i].DfsN)

                Dfs(_nodes + i);

        for (int i = 1; i <= TotNode; i++)

            for (unsigned int j = 0; j < _nodes[i].Next.size(); j++)

                if (_nodes[i].BlockIn != _nodes[i].Next[j]->BlockIn)

                    _blocks[_nodes[i].BlockIn].Next.push_back(_nodes[i].Next[j]->BlockIn);

    }

    int GetBlockIn(int v)

    {

        return _nodes[v].BlockIn;

    }

}g;

struct TopGraph

{

private:

    struct Node;

    struct Edge;

    struct Node

    {

        Edge *Head;

        int Dist;

        int DfsN;//0:未访问 1：在系统栈内 2：处理完毕

    }_nodes[MAX_NODE * 4];

    int TotNode;

    stack<Node*> St;

    struct Edge

    {

        Node *To;

        Edge *Next;

        int Weight;

    }_edges[MAX_EDGE * 3 + MAX_NODE * 2];

    int _eCount;

    void Dfs(Node *cur)

    {

        assert(cur->DfsN != 1);

        if (cur->DfsN == 2)

            return;

        cur->DfsN = 1;

        for (Edge *e = cur->Head; e; e = e->Next)

            Dfs(e->To);

        cur->DfsN = 2;

        St.push(cur);

    }

public:

    void Init(int totNode)

    {

        TotNode = totNode;

    }

    void AddEdge(int u, int v, int w)

    {

        Node *from = _nodes + u, *to = _nodes + v;

        Edge *e = _edges + ++_eCount;

        e->To = to;

        e->Weight = w;

        e->Next = from->Head;

        from->Head = e;

    }

    int LongestPath(int s, int t)

    {

        Dfs(_nodes + s);

        for (int i = 1; i <= TotNode; i++)

            _nodes[i].Dist = MINF;

        _nodes[s].Dist = 0;

        while (!St.empty())

        {

            Node *cur = St.top();

            St.pop();

            for (Edge *e = cur->Head; e; e = e->Next)

                e->To->Dist = max(e->To->Dist, cur->Dist + e->Weight);

        }

        return _nodes[t].Dist;

    }

}t;

int main()

{

    int totNode, totEdge;

    scanf("%d%d", &totNode, &totEdge);

    g.Init(totNode);

    for (int i = 1; i <= totEdge; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        g.AddEdge(u, v);

    }

    g.GetBlock();

    t.Init(g.BlockCnt * 2);

    for (int i = 1; i <= g.BlockCnt; i++)

    {

        t.AddEdge(i * 2 - 1, i * 2, g._blocks[i].Size);

        t.AddEdge((i + totNode) * 2 - 1, (i + totNode) * 2, g._blocks[i].Size);

        for (unsigned int j = 0; j < g._blocks[i].Next.size(); j++)

        {

            int v = g._blocks[i].Next[j];

            t.AddEdge(i * 2, v * 2 - 1, 0);

            t.AddEdge((i + totNode) * 2, (v + totNode) * 2 - 1, 0);

            t.AddEdge(v * 2, (i + totNode) * 2 - 1, 0);

        }

    }

    printf("%d\n", t.LongestPath(g.GetBlockIn(1) * 2 - 1, (g.GetBlockIn(1) + totNode) * 2 - 1));

    return 0;

}

巴特西

luogu3119 草鉴定

题目大意

题解

最新文章

热门文章