题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3072
题目大意：为一个有向连通图加边。使得整个图全连通，有重边出现。
解题思路：
先用Tarjan把强连通分量缩点。
由于整个图肯定是连通的，所以枚举每一条边，记录到非0这个点所在连通分量的最小cost。
一共需要累加cnt-1个连通分量的cost。
在Tarjan过程中的重边，可以用链式前向星结构解决。（vector邻接表会算错）
在枚举每条边的cost中，用cost[i]记录i这个连通分量的最小cost。
最后不要算上cost[scc[0]]，因为0点所在的连通分量是免费的。
#include "cstdio"
#include "algorithm"
#include "stack"
#include "cstring"
using namespace std;
#define maxn 50005
#define LL long long
int head[maxn],tot,pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,cnt,cost[maxn];
stack<int> S;
struct Edge
{
int to,next,c;
}e[];
void addedge(int u,int v,int c)
{
e[tot].to=v;
e[tot].next=head[u];
e[tot].c=c;
head[u]=tot++;
}
void tarjan(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(!pre[v])
{
tarjan(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if (!sccno[v]) lowlink[u]=min(lowlink[u],lowlink[v]);
}
if(lowlink[u]==pre[u])
{
cnt++;
while()
{
int x=S.top();S.pop();
sccno[x]=cnt;
if(x==u) break;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
int n,m,u,v,c;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-,sizeof(head));
memset(pre,,sizeof(pre));
memset(lowlink,,sizeof(lowlink));
memset(sccno,,sizeof(sccno));
memset(cost,0x3f3f,sizeof(cost));
tot=dfs_clock=cnt=;
for(int i=;i<m;i++)
{
scanf("%d%d%d",&u,&v,&c);
addedge(u,v,c);
}
for(int i=;i<n;i++)
if(!pre[i]) tarjan(i);
LL sum=;
for(int i=;i<n;i++)
for(int j=head[i];j!=-;j=e[j].next)
if(sccno[i]!=sccno[e[j].to]) cost[sccno[e[j].to]]=min(cost[sccno[e[j].to]],e[j].c);
for(int i=;i<=cnt;i++)
if(i!=sccno[])
sum+=cost[i];
printf("%I64d\n",sum);
}
}