題目描述

約翰農場的牛群希望能夠在 N 個(1<=N<=200) 草地之間任意移動。草地的編號由 1到 N。草地之間有樹林隔開。牛群希望能夠選擇草地間的路徑，使牛群能夠從任一 片草地移動到任一片其它草地。 牛群可在路徑上雙向通行。

牛群并不能創(chuàng)造路徑，但是他們會保有及利用已經發(fā)現(xiàn)的野獸所走出來的路徑(以 下簡稱獸徑)。每星期他們會選擇并管理一些或全部已知的獸徑當作通路。

牛群每星期初會發(fā)現(xiàn)一條新的獸徑。他們接著必須決定管理哪些獸徑來組成該周牛 群移動的通路，使得牛群得以從任一草地移動到任一草地。牛群只能使用當周有被 管理的獸徑做為通路。

牛群希望他們管理的獸徑長度和為最小。牛群可以從所有他們知道的所有獸徑中挑 選出一些來管理。牛群可以挑選的獸徑與它之前是否曾被管理無關。

獸徑決不會是直線，因此連接兩片草地之間的不同獸徑長度可以不同。 此外雖然 兩條獸徑或許會相交，但牛群非常的專注，除非交點是在草地內，否則不會在交點 換到另外一條獸徑上。

在每周開始的時候，牛群會描述他們新發(fā)現(xiàn)的獸徑。如果可能的話，請找出可從任 何一草地通達另一草地的一組需管理的獸徑，使其獸徑長度和最小。

輸入輸出格式

輸入格式：

?

輸入的第一行包含兩個用空白分開的整數(shù) N 和 W。W 代表你的程序需要處理 的周數(shù). (1 <= W <= 6000)。

以下每處理一周，讀入一行數(shù)據，代表該周新發(fā)現(xiàn)的獸徑，由三個以空白分開 的整數(shù)分別代表該獸徑的兩個端點 (兩片草地的編號) 與該獸徑的長度(1…10000)。一條獸徑的兩個端點一定不同。

?

輸出格式：

?

每次讀入新發(fā)現(xiàn)的獸徑后，你的程序必須立刻輸出一組獸徑的長度和，此組獸徑可從任何一草地通達另一草地，并使獸徑長度和最小。如果不能找到一組可從任一草地通達另一草地的獸徑，則輸出 “-1”。

?

輸入輸出樣例

輸入樣例#1：
4 6 1 2 10 1 3 8 3 2 3 1 4 3 1 3 6 2 1 2 輸出樣例#1：
-1 //No trail connects 4 to the rest of the fields. -1 //No trail connects 4 to the rest of the fields. -1 //No trail connects 4 to the rest of the fields. 14 //Maintain 1 4 3, 1 3 8, and 3 2 3. 12 //Maintain 1 4 3, 1 3 6, and 3 2 3. 8 //Maintain 1 4 3, 2 1 2, and 3 2 3. //program exit

最小生成樹+插入排序
所謂插入排序

點擊進入插入排序學習網站
屠龍寶刀點擊就送

#include <algorithm> #include <cstdio>#define Max 200 #define syl main using namespace std;struct node {int x,y,z; }edge[Max*Max*7]; int cnt,i,j,fa[Max*7],n,w; void add(int u,int v,int l) {node*now=&edge[++cnt];now->x=u;now->y=v;now->z=l; } bool cmp(node a,node b) {return a.z<b.z; } int find_fa(int k) {return fa[k]==k?k:fa[k]=find_fa(fa[k]); } int kruskal() {for(int i=1;i<=n;++i) fa[i]=i;int ans=0,k=0;for(int i=1;i<=cnt;++i){int fx=find_fa(edge[i].x),fy=find_fa(edge[i].y);if(fx!=fy){k++;fa[fy]=fx;ans+=edge[i].z;if(k==n-1) return ans;}}return -1; } void qr(int &x) {x=0;bool f=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(int)ch-48;ch=getchar();}x=f?(~x)+1:x; } void InsertSort(int size) {int i,j,key,fr,t;for(i=1;i<size;++i){key=edge[i].z;fr=edge[i].x;t=edge[i].y;for(j=i-1;j>=1;--j){if(edge[j].z>key) {edge[j+1].z=edge[j].z;edge[j+1].x=edge[j].x;edge[j+1].y=edge[j].y;}else break;}edge[j+1].z=key;edge[j+1].x=fr;edge[j+1].y=t;} } int syl() {qr(n);qr(w);for(int x,y,z;w--;){qr(x);qr(y);qr(z);add(x,y,z);InsertSort(cnt+1);printf("%d\n",kruskal());}return 0; }

?

轉載于:https://www.cnblogs.com/ruojisun/p/6575097.html

總結

以上是生活随笔為你收集整理的洛谷 P1340 兽径管理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。