HDU-3072-IntelligenceSystem（tarjan，贪心）

链接：https://vjudge.net/problem/HDU-3072

题意：

给你n个点，1个点到另一个点连接花费c，但是如果几个点可以相互可达，则这几个点连通花费为0.

求将整个图连通的最小花费。

思路：

tarjan，求出强连通子图。

对每个子图的进点的最小值更新，再累加即可，（不过不知道为什么）

代码：

#include <iostream>

#include <memory.h>

#include <string>

#include <istream>

#include <sstream>

#include <vector>

#include <stack>

#include <algorithm>

#include <map>

#include <queue>

#include <math.h>

#include <cstdio>

#include <set>

#include <iterator>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 5e4+10;

const int INF = 0x3f3f3f3f;

struct Node

{

    int from_, to_, value_;

    Node(int from, int to, int value):from_(from), to_(to), value_(value){}

    bool operator < (const Node &that) const

    {

        return this->value_ > that.value_;

    }

};

vector<Node> G[MAXN];

stack<int> St;

int Dfn[MAXN], Low[MAXN];

int Vis[MAXN], Dis[MAXN];

int Fa[MAXN], Val[MAXN];

int Num[MAXN];

int n, m;

int times, cnt;

void Init()

{

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

        G[i].clear(), Fa[i] = i;

    memset(Dfn, 0, sizeof(Dfn));

    memset(Low, 0, sizeof(Low));

    memset(Vis, 0, sizeof(Vis));

    memset(Dis, 0, sizeof(Dis));

    memset(Num, 0, sizeof(Num));

    memset(Val, 0, sizeof(Val));

    times = cnt = 0;

}

void Tarjan(int x)

{

    Dfn[x] = Low[x] = ++times;

    Vis[x] = 1;

    St.push(x);

    for (int i = 0;i < G[x].size();i++)

    {

        int node = G[x][i].to_;

        if (Dfn[node] == 0)

        {

            Tarjan(node);

            Low[x] = min(Low[x], Low[node]);

        }

        else if (Vis[node] == 1)

            Low[x] = min(Low[x], Dfn[node]);

    }

    if (Low[x] == Dfn[x])

    {

        cnt++;

        Num[cnt] = 0;

        while (St.top() != x)

        {

            Num[cnt]++;

            Fa[St.top()] = cnt;

            Vis[St.top()] = 0;

            St.pop();

        }

        Num[cnt]++;

        Fa[St.top()] = cnt;

        Vis[St.top()] = 0;

        St.pop();

    }

}

int main()

{

    int t, cn = 0;

    while (~scanf("%d%d", &n, &m))

    {

        Init();

        int l, r, v;

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

        {

            scanf("%d%d%d", &l, &r, &v);

            l++, r++;

            G[l].emplace_back(l, r, v);

        }

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

            if (!Dfn[i])

                Tarjan(i);

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

            Val[i] = INF;

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

        {

            for (int j = 0;j < G[i].size();j++)

            {

                int node = G[i][j].to_;

                if (Fa[i] != Fa[node])

                    Val[Fa[node]] = min(Val[Fa[node]], G[i][j].value_);

            }

        }

        int res = 0;

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

            if (Val[i] != INF)

                res += Val[i];

        cout << res << endl;

    }

    return 0;

}