Codeforces 125E MST Company (单度限制最小生成树)

E. MST Company

time limit pertest 8 seconds

memory limit pertest 256 megabytes

input standardinput

output standardoutput

The MST(Meaningless State Team) company won another tender for an important statereform in Berland.

There are n cities inBerland, some pairs of the cities are connected by roads. Each road has itsprice. One can move along any road in any direction. The MST team should carryout the repair works on some set of roads such that one can get from any cityto any other one moving only along the repaired roads. Moreover, this setshould contain exactly k capitalroads (that is, the roads that start or finish in the capital). The number ofthe capital is 1.

As the budgethas already been approved, the MST Company will profit by finding the set withminimum lengths of roads.

Input

The first inputline contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 10⁵;0 ≤ k < 5000), where n is thenumber of cities in the country, m is thenumber of roads in the country, k is thenumber of capital roads in the required set. Then m linesenumerate the roads in question. Each road is specified by three numbers a_i, b_i, w_i (1 ≤ a_i, b_i ≤ n; 1 ≤ w ≤ 10⁵), where a_i, b_i are thenumbers of cities linked by a road and w_i is itslength.

Between eachpair of cities no more than one road exists. There are no roads that start andfinish in one city. The capital's number is 1.

Output

In the firstline print the number of roads in the required set. The second line shouldcontain the numbers of roads included in the sought set. If the sought set doesnot exist, print -1.

Examples

input

4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2

output

3
1 5 2 

一看题目有MST，我以为是一道简单的最小生成树的题目。但题目的难度超过了我的想象。

详情请看代码

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<functional> #include<algorithm> #define maxn 50005 #define maxm 100005 using namespace std; int ance[maxn],ans[maxn]; int x[maxm],y[maxm],w[maxm]; int sig[maxm]; int cnt,captedge; int n,m,k; int deg; double l,r,mid; bool cmp(int a,int b)//加权以后排序 { return (w[a]+(x[a]==1)*mid)<(w[b]+(x[b]==1)*mid);//这个算法的核心 }//用Mid调整顺序，最后会得到 权重相同的情况与1相连的边在前面 x【a】相同的情况下权重小的在前面 //如果不是很理解，建议把下面注释去掉，看排序情况 int findance(int x)//并查集操作 { if(ance[x]==x) return x; else return ance[x]=findance(ance[x]); } void Kruskal(bool flag) { cnt=captedge=0; for(int i=1;i<=n;i++) ance[i]=i;//并查集初始化 sort(sig,sig+m,cmp);//排序 for(int i=0;i<m;i++) { if(cnt+1==n) return ; int j=sig[i]; int u=findance(x[j]);//并查集合并准备操作 int v=findance(y[j]); if((u!=v)&&(flag||(captedge+(x[j]==1))<=k))//两种不同的操作策略 //flag=1 普通的Kruskal算法操作，有边可连就连 //flag=0 前部分操作一样，当选够了K条边与1相连的边以后就不再连接与1相连的边 { ance[u]=v; ans[cnt++]=j; if(x[j]==1) captedge++;//统计1的度数 } } } int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF) { deg=0; l=(-1)*100000.0; r=100000.0; mid=0; for(int i=0;i<m;i++) { sig[i]=i;//Sig存储边的编号 scanf("%d%d%d",&x[i],&y[i],&w[i]); if(x[i]>y[i])//存储边的起点和终点 swap(x[i],y[i]);//X存储两者较小的，处理与1相连的边时方便 if(x[i]==1) deg++;//统计与1相连边的度数 } if(deg<k||(n>1&&k==0))//可选边<k必然不可能 {//n>1时1的度数必然>=1, printf("-1\n"); return 0;//不可能满足题意 } cnt=0; Kruskal(1);//普通的跑一边算法 if(cnt!=n-1)//不能构成生成树 { printf("-1\n"); return 0; } while((l+1e-5<r)&&(captedge!=k))//二分权重找答案 { mid=(l+r)/2.0; Kruskal(1); if(captedge<k) r=mid;//减少权重，把与1相连的边前移 else l=mid;//增加权重，把与1相连的边后移 } if(captedge!=k) mid=(l+r)/2.0;//二分即可得到答案 Kruskal(0);//Captedge=K时调整一下答案，!=K的时候就得到答案 printf("%d\n",n-1); if(cnt>=1) printf("%d",ans[0]+1); for(int i=1;i<cnt;i++) printf(" %d",ans[i]+1); printf("\n");//输出格式有点乱，但CF不怎么看输出格式 } }