学习了最小树形图 题解：http://www.cnblogs.com/wust-ouyangli/p/5722496.html
努力理解了最小树形图的原理 对于这道题 我个人感觉是类似于dijkstra 因为首先这个是一定能找到通路的，既然这样就不断更新(不管从哪里)到这个点的最小花费
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
const int maxn=
50010;
const int vm=
100010;
const int INF=
0x3f3f3f3f;
struct points
{
int v,c;
};
vector<int> G[vm];
int n;
int dis[maxn],vis[maxn],inq[maxn];
int uu[vm],vv[vm],ww[vm];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
void dfs(
int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for (
int i=
0;i<G[u].size();i++)
{
int v=G[u][i];
if (!pre[v])
{
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if (!sccno[v]) lowlink[u]=min(lowlink[u],pre[v]);
}
if (lowlink[u]==pre[u])
{
scc_cnt++;
for (;;)
{
int x=S.top(); S.pop();
sccno[x]=scc_cnt;
if (x==u)
break;
}
}
}
void find_scc(
int n)
{
dfs_clock=scc_cnt=
0;
memset(sccno,
0,
sizeof(sccno));
memset(pre,
0,
sizeof(pre));
for (
int i=
0;i<n;i++)
if (!pre[i]) dfs(i);
}
int main()
{
int m,ans;
while (~
scanf(
"%d%d",&n,&m))
{
for (
int i=
0;i<=n;i++) G[i].clear();
for (
int i=
1;i<=m;i++)
{
scanf(
"%d%d%d",&uu[i],&vv[i],&ww[i]);
G[uu[i]].push_back(vv[i]);
}
find_scc(n);
for (
int i=
1;i<=scc_cnt;i++) dis[i]=INF;
for (
int i=
1;i<=m;i++)
{
int u=sccno[uu[i]],v=sccno[vv[i]];
if (v!=u) dis[v]=min(dis[v],ww[i]);
}
n=scc_cnt;
ans=
0;
for (
int i=
1;i<=scc_cnt;i++)
{
if (i!=sccno[
0])
ans+=dis[i];
}
printf(
"%d\n",ans);
}
return 0;
}
