HDU - 3072 Intelligence System

题意：

　　给出一个N个节点的有向图。图中任意两点进行通信的代价为路径上的边权和。如果两个点能互相到达那么代价为0。问从点0开始向其余所有点通信的最小代价和。保证能向所有点通信。

题解：

　　求出所有的强连通分量，然后进行缩点操作。最后贪心的找出每个点的最小代价，然后求和。

#include <iostream>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 5e4+;

const int inf = 0x3f3f3f3f;

int n, m;

struct node {

    int u, v, w;

}e[maxn<<];

vector<int> g[maxn];

vector<int> rg[maxn];

vector<int> vs;

bool vis[maxn];

int cmp[maxn], in[maxn];

ll ans;

void add_edge(int u, int v) {

    g[u].push_back(v);

    rg[v].push_back(u);

}

void dfs(int u) {

    vis[u] = true;

    int len = g[u].size();

    for(int i = ; i < len; i++) {

        int v = g[u][i];

        if(!vis[v]) dfs(v);

    }

    vs.push_back(u);

}

void rdfs(int u, int k) {

    vis[u] = true;

    cmp[u] = k;

    int len = rg[u].size();

    for(int i = ; i < len; i++) {

        int v = rg[u][i];

        if(!vis[v]) rdfs(v, k);

    }

}

int scc() {

    memset(vis, , sizeof(vis));

    vs.clear();

    for(int u = ; u < n; u++) {

        if(!vis[u]) dfs(u);

    }

    memset(vis, , sizeof(vis));

    int k = ;

    int len = vs.size();

    for(int i = len-; i >= ; i--) {

        int v = vs[i];

        if(!vis[v]) rdfs(v, k++);

    }

    return k;

}

int main() {

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

        ans = ;

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

            g[i].clear();

            rg[i].clear();

        }

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

            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

            add_edge(e[i].u, e[i].v);

        }

        n = scc();

        for(int i = ; i < n; i++) in[i] = maxn;

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

            int u = cmp[e[i].u];

            int v = cmp[e[i].v];

            if(u!=v) in[v] = min(in[v], e[i].w);

        }

        for(int i = ; i < n; i++) ans += in[i];

        printf("%lld\n", ans);

    }

}