设为首页 加入收藏

TOP

不定根最小树形图实例分析(四)
2013-12-05 13:05:29 来源: 作者: 【 】 浏览:271
Tags:不定 最小 树形 实例分析


    //找到每个点的最小入边
    for (int i = 0 ; i < NE ; i ++ ){
    int s = ed[i].s ;
    int e = ed[i].e ;
    if(ed[i].l < in[e] && s != e){
    pre[e] = s ;
    in[e] = ed[i].l ;
    }
    }
    //最小入边
    //        for (int i = 1 ; i < NV ; i ++ ){
    //            cout 《 i 《 " : " 《 in[i] 《 endl;
    //        }
    for (int i = 0 ; i < NV ; i ++ ){//除根节点外所有点都找到一条入边
    if(i == root)continue ;
    if(in[i] == inf)return -1 ;
    }
    //找环
    int cntnode = 0 ;
    mem(vis ,-1) ;
    mem(id ,-1) ;
    in[root] = 0 ;
    for (int i = 0 ; i < NV ; i ++ ){
    ret += in[i] ;
    int v = i ;
    while(vis[v] != i && id[v] == -1 && v != root){
    vis[v] = i ;
    v = pre[v] ;
    }
    if(v != root && id[v] == -1){
    for (int u = pre[v] ; u != v ; u = pre[u]){
    id[u] = cntnode ;
    }
    id[v] = cntnode ++ ;
    }
    }
    if(cntnode == 0)break ;//无环
    for (int i = 0 ; i < NV ; i ++ ){
    if(id[i] == -1)id[i] = cntnode ++ ;
    }
    //缩点
    for (int i = 0 ; i < NE ; i ++ ){
    int s = ed[i].s ;
    int e = ed[i].e ;
    ed[i].s = id[s] ;
    ed[i].e = id[e] ;
    if(ed[i].s != ed[i].e){
    ed[i].l -= in[e] ;
    }
    }
    NV = cntnode ;
    root = id[root] ;
    }
    return ret ;
    }
    int main() {
    while(cin 》 n , n ){
    int a , b ;
    for (int i = 1 ; i <= n ; i ++ ){
    scanf("%lf %lf",&P[i].x ,&P[i].y) ;
    }
    init() ;
    double dis_sum = 0 ;
    for (int i = 1 ; i <= n ;i ++ ){
    for (int j = 1 ; j <= n ;j ++ ){
    if(i == j)continue ;
    double dis = getdis(i , j) ;
    if(P[i].y <= P[j].y){
    add(i , j , dis) ;
    //                    cout 《 dis 《 endl;
    dis_sum += dis ;
    }
    }
    }
    S = 0 ;
    for (int i = 1 ; i <= n ; i ++ ){
    add(S , i , inf - 1 ) ;
    }
    printf("%.2f\n",Directed_MST(0 , n + 1 , num ) - inf + 1) ;
    }
    return 0 ;
    }

      

首页 上一页 1 2 3 4 5 下一页 尾页 4/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇王子选公主结婚POJ问题 下一篇一道最小树形图的基础题

评论

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

·PostgreSQL 索引 - (2025-12-25 22:20:43)
·MySQL Node.js 连接 (2025-12-25 22:20:41)
·SQL 撤销索引、表以 (2025-12-25 22:20:38)
·Linux系统简介 (2025-12-25 21:55:25)
·Linux安装MySQL过程 (2025-12-25 21:55:22)