hdu 3072 有向图缩点成最小树形图计算最小权

题意，从0点出发，遍历所有点，遍历边时候要付出代价，在一个SCC中的边不要付费。求最小费用。

有向图缩点（无需建立新图，，n《=50000，建则超时），遍历边，若不在一个SCC中，用一个数组更新记录最小到达该连通分量的最小边权即可。。。边聊天，边1A，哈哈。。。

#include<iostream>

#include<stack>

#include<queue>

#include<cstdio>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxv=50005,maxe=100005;

int nume=0;int head[maxv];int e[maxe][3];

void inline adde(int i,int j,int c)

{

    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;

    e[nume++][2]=c;

}

int dfn[maxv];int low[maxv];int vis[maxv];int ins[maxv]; stack<int>sta;

int scc[maxv];int numb=0;int times=0;

int n,m;

void tarjan(int u)

{

    dfn[u]=low[u]=times++;

    ins[u]=1;

    sta.push(u);

    for(int i=head[u];i!=-1;i=e[i][1])

    {

        int v=e[i][0];

        if(!vis[v])

        {

            vis[v]=1;

            tarjan(v);

            if(low[v]<low[u])low[u]=low[v];

        }

        else if(ins[v]&&dfn[v]<low[u])

        {

            low[u]=dfn[v];

        }

    }

    if(low[u]==dfn[u])

    {

        numb++;

        int cur;

       do

        {

            cur=sta.top();

            sta.pop();

            ins[cur]=0;

            scc[cur]=numb;

        }while(cur!=u);

    }

}

int mincost_to_v[maxv];    //记录

void solve()

{

     vis[0]=1;

     tarjan(0);

    for(int i=0;i<n;i++)

      for(int j=head[i];j!=-1;j=e[j][1])

      {

          int v=e[j][0];

          if(scc[i]!=scc[v])

        {

            if(e[j][2]<mincost_to_v[scc[v]])

             {

                 mincost_to_v[scc[v]]=e[j][2];

             }

        }

      }

    int sums=0;

    for(int i=1;i<=numb;i++)

        {

            if(mincost_to_v[i]!=inf)    //起点

             sums+=mincost_to_v[i];

        }

   printf("%d\n",sums);

}

void read_build()

{

    int aa,bb,cc;

    for(int i=0;i<m;i++)

    {

        scanf("%d%d%d",&aa,&bb,&cc);

        adde(aa,bb,cc);

    }

}

void init()

{

    numb=times=nume=0;

    for(int i=0;i<maxv;i++)

      {

          head[i]=-1;

          ins[i]=dfn[i]=low[i]=scc[i]=vis[i]=0;

          mincost_to_v[i]=inf;

      }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

        read_build();

        solve();

    }

    return 0;

}

巴特西

hdu 3072 有向图缩点成最小树形图计算最小权

最新文章

热门文章