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

佚名 7年前 (2019-05-06) 随笔 603人围观抢沙发百度已收录

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

题意：

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

思路：

tarjan算法，缩点。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

先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;
}