有向图——最小点基和最小权点基

??? 考虑这样一个问题：

??? 老师想通知他的所有学生一个消息，虽然他手上有他们的联系方式，但是一个一个联系太耗时间和电话费了。他知道其它人也有一些别人的联系方式，这样可以通知他人，再让他们去通知一下别人。现在要求出至少需要联系多少人，最少需要多少花费，使得所有的人都被通知到。

??? 上述问题可以抽象为：图G中，每个点都有一个权值，若a能联系到b，则连边(a,b)。选出最少的点数(或者权值最小)，使从这些点能到达所有点。

??? 解：求图G的强连通分量，入度为0的强连通分量个数即为最小点基，从每个入度为0的强连通分量中取出权值最小的点，构成的集合即最小权点基。求强连通Trajan算法不再赘述。

?

例：HDU1827

/*最小点基和最小权点基：    最小点基=从每个入度为0的SCC中任意选出一个点的集合    最小权点基=从每个入度为0的SCC中选出最小权值的点的集合*/#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int INF = 0x7fffffff;const int MAX = 1005;int n,m;int node[MAX];struct Edge{    int from;    int to;    int next;};Edge e[2005];int head[MAX],edgeNum;int dfn[MAX],low[MAX],seq;int stack[MAX],top;bool inStack[MAX];int belong[MAX],cnt;int ind[MAX];int cost[MAX];void addEdge(int from, int to){    e[edgeNum].from = from;    e[edgeNum].to = to;    e[edgeNum].next = head[from];    head[from] = edgeNum++;}int min(int a, int b){    return a<b?a:b;}void Tarjan(int u){    dfn[u] = low[u] = seq++;    stack[top++] = u;    inStack[u] = true;    for(int i = head[u]; i != -1; i = e[i].next)    {        int w = e[i].to;        if(dfn[w] < 0)        {            Tarjan(w);            low[u] = min(low[u],low[w]);        }        else if(inStack[w])            low[u] = min(low[u],dfn[w]);    }    if(dfn[u] == low[u])    {        int v;        cnt++;        do        {            top--;            v =stack[top];            inStack[v] = false;            belong[v] = cnt;        }while(u != v);    }}void solve(){    int i;    for(i = 1; i <= n; i++)        if(dfn[i] < 0)            Tarjan(i);    for(i = 0; i < edgeNum; i++)    {        if(belong[e[i].from] != belong[e[i].to])            ind[belong[e[i].to]]++;    }    for(i = 1; i <= n; i++)    {        if(cost[belong[i]] > node[i])            cost[belong[i]] = node[i];    }    int result1=0,result2=0;    for(i = 1; i <= cnt; i++)    {        if(ind[i]==0)        {            result1++;            result2 += cost[i];        }    }    printf("%d %d\n",result1,result2);}int main(){    int i;    int from,to;    while(scanf("%d %d",&n,&m)!=EOF)    {        edgeNum = seq = cnt = top = 0;        memset(head,-1,sizeof(head));        memset(dfn,-1,sizeof(dfn));        memset(inStack,0,sizeof(inStack));        memset(ind,0,sizeof(ind));        for(i = 1; i <= n; i++)            cost[i] = INF;        for(i = 1; i <= n; i++)            scanf("%d",&node[i]);        for(i = 0; i < m; i++)        {            scanf("%d %d",&from,&to);            addEdge(from,to);        }        solve();    }    return 0;}

?