1083:[SCOI 2005]忙しい都市
10427 ワード
1083:[SCOI 2005]忙しい都市
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1611 Solved: 1040[ Submit ][ Status ][ Discuss ]
Description
都市Cは非常に忙しい大都市で、都市の中の道路は非常に混雑しているので、市長はその中の道路を改造することにした.都市Cの道路はこのように分布しています:都市の中でnつの交差点があって、一部の交差点の間には道路がつながっていて、2つの交差点の間には最大1つの道路がつながっています.これらの道路は双方向で、すべての交差点を直接または間接的に接続しています.各道路にはスコアがあり、スコアが小さいほど、この道路が忙しいほど改造が必要であることを示しています.しかし、市役所の資金は限られており、市長は改造を行う道が少なければ少ないほど良いことを望んでおり、1.改造された道路はすべての交差点を直接または間接的につなぐことができるという要求を出した.2.要求1を満たす場合、改造された道路はできるだけ少なくする.3.要求1、2を満たす場合、改造された道路の中で最も点数の大きい道路の点数はできるだけ小さくする.任務:市計画局のあなたとして、最も良い決定をして、それらの道路が建設されるべきことを選択しなければなりません.
Input
1行目には2つの整数nがあり、mは都市にnつの交差点があり、m本の道路があることを示している.次にm行は各道路についての記述であり、u,v,cは交差点uとvの間に道路が接続されていることを示し、値はcである.(1≤n≤300,1≤c≤10000)
Output
2つの整数s,maxは、あなたがいくつかの道路を選んだことを示しています.点数が最も大きい道路の点数はいくらですか.
Sample Input
4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8
Sample Output
3 6
[ Submit ][ Status ][ Discuss ]
これは最小生成木の問題であり,クルーズカールアルゴリズムで解決できるが,問題は改造を要求する辺ができるだけ少なく,それを1つの木を生成させなければならないので,選択した道路の数はN−1に違いない,第1問で解決する.
2番目の質問では、スコアが最も大きいルートのスコアを取ることが要求されています.クルーズカールの中の集計のみが間違っています.改善する必要があります.スレッドは以下の通りです.
1 //
2 #include<bits/stdc++.h>
3 using namespace std;
4 const int maxn=500;
5 const int inf=1e9;
6 int fa[maxn];
7 int MAX;
8 struct node{
9 int c;
10 int l1,l2;
11 };
12 node edge[250000];
13 int get_fa(int x){
14 if(fa[x]!=x) fa[x]=get_fa(fa[x]);
15 return fa[x];
16 }
17 int cmp(const node&a,const node&b){
18 if(a.c<b.c) return 1;
19 return 0;
20 }
21 int hehe(int x,int y){
22 int r1=get_fa(x);
23 int r2=get_fa(y);
24 if(r1<r2) fa[r2]=r1;
25 else fa[r1]=r2;
26 }
27 int N,M;
28 int u,v,w;
29 int tot;
30 int main(){
31 cin>>N>>M;
32 for(int i=1;i<=M;i++){
33 scanf("%d%d%d",&u,&v,&w);
34 edge[i].l1=u;
35 edge[i].l2=v;
36 edge[i].c=w;
37 }
38 for(int i=1;i<=N;i++) fa[i]=i;
39 sort(edge+1,edge+M+1,cmp);
40
41 for(int i=1;i<=M;i++){
42 int r1=edge[i].l1;
43 int r2=edge[i].l2;
44 if(get_fa(r1)!=get_fa(r2)){
45 hehe(r1,r2);
46 tot++;
47 }
48 if(tot==N-1){
49 MAX=edge[i].c;
50 break;
51 }
52
53 }
54 cout<<(N-1)<<" "<<MAX;
55 return 0;
56 }次はエラーhehe()関数です.
1 int hehe(int x,int y){
2 int r1=get_fa(x);
3 int r2=get_fa(y);
4 fa[r1]=r2;
5 }なぜか、このデータを試してみましょう.
4 61 2 11 3 11 4 12 4 12 3 1003 4 100
正しいのは3 1で、間違っているのは3 100です.なぜなら、最初のステップで1,2ノードをマージさせるとhehehe(1,2)後fa[1]=2,fa[2]=2,後に1,3,hehe(1,3)後fa[1]=3,fa[2]=2,fa[3]=3,,,,,1,2に相当して切れてしまい、問題はここにあり、解決策はノードをすべて小さい父親にすることでACができるからである.