Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: code tìm cây có trọng lượng nhỏ nhất bằng giải thuật prim-cách chạy tay code này

  1. #1
    Ngày gia nhập
    01 2011
    Bài viết
    2

    Mặc định code tìm cây có trọng lượng nhỏ nhất bằng giải thuật prim-cách chạy tay code này

    anh chị ơi em đang gặp vấn đề về:code tìm cây có trọng lượng nhỏ nhất bằng giải thuật prim-cách chạy tay
    yêu cầy:
     Cập nhật dữ liệu về đồ thị.
     Biểu diễn đồ thị trên màn hình.
     Kiểm tra tính liên thông.
     Cho phép tìm cây có trọng lượng nhỏ nhất.

    em đang học lập trình c++

    ai co xin poss giùm em

    love_rua_con206@yahoo.com.vn

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    mình có code prim+heap, kruskal+disjointset, code n^2 bạn tìm trong sách vậy

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  3. #3
    Ngày gia nhập
    02 2011
    Bài viết
    1

    vậy bạn có code chưa z..mình cũng cần nà.có gì share cho mình với hé.hoangluanchau89@yahoo.com


  4. #4
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Đề bài ở đây
    http://vn.spoj.pl/problems/QBMST/
    Code prim+heap viết hồi năm 2 nên hơi chuối và ko kiểm tra điều kiện, nếu cần thì thêm vào
    C++ Code:
    1. #include<cstdio>
    2. #include<conio.h>
    3. #include<algorithm>
    4. #define nm 10001
    5. #define oo 1000000000
    6. using namespace std;
    7. typedef struct node*ptr;
    8. struct node
    9. {
    10.        int data,cost;
    11.        ptr pnext;
    12. };
    13. void chen(ptr &f,int x,int c)
    14. {
    15.      ptr p=new node;
    16.      p->data=x;
    17.      p->cost=c;
    18.      p->pnext=f;
    19.      f=p;
    20. }
    21. int n,m;
    22. ptr a[nm];
    23. int h[nm],nh=0;
    24. int pos[nm];
    25. int d[nm];
    26. bool check[nm];
    27. int res=0;
    28. void update(int u)
    29. {
    30.      int r,c;
    31.      c=pos[u];
    32.      if (!c)c=++nh;
    33.      r=c/2;
    34.      while (r)
    35.      {
    36.            if (d[h[r]]<=d[u])break;
    37.            h[c]=h[r];
    38.            pos[h[c]]=c;
    39.            c=r;
    40.            r=c/2;
    41.      }
    42.      h[c]=u;
    43.      pos[h[c]]=c;
    44. }
    45. int visit()
    46. {
    47.     int r,c,v;
    48.     int kq=h[1];
    49.     v=h[nh--];
    50.     r=1;
    51.     while (r*2<=nh)
    52.     {
    53.           c=r*2;
    54.           if (c<nh&&d[h[c+1]]<d[h[c]])c++;
    55.           if (d[h[c]]>=d[v])break;
    56.           h[r]=h[c];
    57.           pos[h[r]]=r;
    58.           r=c;
    59.     }
    60.     h[r]=v;
    61.     pos[h[r]]=r;
    62.     return kq;
    63. }
    64. int main()
    65. {
    66.     freopen("QBMST.txt","r",stdin);
    67.     scanf ("%d%d",&n,&m);
    68.     for (int i=1;i<=m;i++)
    69.     {
    70.         int u,v,c;
    71.         scanf ("%d%d%d",&u,&v,&c);
    72.         chen(a[u],v,c);
    73.         chen(a[v],u,c);
    74.     }
    75.     for (int i=1;i<=n;i++)
    76.         d[i]=oo;
    77.     update(1);
    78.     d[1]=0;
    79.     while (nh)
    80.     {
    81.           int u=visit();
    82.           res+=d[u];
    83.           check[u]=true;
    84.           ptr p=a[u];
    85.           while (p)
    86.           {
    87.                 int v=p->data;
    88.                 if (!check[v]&&d[v]>p->cost)
    89.                 {
    90.                    d[v]=p->cost;
    91.                    update(v);
    92.                 }
    93.                 p=p->pnext;
    94.           }
    95.     }
    96.     printf ("%d",res);
    97.     getch();
    98.     return 0;
    99. }

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

Các đề tài tương tự

  1. Lập trình C Tìm cây khung nhỏ nhất bằng giải thuật Prim trên C
    Gửi bởi ba_duong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 02-12-2012, 09:05 PM
  2. Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
    Gửi bởi lephithang trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 25-03-2011, 06:57 AM
  3. Lập trình C++ Tìm đường đi ngắn nhất viết bằng giải thuật prim trong lập trình C++?
    Gửi bởi minhtoan991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 25-02-2011, 05:49 PM
  4. Bài tập C Tìm cây khung nhỏ nhất trên C bằng giải thuật Prim
    Gửi bởi lephithang trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 18-02-2011, 08:25 PM
  5. Code thuật toán prim trê C++
    Gửi bởi dinhviethoang trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 06-05-2010, 09:06 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn