HDU-1827-Summer Holiday（强连通分量，贪心）

雨点打透心脏的1/2处 2021-12-24 05:07 213阅读 0赞

### 链接：[https://vjudge.net/problem/HDU-1827][https_vjudge.net_problem_HDU-1827] ###

### 题意： ###

听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？

### 思路： ###

tarjan算法， 缩点。

先tarjan缩点，得到入度为0的强连通分量，再在每个入度为0的强连通分量中寻找一个消耗最小的人。

找最小的人可以在搜索的出栈的时候得到。

卡cin

### 代码： ###

#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 = 1e3+10;
    const int INF = 0x3f3f3f3f;
    
    vector<int> G[MAXN];
    stack<int> St;
    int Dfn[MAXN], Low[MAXN];
    int Vis[MAXN], Dis[MAXN];
    int Fa[MAXN], Cost[MAXN];
    int Val[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));
        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];
            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++;
            Val[cnt] = Cost[St.top()];
            while (St.top() != x)
            {
                Val[cnt] = min(Val[cnt], Cost[St.top()]);
                Fa[St.top()] = cnt;
                Vis[St.top()] = 0;
                St.pop();
            }
            Val[cnt] = min(Val[cnt], Cost[St.top()]);
            Fa[St.top()] = cnt;
            Vis[St.top()] = 0;
            St.pop();
        }
    }
    
    int main()
    {
        int t;
        while (~scanf("%d%d", &n, &m))
        {
    //        cin >> n >> m;
            Init();
            for (int i = 1;i <= n;i++)
                scanf("%d", &Cost[i]);
    //            cin >> Cost[i];
            int l, r;
            for (int i = 1;i <= m;i++)
            {
                scanf("%d%d", &l, &r);
    //            cin >> l >> r;
                G[l].push_back(r);
            }
            for (int i = 1;i <= n;++i)
                if (!Dfn[i])
                    Tarjan(i);
            for (int i = 1;i <= n;++i)
            {
                for (int j = 0;j < G[i].size();j++)
                {
                    int node = G[i][j];
                    if (Fa[i] != Fa[node])
                        ++Dis[Fa[node]];
                }
            }
            int res_num = 0, res_val = 0;
            for (int i = 1;i <= cnt;i++)
                if (!Dis[i])
                    res_num++, res_val += Val[i];
            cout << res_num << ' ' << res_val << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10821724.html

[https_vjudge.net_problem_HDU-1827]: https://vjudge.net/problem/HDU-1827