Heap Spanning Tree

Tiêu đề: Heap Spanning Tree 04.12.08 0:01

lỡ làm Heap rồi, thôi thì quất lun đi cho đủ bộ.
thấy có bài về Heap nữa, mọi người thử xem

2786. Cây khung nhỏ nhất ( HEAP )
Mã bài: QBMST

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G
Input

Dòng 1: Chứa hai số n, m (1 <= n <= 10000; 1 <= m <= 15000)

M dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (1 <= u, v <= n; 0 <= c <= 10000).
Output

Gồm 1 dòng duy nhất: Ghi trọng số cây khung nhỏ nhất
Example
Input:
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2

Output:
5

http://vnoi.info/index.php?option=com_voj&task=viewStatement&problem=QBMST

Tiêu đề: Re: Heap Spanning Tree 04.12.08 19:37

thấy có Thi (bt09) AC rồi, không biết có ai làm nữa không?
mà sao đặc điểm trên vn.SPOJ hình như top score luôn thuộc về PAS thì phải Sad

Phải làm gì đó đi chứ.

--

04-12-2008 đã spam và giành lại vị trí độc tôn cho C++ với 0.07s rabbit

Tiêu đề: Re: Heap Spanning Tree 07.12.08 23:29

Code:: //MST (minimum spanning tree)
#include <stdio.h>
#include <iostream>
#define maxN 10001
#define maxE 15001
using namespace std;

int n, m;
int c[maxE][2];
int w[maxE];
int tree[maxN];
long long trso;

void DownHeap(int k) {
int i, t1, t2;
int x;

x = w[k];
t1 = c[k][0]; t2 = c[k][1];

while (k <= m/2) {
i = k<<1;
if (i<m)
if (w[i] > w[i+1]) i++;
if (x <= w[i]) break;
w[k] = w[i];
c[k][0] = c[i][0]; c[k][1] = c[i][1];
k = i;
}
w[k] = x;
c[k][0] = t1; c[k][1] = t2;
}

void ghep(int u, int v) {
int i, tmp;
trso += w[1];
tmp = tree[v];
for (i=1; i<=n; i++)
if (tree[i]==tmp) tree[i] = tree[u];
}

int XayDung() {
int i, sc, u, v;
for (i=1; i<=n; i++) tree[i] = i;
for (i=m/2; i>=1; i--) DownHeap(i);

sc = 1;
do {
if (tree[c[1][0]] != tree[c[1][1]])
{
ghep(c[1][0], c[1][1]);
sc += 1;
if (sc==n) return 1;
}

//to chuc lai heap
c[1][0] = c[m][0]; c[1][1] = c[m][1];
w[1] = w[m];
m--;
DownHeap(1);
} while (sc<n);
}

int main() {
int x, y, d;

scanf("%d%d", &n, &m);
for (int i=1; i<=m; i++)
{
scanf("%d%d%d", &c[i][0], &c[i][1], &w[i]);
}
trso = 0;
XayDung();
printf("%lld\n", trso);
//system("PAUSE");
}

á á, a Thuận làm Heap của STL hay sao mà đc 0.07s? up code lên cho xem với Razz

cái đoạn code trên của e là code mà e trung thành từ trước tới nay (dĩ nhiên là đúng mới trung thành ^^ ) mà nó chạy đên 1.26s

Tiêu đề: Re: Heap Spanning Tree 07.12.08 23:43

STL code ngắn, thấy tốc độ nó khá nhanh.

Bài này nhập nhiều nên dùng code nhập chôm bên Input đó, chạy cho nhanh

Dũng log vô lấy về đi

https://vn.spoj.pl/status/QBMST,hcmut/

tư tưởng chính như sau:

Code:: D[0] = 0;
Q.push(ii(0,0));
i = 0;
while (i<N) {
// fetch the nearest element
top = Q.top();
Q.pop();
// v is vertex index, w is the distance
v = top.second;
   w = top.first;

if (w <= D[v]) {
D[v] = 0;
TONG += w;
i++;

// iterate through all outcoming edges from v
for (it = G[v].begin(); it != G[v].end(); it++){
v2 = it->second;
         cost = it->first;
if(D[v2] > cost) {
// update distance if possible
D[v2] = cost;
// add the vertex to queue
Q.push(ii(D[v2],v2));
}
}
}
}

» Heap Dijkstra
» Hàng đợi có độ ưu tiên (HEAP)