bài giải NKRACING spoj – Vòng đua F1
Nguồn đề bài http://vn.spoj.com/problems/NKRACING/ 1. Đề bài NKRACING spoj Singapore sẽ tổ chức một cuộc đua xe Công Thức 1 vào năm 2008. Trước khi cuộc đua diễn ra, đã xuất hiện một số cuộc đua về đêm trái luật. Chính quyền muốn thiết kế một hệ thống kiểm soát giao thông để bắt ...
Nguồn đề bài http://vn.spoj.com/problems/NKRACING/
1. Đề bài NKRACING spoj
Singapore sẽ tổ chức một cuộc đua xe Công Thức 1 vào năm 2008. Trước khi cuộc đua diễn ra, đã xuất hiện một số cuộc đua về đêm trái luật. Chính quyền muốn thiết kế một hệ thống kiểm soát giao thông để bắt giữ các tay đua phạm luật. Hệ thống bao gồm một số camera đặt trên các tuyến đường khác nhau. Để đảm bảo tính hiệu quả cho hệ thống, cần có ít nhất một camera dọc theo mỗi vòng đua.
Hệ thống đường ở Singapore có thể được mô tả bởi một dãy các nút giao thông và các đường nối hai chiều (xem hình vẽ). Một vòng đua bao gồm một nút giao thông xuất phát, tiếp theo là đường đi bao gồm ít nhất 3 tuyến đường và cuối cùng quay trở lại điểm xuất phát. Trong một vòng đua, mỗi tuyến đường chỉ được đi qua đúng một lần, theo đúng một hướng.
Chi phí để đặt camera phụ thuộc vào tuyến đường được chọn. Các số nhỏ trong hình vẽ cho biết chi phí để đặt camera lên các tuyến đường. Các số lớn xác định các nút giao thông. Camera được đặt trên các tuyến đường chứ không phải tại các nút giao thông. Bạn cần chọn một số tuyến đường sao cho chi phí lắp đặt là thấp nhất đồng thời vẫn đảm bảo có ít nhất một camera dọc theo mỗi vòng đua.
Viết chương trính tìm cách đặt các camera theo dõi giao thông sao cho tổng chi phí lắp đặt là thấp nhất.
Dữ liệu
- Dòng đầu tiên chứa 2 số nguyên n, m ( 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000) là số nút giao thông và số đường nối. Các nút giao thông được đánh số từ 1 đến n.
- m dòng tiếp theo mô tả các đường nối, mỗi dòng bao gồm 3 số nguyên dương cho biết hai đầu mút của tuyến đường và chi phí lắp đặt camera. Chi phí lắp đặt thuộc phạm vi [1, 1000].
Kết quả
In ra 1 số nguyên duy nhất là tổng chi phí lắp đặt thất nhất tìm được.
Ví dụ
Dữ liệu:
6 7
1 2 5
2 3 3
1 4 5
4 5 4
5 6 4
6 3 3
5 2 3
Kết qủa
6
———————————————-
2. Gợi ý NKRACING spoj
– Xây dựng cây khung lớn nhất bằng Kruskal.
– Kết quả bài toán chính là tổng trọng số của cây khung lớn nhất
3. code tham khảo NKRACING spoj (pascal, C++):
Pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | const fi='; nmax=10000; mmax=100000; type data=longint; canh=record u,v,c:data; end; var f:text; a:array[1..mmax] of canh; N,m:data; root:array[0..nmax+1] of data; procedure docfile; var i:data; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to m do readln(f,a[i].u,a[i].v,a[i].c); close(f); end; procedure sort(l,r: longint); var i,j,x: longint; y:canh; begin i:=l; j:=r; x:=a[(l+r) shr 1].c; repeat while a[i].c>x do inc(i); while x>a[j].c do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; function findroot(x:data):data; begin if x<>root[x] then root[x]:=findroot(root[x]); exit(root[x]); end; procedure union(x,y:data); var u,v:data; begin u:=findroot(x); v:=findroot(y); if u=v then exit; root[v]:=u; end; procedure kruskal; var i,j,t,x,y,s:data; begin for i:=1 to n do root[i]:=i; t:=0; s:=0; for i:=1 to m do begin s:=s+a[i].c; x:=findroot(a[i].u); y:=findroot(a[i].v); if x<>y then begin union(a[i].u,a[i].v); t:=t+a[i].c; end; end; writeln(s-t); end; begin docfile; sort(1,m); kruskal; end. |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> ip; vector<ip> v; int par[10005]; int anc(int p) { if(p==par[p]) return p; return par[p]=anc(par[p]); } int main() { //freopen("test.inp","r",stdin); int n,m,i,j,l,mst=0; scanf("%d%d",&n,&m); for(i=1;i<=n;++i) par[i]=i; while(m--) { scanf("%d%d%d",&i,&j,&l); mst+=l; v.push_back(ip(l,ii(i,j))); } sort(v.begin(),v.end()); j=0; for(i=v.size()-1;i>=0 && j<n-1;--i) { int a=anc(v[i].second.first),b=anc(v[i].second.second); if(a!=b) { par[a]=b; mst-=v[i].first; ++j; } } printf("%d",mst); } |
[/sociallocker]
