#include<math.h>

#include<string.h>

#define vc 32767

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int i,j,n,x,y;

int c[20][20],tr[20],s[20],chuaxet[20];

void khoitao();

void inra1();

void euler();

void xtoy();

void cayphu();

void taomang();

void ngaunhien();

//====================//

void main()

{

clrscr();

n=0;

taomang();

if(n!=0)

{

printf("\tMa tran sinh ra la:

");

inra1();

khoitao();

euler();

printf("\tNhap vao dinh suat phat X=");

scanf("%d",&x);

printf("\tNhap vao dinh dich Y=");

scanf("%d",&y);

xtoy();

cayphu();

}

getch();

}

void taomang()

{

printf("\tnhap n=");

scanf("%d",&n);

randomize();

for(i=1;i<=n;i++)

{

c[i][i]=0;

for(j=i+1;j<=n;j++)

c[i][j]=c[j][i]=random(99);

}

}

void khoitao()

{

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if (c[i][j]==0)

c[i][j]=vc;

for(i=1;i<=n;i++)

tr[i]=chuaxet[i]=0;

for(i=1;i<=n;i++)

s[i]=vc;

}

void inra1()

{

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

printf("%5d",c[i][j]);

printf("

");

}

}

void euler()

{

int bac,kt=1;

for(i=1;i<=n;i++)

{

bac=0;

for(j=1;j<=n;j++)

if(c[i][j]!=vc)

bac++;

if (((bac%2)==1)||(bac==0))

kt=0;

}

if (kt==1)

printf("

\tDo thi tren la do thi Euler

");

else

printf("

\tDo thi tren khong phai la do thi Euler

");

}

void xtoy()

{

int kt,k,b[20];

chuaxet[y]=1;s[y]=0;tr[y]=0;

do

{

kt=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if ((chuaxet[j]==1)&&(c[i][j]!=vc))

{

if ((s[j]+c[i][j])<s[i])

{

s[i]=s[j]+c[i][j];

tr[i]=j;

chuaxet[i]=1;

kt=1;

}

}

}while(kt==1);

if(s[x]!=vc)

{

b[1]=x;k=1;

while(tr[b[k]]!=0)

{

k++;

b[k]=tr[b[k-1]];

}

printf("\tDuong di ngan nhat tu dinh %d --> %d la:

\t\t",x,y);

for(i=1;i<k;i++)

printf("%d -->",b[i]);

printf("%d

",b[k]);

printf("\t\tDo dai doan duong la:%d",s[x]);

}

else

{

printf("\tKhong ton tai duong di tu dinh %d --> %d

",x,y);

}

}

void cayphu()

{

int p=1,g[20][2],k,h,dodai,kt,min,u,cl;

for(i=1;i<=n;i++)

chuaxet[i]=0;

chuaxet[p]=1;k=1;

for(i=1;i<=n;i++)

if(p!=i)

{

s[i]=c[p][i];

tr[i]=p;

}

kt=0;h=0;cl=0;

while((kt==0)&&(cl==0))

{

min=vc;

for(i=1;i<=n;i++)

if((chuaxet[i]==0)&&(s[i]<=min))

{

min=s[i];

u=i;

}

k++;

chuaxet[u]=1;

h++;

g[h][1]=tr[u];

g[h][2]=u;

if (c[u][tr[u]]==vc) cl=1;

if(k==n)

{

printf("

\tCay khung nho nhat tim thay:");

if(cl==0)

{

kt=1;

dodai=0;

printf("

\t\t");

for(i=1;i<h;i++)

{

printf("(%d,%d);",g[i][1],g[i][2]);

dodai+=c[g[i][1]][g[i][2]];

}

printf("(%d,%d)

",g[h][1],g[h][2]);

dodai+=c[g[h][1]][g[h][2]];

printf("\t\tDo dai cay khung: %d",dodai);

}else

{

printf("

\t");

for(i=1;i<=30;i++)

printf("*");

printf("

");

printf("\t* Khong the tim duoc cay phu *");

printf("

\t");

for(i=1;i<=30;i++)

printf("*");

printf("

");

}

}else

{

for(i=1;i<=n;i++)

if((chuaxet[i]==0)&&(c[u][i]<s[i]))

{

s[i]=c[u][i];

tr[i]=u;

}

}

}

}