设为首页 加入收藏

TOP

hdu 3072 有向图缩点成最小树形图计算最小权
2015-07-20 17:53:36 来源: 作者: 【 】 浏览:2
Tags:hdu 3072 向图缩 最小 树形 计算

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

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

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        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
       
        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]
        
         

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇leetcode 刷题之路 92 Climbing S.. 下一篇POJ 3087 Shuffle'm Up (模..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: