学步园

强联通的缩点问题。

归为模板题。

hdu 1872：

代码：

#include<stdio.h>
#include<string.h>
#include<vector>
#include<climits>
using namespace std;

const int mx=2001;

int n,m;
int top,cnt,index,res;
int low[mx],dfn[mx],vis[mx];
int color[mx],stack[mx];
int price[mx],to[mx];

struct node
{
    int s,e;
    int next;
} edge[mx];
int head[mx];

void init()
{
    index=top=cnt=res=0;
    for(int i=0; i<mx; i++)
    {
        low[i]=dfn[i]=vis[i]=color[i]=to[i]=0;
        head[i]=-1;
    }
}

void add(int a,int b)
{
    edge[res].s=a;
    edge[res].e=b;
    edge[res].next=head[a];
    head[a]=res++;
}
void tarjan(int u)
{
    low[u]=dfn[u]=++index;
    vis[u]=1;
    stack[top++]=u;
    for(int j=head[u]; j!=-1; j=edge[j].next)
    {
        int v=edge[j].e;
        if(dfn[v]==0)
        {
            tarjan(v);
            low[u]=low[u]<low[v]?low[u]:low[v];
        }
        if(vis[v]&&dfn[v]<low[u])
            low[u]=dfn[v];
    }
    if(dfn[u]==low[u])
    {
        cnt++;
        int v;
        do
        {
            v=stack[--top];
            vis[v]=0;
            color[v]=cnt;
        }
        while(v!=u);
    }
}
void sove()
{
    for(int i=1; i<=n; i++)
    {
        if(dfn[i]==0)
            tarjan(i);
    }
    for(int i=0; i<res; i++)
    {
        int a=edge[i].s;
        int b=edge[i].e;
        if(color[a]!=color[b])
        {
            to[color[b]]++;
        }
    }
    int sum=0,count=0;
    for(int i=1; i<=cnt; i++)
    {
        if(to[i]==0)
        {
            int mn=INT_MAX;
            for(int j=1; j<=n; j++)
            {
                if(color[j]==i&&price[j]<mn)
                    mn=price[j];
            }
            count++;
            sum+=mn;
        }
    }
    printf("%d %d\n",count,sum);
}
int main()
{
    //freopen("a.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1; i<=n; i++)
            scanf("%d",&price[i]);
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        sove();
    }
    return 0;
}

hdu 3072 ：

代码 ：

#include<stdio.h>
#include<string.h>
#include<limits.h>
const int mx1=50005;
const int mx2=100005;

int n,m,index,cnt,res,top;
int dfn[mx1],low[mx1],vis[mx1];
int color[mx1],stack[mx1];
int to[mx1],val[mx1];
struct node
{
    int s,e,c;
    int next;
} edge[mx2];
int head[mx2];

void init()
{
    index=top=cnt=res=0;
    for(int i=0; i<mx1; i++)
    {
        dfn[i]=low[i]=vis[i]=color[i]=to[i]=0;
        val[i]=INT_MAX;
    }
    memset(head,-1,sizeof(head));
}

void add(int a,int b,int c)
{
    edge[res].s=a;
    edge[res].e=b;
    edge[res].c=c;
    edge[res].next=head[a];
    head[a]=res++;
}

void tarjan(int u)
{
    low[u]=dfn[u]=++index;
    stack[top++]=u;
    vis[u]=1;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        //printf("*************%d  \n",u);
        int v=edge[i].e;
        if(dfn[v]==0)
        {
            tarjan(v);
            low[u]=low[u]<low[v]?low[u]:low[v];
        }
        else if(vis[v]&&low[u]>dfn[v])
            low[u]=dfn[v];
    }
    if(low[u]==dfn[u])
    {
        cnt++;
        int v;
        do
        {
            v=stack[--top];
            vis[v]=0;
            color[v]=cnt;
        }
        while(v!=u);
    }
}

int sove()
{
    for(int i=1; i<=n; i++)
    {
        if(dfn[i]==0)
            tarjan(i);
    }
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=head[i]; j!=-1; j=edge[j].next)
        {
            int v=edge[j].e;
            if(color[i]!=color[v]&&val[color[v]]>edge[j].c)
                val[color[v]]=edge[j].c;
        }
    }
    for(int i=1; i<=cnt; i++)
    {
        if(val[i]<INT_MAX)
            sum+=val[i];
    }
    printf("%d\n",sum);
}
int main()
{
    //freopen("a.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a+1,b+1,c);
        }
        sove();
    }
    return 0;
}