[MST] UVA 10600 - ACM Contest and Blackout

Tìm cây khung nhỏ nhất và cây khung nhỏ thứ 2

Algorithms:

Tìm cây khung nhỏ nhất rồi đánh dấu các cạnh thuộc cây khung nhỏ nhất

Với mỗi cạnh đã đánh dấu tìm cây khung nhỏ nhất ko chứa cạnh đó:

- Union tất cả các cạnh đk đánh dấu ngoại trừ cạnh đang xét

- Lúc này, đồ thị sẽ chỉ còn lại 2 component, duyệt các cạnh (đã sort) nếu v[i].x và v[i].y không chung gốc thì nối lại và cộng trọng số vào kết quả.

Cây khung tốt nhất tìm được sẽ là cây khung nhỏ thứ 2

Traps:

Lỗi phổ biến là sau khi loại bỏ 1 cạnh thuộc cây khung nhỏ nhất ta tìm luôn cây khung nhỏ nhất của các cạnh còn lại, điều này không đảm bảo việc các đỉnh được liên thông sau khi tìm. Ví dụ trong trường hợp cạnh bị loại là cầu

FOR(I,1,test)
{
cin>>n>>m;
FOR(i,1,m) cin>>v[i].x>>v[i].y>>v[i].cost;
sort(v+1,v+m+1);
SET(a,false);
SET(ar,-1);
res=0;
res2=1e9;
for(int i = 1;i<=m;i++)
{
if(adjustUsingUnionFind(v[i].x,v[i].y)==1)
{
res+= v[i].cost;
a[i]=true;
//printf("%d\n",v[i].cost);
}
}

FOR(j,1,m)
if (a[j])
{
SET(ar,-1);
ll tg=0;
FOR(i,1,m)
if (i!=j && a[i])
{
if(adjustUsingUnionFind(v[i].x,v[i].y)==1)
{
tg+= v[i].cost;
}
}
ll d=0;
FOR(i,1,m)
if (!a[i])
{
if(adjustUsingUnionFind(v[i].x,v[i].y)==1)
{
tg+=v[i].cost;
d=1;
break;
}
}

if (d)
res2=min(res2,tg);
}

cout<<res<<" "<<res2<<endl;
}