今天刷一下水題練手入門，明天繼續。
poj1861 Network（最小生成樹）新手入門題。
題意：輸出連接方案中最長的單根網線長度（必須使這個值是所有方案中最小的），然后輸出方案。
題解：本題沒有直接求生成樹，但如果連接n個集線器的方案多于n-1條邊，那么必存在回路，因此去掉某些邊剩下的邊和所有頂點構成一個生成樹。對于一個圖的最小生成樹來說，它的最大邊滿足所有生成樹的最大邊里最小，正和題意。
吐槽：題目樣例是錯的。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1001; 6 struct edge{ 7 int u,v,w; 8 }e[15001]; 9 int f[N],a[N],ai; 10 int n,m,ma; 11 int cmp(edge a,edge b){ 12 return a.w<b.w; 13 } 14 void init(){ 15 for(int i=1;i<=n;++i) 16 f[i]=i; 17 } 18 int fin(int x){ 19 if(x!=f[x])f[x]=fin(f[x]); 20 return f[x]; 21 } 22 void Kruskal(){ 23 ma=ai=0; 24 int u,v,i; 25 init(); 26 for(i=0;i<m;++i){ 27 u=e[i].u; 28 v=e[i].v; 29 if((u=fin(u))!=(v=fin(v))){ 30 f[u]=v; 31 a[ai++]=i; 32 ma=max(e[i].w,ma); 33 } 34 if(ai>=n-1)break; 35 } 36 } 37 int main(){ 38 int i,u,v,w; 39 scanf("%d%d",&n,&m); 40 for(i=0;i<m;++i){ 41 scanf("%d%d%d",&u,&v,&w); 42 e[i]=edge{u,v,w}; 43 } 44 sort(e,e+m,cmp); 45 Kruskal(); 46 printf("%d\n%d\n",ma,ai); 47 for(i=0;i<ai;++i) 48 printf("%d %d\n",e[a[i]].u,e[a[i]].v); 49 return 0; 50 }
?
poj1251 Jungle Roads（最小生成樹）水題。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=27; 6 struct edge{ 7 int u,v,w; 8 }e[75]; 9 int f[N]; 10 int n,m,ans; 11 int cmp(edge a,edge b){ 12 return a.w<b.w; 13 } 14 void init(){ 15 for(int i=0;i<n;++i) 16 f[i]=i; 17 } 18 int fin(int x){ 19 if(x!=f[x])f[x]=fin(f[x]); 20 return f[x]; 21 } 22 void Kruskal(){ 23 ans=0; 24 int u,v,i; 25 init(); 26 for(i=0;i<m;++i){ 27 u=e[i].u; 28 v=e[i].v; 29 if((u=fin(u))!=(v=fin(v))){ 30 f[u]=v; 31 ans+=e[i].w; 32 } 33 } 34 } 35 int main(){ 36 int i,j,w,k; 37 char u[3],v[3]; 38 while(scanf("%d",&n),n){ 39 m=0; 40 for(i=0;i<n-1;++i){ 41 scanf("%s %d",u,&k); 42 for(j=0;j<k;++j){ 43 scanf("%s %d",v,&w); 44 e[m++]={u[0]-'A',v[0]-'A',w}; 45 } 46 } 47 sort(e,e+m,cmp); 48 Kruskal(); 49 printf("%d\n",ans); 50 } 51 return 0; 52 }
?
poj1287 Networking（最小生成樹）水題。
用prim要注意兩個地點之間的線路可能多條，即有重邊。我這里練的是Kruskal，題目沒給邊數，但知道點數最多50，則邊數最多50*49/2=1225條，有重邊，開大點數組就行，因為數據弱，隨便開個1500都過了，醉。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int M=1500; 6 struct edge{ 7 int u,v,w; 8 }e[M]; 9 int f[50]; 10 int n,m,ans; 11 int cmp(edge a,edge b){ 12 return a.w<b.w; 13 } 14 void init(){ 15 for(int i=1;i<=n;++i) 16 f[i]=i; 17 } 18 int fin(int x){ 19 if(x!=f[x])f[x]=fin(f[x]); 20 return f[x]; 21 } 22 void Kruskal(){ 23 ans=0; 24 int u,v,i; 25 init(); 26 for(i=0;i<m;++i){ 27 u=e[i].u; 28 v=e[i].v; 29 if((u=fin(u))!=(v=fin(v))){ 30 f[u]=v; 31 ans+=e[i].w; 32 } 33 } 34 } 35 int main(){ 36 int i,u,v,w; 37 while(scanf("%d",&n),n){ 38 scanf("%d",&m); 39 for(i=0;i<m;++i){ 40 scanf("%d%d%d",&u,&v,&w); 41 e[i]={u,v,w}; 42 } 43 sort(e,e+m,cmp); 44 Kruskal(); 45 printf("%d\n",ans); 46 } 47 return 0; 48 }
?
poj2031 Building a Space Station（最小生成樹）題目看老久，其實挺水…空間站存在一些球形單間，如果單間之間接觸，重疊或用走廊連接則連通。給出單間坐標和半徑，求要使得所有單間相連通的走廊總長度的最小值。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const int M=5000; 7 const int N=100; 8 struct edge{ 9 int u,v; 10 double w; 11 }e[M]; 12 double a[N],b[N],c[N],r[N]; 13 int f[N]; 14 int n,m; 15 double ans; 16 int cmp(edge a,edge b){ 17 return a.w<b.w; 18 } 19 double dist(int i,int j){ 20 return sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(c[i]-c[j])*(c[i]-c[j]))-r[i]-r[j]; 21 } 22 void init(){ 23 for(int i=0;i<n;++i) f[i]=i; 24 } 25 int fin(int x){ 26 if(x!=f[x])f[x]=fin(f[x]); 27 return f[x]; 28 } 29 void Kruskal(){ 30 ans=0; 31 int u,v,i,cnt=0; 32 init(); 33 for(i=0;cnt<n-1;++i){ 34 u=e[i].u; 35 v=e[i].v; 36 if((u=fin(u))!=(v=fin(v))){ 37 f[u]=v; 38 ans+=e[i].w; 39 cnt++; 40 } 41 } 42 } 43 int main(){ 44 int i,j; 45 double w; 46 while(scanf("%d",&n),n){ 47 for(i=0;i<n;++i){ 48 scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&r[i]); 49 } 50 for(m=i=0;i<n-1;++i){ 51 for(j=i+1;j<n;++j){ 52 w=dist(i,j); 53 if(w<0) w=0; 54 e[m++]={i,j,w}; 55 } 56 } 57 sort(e,e+m,cmp); 58 Kruskal(); 59 printf("%.3f\n",ans); 60 } 61 return 0; 62 }
?
poj2421 Constructing Roads（最小生成樹）水題。有些點已經連邊，進行標記，加邊時將其邊賦值為0即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int M=5000; 6 const int N=101; 7 struct edge{ 8 int u,v,w; 9 }e[M]; 10 int f[N]; 11 int g[N][N],vis[N][N]; 12 int n,ans; 13 int cmp(edge a,edge b){ 14 return a.w<b.w; 15 } 16 void init(){ 17 for(int i=1;i<=n;++i) f[i]=i; 18 } 19 int fin(int x){ 20 if(x!=f[x])f[x]=fin(f[x]); 21 return f[x]; 22 } 23 void Kruskal(){ 24 ans=0; 25 int u,v,i,cnt=0; 26 init(); 27 for(i=0;cnt<n-1;++i){ 28 u=e[i].u; 29 v=e[i].v; 30 if((u=fin(u))!=(v=fin(v))){ 31 f[u]=v; 32 ans+=e[i].w; 33 cnt++; 34 } 35 } 36 } 37 int main(){ 38 int i,j,a,b,ei,m; 39 while(scanf("%d",&n)==1){ 40 for(i=1;i<=n;++i) 41 for(j=1;j<=n;++j) 42 scanf("%d",&g[i][j]); 43 memset(vis,0,sizeof(vis)); 44 scanf("%d",&m); 45 while(m--){ 46 scanf("%d%d",&a,&b); 47 vis[a][b]=1; 48 } 49 ei=0; 50 for(i=1;i<n;++i){ 51 for(j=i+1;j<=n;++j){ 52 if(vis[i][j]) e[ei++]={i,j,0}; 53 else e[ei++]={i,j,g[i][j]}; 54 } 55 } 56 sort(e,e+ei,cmp); 57 Kruskal(); 58 printf("%d\n",ans); 59 } 60 return 0; 61 }
?
