学步园

  见网上都没有这个算法的具体模板，我不为什么，也许是太简单啦
在队友的帮助下，写了一个，分享一下，
追求简单易懂（不求短码） 你如果理解后，可以大大的简写代码（不用写两个dfs 一个就够了）

对应hdoj 3072

题意：给你n个点，m条边，每条边有一个权值（传送message代价），已知强连通分支内部不需花费，求minimal
cost

步骤：

1.缩点n->scc个点

2.将到这scc个点的最小代价计算出来

3.相加

 #include
<stdio.h>
#include <string.h>

#define INF   
0x3f3f3f3f
#define V   
50050
#define E   
100050

struct edge
{
    int to,
cost, next;
}Edge1[E], Edge2[E];  //edge1是正向图G edge2
是图G的逆GT
int head1[V], head2[V], e, n;

void addedge(int u, int v, int c)
{
    Edge1[e].to
= v;
   
Edge1[e].cost = c;
   
Edge1[e].next = head1[u];
    head1[u] =
e;
    Edge2[e].to
= u;
   
Edge2[e].cost = c;
   
Edge2[e].next = head2[v];
    head2[v] =
e++;
}

int cnt, scc;
int order[V],vis[V], scc_id[V], dist[V];
//order是记录点出栈的时间，ssc_id 记强连通分量的集合 在同一强连通分量中 ssc_id[i] 的值相同
int dfs(int u)  //搜索图G 记录各点出栈时间
{
    for (int
i=head1[u]; i!=-1; i=Edge1[i].next)
    {
   
    int v =
Edge1[i].to;
   
    if (vis[v]
== 0)
   
    {
   
   
    vis[v] =
1;
   
   
   
dfs(v);
   
    }
    }
    order[++cnt]
= u;    //order
[1..n] 记录的是出栈时间最早的 order[1]最早
    return
0;
}

int redfs(int u)  //搜索GT图 缩点
{
    for (int
i=head2[u]; i!=-1; i=Edge2[i].next)
    {
   
    int v =
Edge2[i].to;
   
    if
(scc_id[v] == 0)
   
    {
   
   
    scc_id[v] =
scc;
   
   
   
redfs(v);
   
    }
    }
    return
0;
}

int kosaraju()
{
    int i,
u;
    cnt = scc =
0;   
//scc是强连通图的个数
   
memset(order, 0, sizeof(order));
    memset(vis,
0, sizeof(vis));
    for (i=0;
i!=n; ++i)
    {
   
    if (vis[i]
== 0)
   
    {
   
   
    vis[i] =
1;
   
   
   
dfs(i);
   
    }
    }
   
memset(scc_id, 0, sizeof(scc_id));
    for (i=n;
i!=0;
--i)          
//从出栈时间最晚的开始搜索缩点 这样不会连通到别的树上
    {
   
    u =
order[i];
   
    if
(scc_id[u] == 0)