题目大意：有一个人想要将消息告诉给所有人（在同一个强连通分量里面的人可以相互转告，费用为0），问所有人都知道消息的最小花费是多少
解题思路：求出所有的强连通分量，然后将其缩点，桥就是连接其中的边 因为是张连通图，所以只要求出每个强连通分量被通知的最小价值，，然后累加即可 刚开始以为可以用最小生成树，但发现错了，假设求出了三个强连通分量了，分别标号为1，2，3 再给出桥 1-2，权值1，1-3权值5，3-2权值4 按最小生成树的话，得到的结果是5，然而并不是这样的，因为是有向边，所以3这个点是不会被通知到的。
;Edge{int to, from, next, val;}E[M];int head[N], pre[N], lowlink[N], sccno[N], stack[N], d[N];int n, m, tot, scc_cnt, top, dfs_clock;void AddEdge(int from, int to, int val) {E[tot].from = from;E[tot].to = to;E[tot].next = head[from];E[tot].val = val;head[from] = tot++; }void init() {memset(head, -1, sizeof(head));tot = 0;int u, v, val;for (int i = 0; i < m; i++) {scanf(“%d%d%d”, &u, &v, &val);AddEdge(u, v, val);}}void dfs(int u) {pre[u] = lowlink[u] = ++dfs_clock;stack[++top] = u;for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (!pre[v]) {dfs(v);lowlink[u] = min(lowlink[u], lowlink[v]);}else if (!sccno[v]) {lowlink[u] = min(lowlink[u], pre[v]);}}int x;if (pre[u] == lowlink[u]) {scc_cnt++;while (1) {x = stack[top–];sccno[x] = scc_cnt;if (x == u)break;}}}void solve() {memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));dfs_clock = top = scc_cnt = 0;for (int i = 0; i < n; i++)if (!pre[i])dfs(i);int u, v;memset(d, 0x3f, sizeof(d));for (int i = 0; i < tot; i++) {u = sccno[E[i].from], v = sccno[E[i].to];if (u != v) {d[v] = min(d[v], E[i].val);}}int ans = 0;for (int i = 1; i <= scc_cnt; i++)if (d[i] != INF)ans += d[i];printf(“%d\n”, ans);}int main() {while (scanf(“%d%d”, &n, &m) != EOF) {init();solve();}return 0;}
奢侈地享受旅不问人，行随己意的潇洒。
