最小生成樹
Description
在一張圖上有N個點，點與點之間的連線的花費都已經告訴你了，請你設計一下，如何解決這個「最小生成樹」的問題。要求用prim方法求解。
Input
首先輸入一個數字N（0〈=N〈=100）
然後輸入一個N*N的矩陣 其中第i行第j列的數位k表示從點i到點j需要的花費。
Output
一個數字，最少需要多少花費才能 纔能使得整張圖任意兩點都直接或者間接連通（也就是最小生成樹的權）
Sample Input
5
0 41 67 34 0
41 0 69 24 78
67 69 0 58 62
34 24 58 0 64
0 78 62 64 0
0
2
0 1
1 0
Sample Output
116
0
1
#include<bits/stdc++.h>
using namespace std;
struct jg{
int x,y,q;
};
#define INF 999999999
int G[101][101];
bool bj1[101],bj2[101];
jg nsj(int xn);
int main()
{
int n,ans,c;
jg pp;
while(cin>>n)
{
if(n==0)
{
cout<<0<<endl;
}
else
{
memset(bj1,false,sizeof(bj1));
memset(bj2,true,sizeof(bj2));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>G[i][j];
}
}
ans=0;
c=1;
bj1[1]=true;
bj2[1]=false;
while(c<n)
{
pp=nsj(n);
ans+=pp.q;
bj1[pp.y]=true;
bj2[pp.y]=false;
c++;
}
cout<<ans<<endl;
}
}
return 0;
}
jg nsj(int xn)
{
jg nsjj;
int mi,i,j;
mi=999999999;
nsjj.x=1;
nsjj.y=1;
for(i=1;i<=xn;i++)
{
if(bj1[i])
{
for(j=1;j<=xn;j++)
{
if(bj2[j])
{
if(mi>G[i][j])
{
mi=G[i][j];
nsjj.x=i;
nsjj.y=j;
nsjj.q=mi;
}
}
}
}
}
return nsjj;
}
最小生成樹(要求用kruskal演算法寫)
Description
在一張圖上有N個點，點與點之間的連線的花費都已經告訴你了，請你設計一下，如果解決這個「最小生成樹」的問題。
Input
首先輸入一個數字N（0〈=N〈=100）
然後輸入一個N*N的矩陣 其中第i行第j列的數位k表示從點i到點j需要的花費。
Output
一個數字，最少需要多少花費才能 纔能使得整張圖任意兩點都直接或者間接連通（也就是最小生成樹的權）
Sample Input
5
0 41 67 34 0
41 0 69 24 78
67 69 0 58 62
34 24 58 0 64
0 78 62 64 0
0
2
0 1
1 0
Sample Output
116
0
1
#include<bits/stdc++.h>
using namespace std;
struct jg{
int x,y,q;
};
jg a[5003];
int zz[101];
int n,e;
void Merge(int r,int t);
bool bj(const jg &u,const jg &v);
int main()
{
int ans,xx,aa,b,alg,k,i,j;
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
zz[i]=i;
}
e=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>xx;
if(i<j)
{
e++;
a[e].x=i;
a[e].y=j;
a[e].q=xx;
}
}
}
sort(a+1,a+e+1,bj);
ans=0;
k=n;
alg=1;
while(k>1)
{
aa=zz[a[alg].x];
b=zz[a[alg].y];
if(aa!=b)
{
ans+=a[alg].q;
Merge(aa,b);
k--;
}
alg++;
}
cout<<ans<<endl;
}
return 0;
}
void Merge(int r,int t)
{
int i;
for(i=1;i<=n;i++)
{
if(zz[i]==t)
{
zz[i]=r;
}
}
}
bool bj(const jg &u,const jg &v)
{
return u.q<v.q;
}
不同條件下的最小生成樹
Description
課堂上我們學習了最小生成樹的演算法思想，也在實驗課自己動手實現了這個演算法，今天我們仍然要求來實現這個演算法，只不過輸入要求不一樣，而且給定的圖也不是所有頂點之間都有連線的邊，有些頂點之間沒有邊，要求計算的最小費用也有點變化，請準確理解並求解.
Input
輸入的第一行是測試數據的組數，對於每一組測試數據，有兩部分，第一部分只有一行，分別有兩個正整數nNode、nEdge（分別表示圖的頂點數、邊數，其中頂點編號爲1到nNode，1<=nNode<=100）；第二部分共有nEdge行，每行有四個正整數nFrom、nTo、nDist、nV（分別表示這一條邊的起始頂點、終止頂點、邊的長度、這條邊上能夠承載的速度，當然它們的單位已經換算成相應的標準單位了，你不用考慮單位換算的問題；其中1<=nFrom，nTo<=nNode）。輸入數據保證能夠有生成樹，每條邊在計算費用時假設是各自的勻速運動。
Output
你的任務是以每條邊上能承載的速度前提下將所需時間作爲邊的費用，求出最小生成樹的花費，輸出只有一行，即所求的花費，輸出時保留一位小數。
Sample Input
1
6 10
1 2 6 3
1 3 1 1
1 4 5 2
2 3 5 3
2 5 3 2
3 4 5 3
3 5 6 3
3 6 4 2
4 6 2 1
5 6 6 3
Sample Output
7.8
#include<bits/stdc++.h>
using namespace std;
struct jg{
int x,y,q,v;
};
jg a[5003];
int zz[101];
int n,e;
void Merge(int r,int t);
bool bj(const jg &u,const jg &x);
int main()
{
int aa,b,alg,k,i,j,jpii,kk;
double ans;
cin>>jpii;
for(kk=1;kk<=jpii;kk++)
{
cin>>n>>e;
for(i=1;i<=n;i++)
{
zz[i]=i;
}
for(i=1;i<=e;i++)
{
cin>>a[i].x>>a[i].y>>a[i].q>>a[i].v;
}
sort(a+1,a+e+1,bj);
ans=0.0;
k=n;
alg=1;
while(k>1)
{
aa=zz[a[alg].x];
b=zz[a[alg].y];
if(aa!=b)
{
ans+=(1.0*a[alg].q)/(1.0*a[alg].v);
Merge(aa,b);
k--;
}
alg++;
}
printf("%.1lf\n",ans);
}
return 0;
}
void Merge(int r,int t)
{
int i;
for(i=1;i<=e;i++)
{
if(zz[i]==t)
{
zz[i]=r;
}
}
}
bool bj(const jg &u,const jg &x)
{
return (1.0*u.q)/(1.0*u.v)<(1.0*x.q)/(1.0*x.v);
}