hdu 1827 Summer Holiday 强连通分量缩点

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1827

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

思路：把关系抽象成图，人看作点，强连通分量分解。同一个强连通分量内的点，可以互相通知，那么处理出每个强连通分量内的最小花费。然后缩点，记录每个点的入度，对于入度不为0的点，可以由其他点通知，对于入度为0的点，必须由lcy去通知。于是，lcy需要通知的最小人数就是入度为0的点数，最小花费就是这些点代表的强连通分量内的最小花费。

总结：刚开始以为缩点后还要拓扑排序找出入度不为0的点，后来发现直接统计就好了，汗...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 1010;
struct edge
{
    int to, next;
} G[N*10];
int dfn[N], low[N], scc[N], st[N];
int head[N];
bool vis[N];
int index, cnt, num, top;
int scccost[N], indegree[N];
int n, m;

void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, -1, sizeof dfn);
    memset(vis, 0, sizeof vis);
    index = cnt = num = top = 0;
}
void add_edge(int v, int u)
{
    G[cnt].to = u;
    G[cnt].next = head[v];
    head[v] = cnt++;
}
void tarjan(int v)
{
    dfn[v] = low[v] = index++;
    st[top++] = v;
    vis[v] = true;
    int u;
    for(int i = head[v]; i != -1; i = G[i].next)
    {
        u = G[i].to;
        if(dfn[u] == -1)
        {
            tarjan(u);
            low[v] = min(low[v], low[u]);
        }
        else if(vis[u])
            low[v] = min(low[v], dfn[u]);
    }
    if(dfn[v] == low[v])
    {
        num++;
        do
        {
            u = st[--top];
            scc[u] = num;
            vis[u] = false;
        }
        while(u != v);
    }
}

void shrinkage_point() /*缩点，统计各点的入度*/
{
    memset(indegree, 0, sizeof indegree);
    for(int i = 1; i <= n; i++)
        for(int j = head[i]; j != -1; j = G[j].next)
            if(scc[i] != scc[G[j].to])
                indegree[scc[G[j].to]]++;

    int res = 0, a = 0;
    for(int i = 1; i <= num; i++)
        if(indegree[i] == 0)
            res += scccost[i], a++;
    printf("%d %d\n", a, res);
}

int main()
{
    int a, b;
    int cost[N];
    while(~ scanf("%d%d", &n, &m))
    {
        init();
        for(int i = 1; i <= n; i++)
            scanf("%d", cost + i);
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &a, &b);
            add_edge(a, b);
        }
        for(int i = 1; i <= n; i++)
            if(dfn[i] == -1)
                tarjan(i);

        memset(scccost, 0x3f, sizeof scccost);
        for(int i = 1; i <= n; i++) /*统计出每个强连通分量内的最小花费*/
            scccost[scc[i]] = min(scccost[scc[i]], cost[i]);
        shrinkage_point();
    }
    return 0;
}