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 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

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++

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

bài giải NKRACING spoj – Vòng đua F1