ĐỀ THI MÔN Cấu Trúc Dữ Liệu và Giải Thuật học viện công nghệ bưu chính viễn thông (25)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (17.52 KB, 3 trang )
M¹nh D¬ng Biªn So¹n
Bé M«n CÊu Tróc D÷ LiÖu
Gi¶i ThuËt 2012
§ª Sè 25
Trong Bé §Ò ¤n TËp
#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<conio.h>
#include<time.h>
#include<string.h>
#include<stdio.h>
ifstream datain("C:/cau truc du lieu/dethi/dothi25.in.txt");
ofstream dataout("C:/cau truc du lieu/dethi/ketqua25.out.txt");
int a[100],b[100],w[100],x[100],n,m;
/*
Thuat toan kruskal tim cay khung nho nhat
*/
void DFS(int i,int a[][100],int n)
{
x[i]=1;
for(int j=1;j<=n;j++)
if(x[j]==0&&a[i][j]==1)DFS(j,a,n);
}
int NhapDL(int &n,int &m)
{
datain>>n>>m;
for(int i=1;i<=m;i++)
datain>>a[i]>>b[i]>>w[i];
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
if(w[j]<w[i])
{
int k;
k=w[i];
w[i]=w[j];
w[j]=k;
k=a[i];
a[i]=a[j];
a[j]=k;
k=b[i];
b[i]=b[j];
b[j]=k;
}
int aa[100][100];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
aa[i][j]=0;
for(int i=1;i<=m;i++)
{aa[a[i]][b[i]]=1;
aa[b[i]][a[i]]=1;}
for(int i=1;i<=n;i++)x[i]=0;
DFS(1,aa,n);
for(int i=1;i<=n;i++)if(x[i]==0)return 0;
return 1;
}
int dem=0;
void KT(int a[][100],int i,int j,int n)
{
x[i]=1;
for(int k=1;k<=n;k++)
if(x[k]==0&&a[i][k]==1)
{
if(k==j){
dem=1;
return ;
}
KT(a,k,j,n);
}
}
void KetQua(int m)
{
int kk=0,aa[100],bb[100];
long meo=0;
for(int i=1;i<=m;i++)
{
if(kk==n-1)break;
if(kk==0)
{
kk++;
aa[kk]=a[i];
bb[kk]=b[i];
meo=w[i];
}
else
{
int max=0;
for(int j=1;j<=kk;j++)
{if(max<aa[j])max=aa[j];
if(max<bb[j])max=bb[j];
}
int xx[100][100];
for(int i=1;i<=max;i++)
for(int j=1;j<=max;j++)
xx[i][j]=0;
for(int i=1;i<=kk;i++)
{xx[aa[i]][bb[i]]=1;
xx[bb[i]][aa[i]]=1;
}
dem=0;
KT(xx,a[i],b[i],max);
if(dem==0)
{
kk++;
aa[kk]=a[i];
bb[kk]=b[i];
meo+=w[i];
}
}
}
dataout<<meo<<endl;
for(int i=1;i<=kk;i++)
dataout<<aa[i]<<" "<<bb[i]<<endl;
}
main()
{
if(NhapDL(n,m)==0)dataout<<"Khong Ton Tai Cay Khung
"<<endl;else
KetQua(m);
}
