並查集最常用來判斷圖是否為連通圖，或用來求圖的連通分量數。 並查集1--<=>求連通分量個數 題目描述 某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目標是使全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可 ...
並查集最常用來判斷圖是否為連通圖，或用來求圖的連通分量數。
並查集1--<=>求連通分量個數
題目描述
某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目標是使全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設多少條道路？輸入描述:
測試輸入包含若幹測試用例。每個測試用例的第1行給出兩個正整數，分別是城鎮數目N ( < 1000 )和道路數目M；隨後的M行對應M條道路，每行給出一對正整數，分別是該條道路直接連通的兩個城鎮的編號。為簡單起見，城鎮從1到N編號。 註意:兩個城市之間可以有多條道路相通,也就是說 3 3 1 2 1 2 2 1 這種輸入也是合法的 當N為0時，輸入結束，該用例不被處理。
輸出描述:
對每個測試用例，在1行里輸出最少還需要建設的道路數目。
輸入
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0
輸出
1 0 2 998
1 #include<bits/stdc++.h> 2 using namespace std; 3 int father[1005]; 4 int height[1005]; 5 void Initial(int n){//初始化 6 for(int i=0;i<n;i++){ 7 father[i]=i; 8 height[i]=0; 9 } 10 } 11 int Find(int x){//路徑壓縮 12 if(x!=father[x]) father[x]=Find(father[x]); 13 return father[x]; 14 } 15 void Union(int x,int y){//合併----實際上為了使得查找效率更高 可以讓高度較低的樹 作為高度較高的樹的子樹來合併。 16 x=Find(x); 17 y=Find(y); 18 if(x!=y) father[x]=y; 19 } 20 int main(){ 21 int n,m; 22 while(cin>>n>>m){ 23 Initial(n); 24 for(int i=0;i<m;i++){ 25 int x,y; 26 cin>>x>>y; 27 Union(x,y); 28 } 29 int ans=0; 30 for(int i=0;i<m;i++){ 31 if(Find(i)==i) ans++;//如果根就是自己，代表了一個連通分量。 32 } 33 cout<<ans-1<<endl; 34 } 35 return 0; 36 }
並查集2---<=>判斷圖是否連通
題目描述
給定一個無向圖和其中的所有邊，判斷這個圖是否所有頂點都是連通的。
輸入描述:
每組數據的第一行是兩個整數 n 和 m（0<=n<=1000）。n 表示圖的頂點數目，m 表示圖中邊的數目。隨後有 m 行數據，每行有兩個值 x 和 y（0<x, y <=n），表示頂點 x 和 y 相連，頂點的編號從 1 開始計算。輸入不保證這些邊是否重覆。
輸出描述:
對於每組輸入數據，如果所有頂點都是連通的，輸出"YES"，否則輸出"NO"。示例1
輸入
複製4 3 1 2 2 3 3 2 3 2 1 2 2 3 0 0
輸出
複製NO YES
思路：計算圖的連通分量 個數，如果為1，那說明是圖，否則不是圖，輸出NO。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int father[1000]; 4 int height[1000]; 5 void Initial(int n){ 6 for(int i=0;i<n;i++){ 7 father[i]=i; 8 height[i]=0; 9 } 10 } 11 int Find(int x){ 12 if(x!=father[x]) 13 father[x]=Find(father[x]); 14 return father[x]; 15 } 16 void Union(int x,int y){ 17 x=Find(x); 18 y=Find(y); 19 if(x!=y) 20 father[x]=y; 21 } 22 int main(){ 23 int n,m; 24 while(cin>>n>>m){ 25 if(n==0&&m==0) break; 26 Initial(n); 27 while(m--){ 28 int x,y; 29 cin>>x>>y; 30 Union(x,y); 31 } 32 int cnt=0; 33 for(int i=0;i<n;i++){ 34 if(Find(i)==i) cnt++; 35 } 36 if(cnt==1) cout<<"YES"<<endl; 37 else cout<<"NO"<<endl; 38 } 39 return 0; 40 }
並查集3---<=>判斷是否是一棵樹
判斷是否為樹的方法：1、這個圖是連通的，即連通分量個數=1, 2、根節點入度=0，其他節點入度=1.
題目描述
A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties. There is exactly one node, called the root, to which no directed edges point. Every node except the root has exactly one edge pointing to it. There is a unique sequence of directed edges from the root to each node. For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.
輸入描述:
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero and less than 10000.
輸出描述:
For each test case display the line "Case k is a tree." or the line "Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).示例1
輸入
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0
3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
輸出
Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.
1 #include<bits/stdc++.h> 2 using namespace std; 3 int father[1000]; 4 int height[1000]; 5 int inD[1000];//入度數組 6 bool visit[1000]; 7 void Initial(){ 8 for(int i=0;i<1000;i++){ 9 father[i]=i; 10 height[i]=0; 11 inD[i]=0; 12 visit[i]=false; 13 } 14 } 15 int Find(int x){ 16 if(x!=father[x]) father[x]=Find(father[x]); 17 return father[x]; 18 } 19 void Union(int x,int y){ 20 x=Find(x); 21 y=Find(y); 22 if(x!=y) father[x]=y; 23 } 24 bool isTree(){ 25 bool flag=true; 26 int cnt=0,root=0; 27 for(int i=0;i<1000;i++){ 28 if(visit[i]==false) continue; 29 if(Find(i)==i) cnt++; 30 if(inD[i]==0) root++; 31 if(inD[i]>1) flag=false; 32 } 33 if((cnt!=1)||root!=1) flag=false;//不連通、根的入度！=0、其他節點入度>1 都不是樹 34 if(cnt==0&&root==0) flag=true;//空樹也是樹！ 35 return flag; 36 } 37 int main(){ 38 int x,y; 39 int num=1; 40 Initial();//初始化 41 while(cin>>x>>y){ 42 if(x==-1&&y==-1) break; 43 if(x==0&&y==0){ 44 if(isTree()) cout<<"Case "<<num++<<" is a tree."<<endl; 45 else cout<<"Case "<<num++<<" is not a tree."<<endl; 46 Initial();//每次結束之後都要初始化 47 }else{ 48 Union(x,y); 49 inD[y]++;//入度增加 50 visit[x]=true,visit[y]=true;//標記以訪問 51 } 52 } 53 return 0; 54 }
最小生成樹1--kruskal演算法（每次選擇權值最小的，如果沒有被。。那就加入~）
題目描述
省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。現得到城鎮道路統計表，表中列出了任意兩城鎮間修建道路的費用，以及該道路是否已經修通的狀態。現請你編寫程式，計算出全省暢通需要的最低成本。輸入描述:
測試輸入包含若幹測試用例。每個測試用例的第1行給出村莊數目N ( 1< N < 100 )；隨後的 N(N-1)/2 行對應村莊間道路的成本及修建狀態，每行給4個正整數，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態：1表示已建，0表示未建。 當N為0時輸入結束。
輸出描述:
每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。示例1
輸入
複製3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0
輸出
複製3 1 0
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct edge{ 4 int from; 5 int to; 6 int cost; 7 int status; 8 }; 9 edge a[10000]; 10 int father[100]; 11 int height[100]; 12 bool cmp(edge x,edge y){//kruskal演算法按邊權值從小到大排序 13 return x.cost<y.cost; 14 }; 15 void Initial(int n){ 16 for(int i=0;i<n;i++){ 17 father[i]=i; 18 height[i]=0; 19 } 20 } 21 int Find(int x){ 22 if(x!=father[x]) father[x]=Find(father[x]); 23 return father[x]; 24 } 25 void Union(int x,int y){ 26 if(Find(x)!=Find(y)){ 27 father[Find(x)]=Find(y); 28 } 29 } 30 int main(){ 31 int n; 32 while(cin>>n&&n!=0){ 33 Initial(n);//初始化 34 int ans=0,num=(n-1)*n/2; 35 for(int i=0;i<num;i++){ 36 cin>>a[i].from>>a[i].to>>a[i].cost>>a[i].status; 37 if(a[i].status==1) a[i].cost=0;//表示已經有的道路。 38 } 39 sort(a,a+num,cmp);//按權值排序 40 for(int i=0;i<num;i++){//kruskal 演算法 41 if(Find(a[i].from)!=Find(a[i].to)){//如果沒有 就加入 42 Union(a[i].from,a[i].to); 43 ans+=a[i].cost; 44 } 45 } 46 cout<<ans<<endl; 47 } 48 return 0; 49 }
最小生成樹2---kruskal演算法
題目描述
In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.輸入描述:
The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.
輸出描述:
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.示例1
輸入
複製3 1.0 1.0 2.0 2.0 2.0 4.0
輸出
複製3.41
本題與上題最大的不同在於要先將坐標轉換成邊的信息。
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Edge{ 4 int from; 5 int to; 6 float len; 7 }; 8 struct Point{ 9 float x; 10 float y; 11 }; 12 int father[105]; 13 int height[100]; 14 Edge edge[10000]; 15 Point point[105]; 16 void Initial(int n){ 17 for(int i=0;i<n;i++){ 18 father[i]=i; 19 height[i]=0; 20 } 21 } 22 int Find(int x){ 23 if(x!=father[x]) father[x]=Find(father[x]); 24 return father[x]; 25 } 26 void Union(int x,int y){ 27 x=Find(x); 28 y=Find(y); 29 if(x!=y){ 30 father[x]=y; 31 } 32 } 33 bool cmp(Edge x,Edge y){ 34 return x.len<y.len; 35 } 36 int main(){ 37 int n; 38 while(cin>>n){ 39 Initial(n); 40 // int num=(n-1)-n/2; 41 for(int i=0;i<n;i++){ 42 cin>>point[i].x>>point[i].y; 43 } 44 int num=0; 45 for(int i=0;i<n;i++){ 46 for(int j=i+1;j<n;j++){ 47 int s1=pow(point[i].x-point[j].x,2); 48 int s2=pow(point[i].y-point[j].y,2); 49 float ss=sqrt(s1+s2); 50 edge[num].from=i; 51 edge[num].to=j; 52 edge[num].len=ss; 53 num++;//邊的個數 54 } 55 }//初始化 邊： 56 sort(edge,edge+num,cmp);//按邊的長度大小排序。 57 float sum=0; 58 for(int i=0;i<num;i++){ 59 if(Find(edge[i].from)!=Find(edge[i].to)){ 60 Union(edge[i].from,edge[i].to); 61 sum+=edge[i].len; 62 } 63 } 64 cout<<fixed<<setprecision(2)<<sum<<endl; 65 } 66 return 0; 67 }
最小生成樹3
題目描述
The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.（ps:如果不是連通圖的話，最後的結果輸出不用包含不在連通圖裡的那些點）
輸入描述:
The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.
輸出描述:
The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.示例1
輸入
複製9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0
輸出
複製216 30
本題需要將輸入中的 信息轉化
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct edge{ 4 int from; 5 int to; 6 int len; 7 }; 8 edge a[1000]; 9 int father[30]; 10 int height[30]; 11 void Initial(int n){ 12 for(int i=0;i<n;i++){ 13 father[i]=i; 14 height[i]=0; 15 } 16 } 17 int Find(int x){ 18 if(x!=father[x]) father[x]=Find(father[x]); 19 return father[x]; 20 } 21 void Union(int x,int y){ 22 x=Find(x); 23 y=Find(y); 24 if(x!=y) father[x]=y; 25 } 26 bool cmp(edge x, edge y){ 27 return x.len<y.len; 28 } 29 int main(){ 30 int n; 31 while(cin>>n&&n!=0){ 32 Initial(n); 33 int num=0,cnt=0; 34 for(int i=0;i<n-1;i++){ 35 char from; 36 int m; 37 cin>>from>>m; 38 num+=m;//num為邊的個數--- 39 while(m--){ 40 char to; 41 int x; 42 cin>>to>>x; 43 a[cnt].from=from-'A'; 44 a[cnt].to=to-'A'; 45 a[cnt].len=x; 46 cnt++; 47 } 48 } 49 int sum=0; 50 sort(a,a+num,cmp);//邊按權值大小排序 51 for(int i=0;i<num;i++){ 52 if(Find(a[i].from)!=Find(a[i].to)){// 53 Union(a[i].from,a[i].to); 54 sum+=a[i].len; 55 } 56 } 57 cout<<sum<<endl; 58 } 59 return 0; 60 }
最小生成樹總結：依然是並查集的板子，但是需要對所有邊的權值按從小到大的順序排序，如果之前未被合併過，那就合併（kruskal演算法），有時需要將坐標、字母等轉化成邊的信息（起點、終點、權值）。
最短路徑問題1
最短路徑問題主要兩種演算法：Dijkstra演算法與Floyd演算法
1、Dijkstra演算法：適合單源最短路徑問題，
2、Floyd演算法：多源最短路徑。思路簡單。但是機試要求頂點個數<100/200，否則會超時。
Dijkstra演算法1
題目描述
給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。
輸入描述:
輸入n,m，點的編號是1~n,然後是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最後一行是兩個數 s,t;起點s，終點t。n和m為0時輸入結束。 (1<n<=1000, 0<m<100000, s != t)
輸出描述:
輸出 一行有兩個數， 最短距離及其花費。示例1
輸入
複製3 2 1 2 5 6 2 3 4 5 1 3 0 0
輸出
複製9 11
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Edge{ 4 int to; 5 int len; 6 int cost; 7 Edge(int t,int l,int c):to(t),len(l),cost(c){} 8 }; 9 struct Point{ 10 int num; 11 int distance; 12 Point(int n,int d):num(n),distance(d){} 13 bool operator<(const Point &c)const{ 14 return distance>c.distance;//與sort反著的。因為優先隊列 int型預設數越大優先順序越高。 15 } 16 }; 17 vector<Edge>graph[100000];//鄰接表建立圖 18 int dis[1005];//存儲最短路徑 19 int cost[1005]; 20 void dij(int s){ 21 priority_queue<Point>my;//按照距離越小優先順序越高來建立優先隊列。 22 dis[s]=0,cost[s]=0;//初始化 23 my.push(Point(s,dis[s]));//壓入初始點 24 //開始遍歷整個圖 25 while(!my.empty()){ 26 int u=my.top().num;//每次選擇離源點最近的點 27 my.pop();//**** 28 for(int i=0;i<graph[u].size();i++){//直到遍歷完鄰接表中所有節點。 29 int v=graph[u][i].to; 30 i
