CodeForces 125E MST Company

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

There are n cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly k capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

Input

The first input line contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), where n is the number of cities in the country, m is the number of roads in the country, k is the number of capital roads in the required set. Then m lines enumerate the roads in question. Each road is specified by three numbers ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), where ai, bi are the numbers of cities linked by a road and wi is its length.

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

Output

In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

Examples

input

output

3
1 5 2

代码基本靠抄，自己吃枣药丸。

传说这题做法主要有两种：

一：

　　先做出不含1点的最小生成树。

　　如果将连接到1的边加进生成树会形成环的话，就在环中找到最长的一条边删掉。

　　↑计算加某条边会使答案增加的量，然后从连接到1的边里选出增量最小的边进行上述操作，重复k次得到最终结果。

　　↑写了好久好久都写不出，怒砸键盘，换第二种写法。结果第二天看到隔壁yhx大神分分钟按上述算法切题……

　　害怕。

　　附传送门：http://blog.csdn.net/sdfzyhx/article/details/53500851

　　还有自己写了半天调不对的代码，姑且先存着：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 #define LL unsigned long long
  7 using namespace std;
  8 const int mxn=5010;
  9 int read(){
 10     int x=0,f=1;char ch=getchar();
 11     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 struct edge{int x,y;int v;int id;}e[mxn*10];
 16 int cmp(const edge a,const edge b){return a.v<b.v;}
 17 struct sdd{int v,nxt,dis,id;}eg[mxn<<2];
 18 int hd[mxn],egct=0;
 19 void add_edge(int u,int v,int dis,int id){
 20     eg[++egct].v=v;eg[egct].nxt=hd[u];eg[egct].dis=dis;eg[egct].id=id;hd[u]=egct;return;
 21 }
 22 int n,m,k;
 23 int ans=0;
 24 int st[mxn],top;
 25 int fir[mxn*10],mct=0;//存所有与1相连的边 
 26 //
 27 int fa[mxn];
 28 int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);}
 29 int add[mxn];
 30 bool del[mxn];
 31 bool intree[mxn];
 32 inline void init(int x){for(register int i=1;i<=x;i++)fa[i]=i;}//并查集初始化 
 33 void PD(){
 34     int cnt=0;
 35     for(int i=2;i<=n;i++){if(find(i)==i)cnt++;}
 36     if(cnt>k){printf("-1
");exit(0);}//联通块数多于可加边数，无解 
 37     return;
 38 }
 39 int mx[mxn],m_id[mxn];
 40 void DFS(int u,int f){
 41     for(int i=hd[u];i;i=eg[i].nxt){
 42         int v=eg[i].v;
 43         if(v==f || !intree[eg[i].id])continue;
 44         if(u==1){mx[v]=1e9;m_id[v]=0;}
 45         bool flag=0;
 46         if(eg[i].dis<mx[v]){
 47             mx[v]=eg[i].dis;
 48             m_id[v]=eg[i].id;
 49             flag=1;
 50         }
 51         if(mx[v]>mx[u]){
 52             mx[v]=mx[u];
 53             m_id[v]=m_id[u];
 54             flag=1;
 55         }
 56         if(flag)DFS(v,u);
 57     }
 58     return;
 59 }
 60 int belone[mxn];
 61 void solve(){
 62     top=0;
 63     int i,j,u,v;
 64     int cnt=0;
 65     //
 66     sort(e+1,e+m+1,cmp);
 67     init(n);
 68     for(i=1;i<=m;i++){
 69         if(e[i].x==1 || e[i].y==1)continue;
 70         u=find(e[i].x);v=find(e[i].y);
 71         if(u!=v){
 72             fa[u]=v;
 73             ans+=e[i].v;
 74             intree[e[i].id]=1;//记录是否在树中
 75             add_edge(e[i].x,e[i].y,e[i].v,e[i].id);
 76             add_edge(e[i].y,e[i].x,e[i].v,e[i].id);
 77             cnt++;
 78         }
 79         if(cnt==n-2)break;//除1以外都连通时，退出 
 80     }
 81     //kruskal处理出除点1以外的生成树 
 82     PD();
 83     //
 84     init(n);
 85     for(i=2;i<=n;i++){belone[i]=find(i);}
 86     for(i=1;i<=m;i++)//找出待加的1边 
 87         if(e[i].x==1 || e[i].y==1){
 88             if(e[i].y==1)swap(e[i].x,e[i].y);
 89             fir[++mct]=i;
 90         }
 91     memset(mx,0x3f,sizeof mx);
 92     for(i=1;i<=mct;i++){
 93         if(e[fir[i]].v<mx[belone[e[fir[i]].y]]){
 94             mx[belone[e[fir[i]].y]]=e[fir[i]].v;
 95             m_id[belone[i]]=fir[i];
 96         }
 97     }
 98     cnt=0;
 99     for(i=1;i<=n;i++){//加入和点1相连的边使图连通 
100         if(belone[i]!=i)continue;
101         intree[e[m_id[i]].id]=1;
102         cnt++;
103         ans+=e[m_id[i]].v;
104         add_edge(e[m_id[i]].x,e[m_id[i]].y,e[m_id[i]].v,e[m_id[i]].id);
105         add_edge(e[m_id[i]].y,e[m_id[i]].x,e[m_id[i]].v,e[m_id[i]].id);
106     }
107     for(i=cnt+1;i<=k;i++){
108         DFS(1,0);
109         int tmp1=1e9,tmp2,tmp3;
110         for(j=1;j<=mct;j++){//尝试替换1边 
111             int to=e[fir[j]].y;
112             if(e[fir[j]].v-mx[to]<tmp1){
113                 tmp1=e[fir[j]].v+mx[to];
114                 tmp2=fir[j];
115                 tmp3=m_id[to];
116             }
117             ans+=tmp1;
118             intree[e[tmp2].id]=1;//加入1边 
119             intree[e[tmp3].id]=0;//删除一条边 
120         }
121     }
122     return;
123 }
124 int main()
125 {
126     int i,j;
127     n=read();m=read();k=read();
128     for(i=1;i<=m;i++){
129         e[i].x=read();e[i].y=read();
130         e[i].v=read();e[i].id=i;
131         fa[find(e[i].x)]=fa[find(e[i].y)];
132     }
133     for(i=1;i<n;i++)if(find(i)!=find(i+1)){
134         printf("-1
");return 0;
135     }//无法连通，无解 
136     solve();
137     printf("%d
",ans);
138     return 0;
139 }

View Code

二：

　　加边的增量具有单调性。二分可能的增量，以此为基准将与1相连的边排序并加入生成树，看何时能正好加入k条，就是答案了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #define LL unsigned long long
 7 using namespace std;
 8 const double eps=1e-5;
 9 const int mxn=5010;
10 int read(){
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 struct edge{
17     int x,y;
18     int v;
19     int id;
20 }e[mxn*20];
21 double mid;
22 int cmp(const edge a,const edge b){
23     return (double)(a.x==1)*mid+(double)a.v < (double)(b.x==1)*mid+(double)b.v;
24 }
25 int n,m,k;
26 int tot=0;
27 //
28 int fa[mxn];
29 int find(int x){
30     if(fa[x]==x)return fa[x];
31     return fa[x]=find(fa[x]);
32 }
33 int ans[mxn],mct=0;
34 void solve(bool flag){
35     for(int i=1;i<=n;i++)fa[i]=i;
36     sort(e+1,e+m+1,cmp);
37     tot=0;mct=0;
38     for(int i=1;i<=m;i++){
39         int u=find(e[i].x),v=find(e[i].y);
40         if(u!=v && (tot+(e[i].x==1)<=k || flag)){
41             fa[u]=v;
42             ans[++mct]=e[i].id;
43             if(e[i].x==1)tot++;
44         }
45     }
46 }
47 int main()
48 {
49     n=read();m=read();k=read();
50     int i,j;
51     int dg1=0;
52     for(i=1;i<=m;i++){
53         e[i].x=read();e[i].y=read();e[i].v=read();e[i].id=i;
54         if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
55         if(e[i].x==1)dg1++;
56     }
57     if(dg1<k || (n>1 && k==0)){printf("-1
");return 0;}//不能满足k要求 
58     mid=0;
59     solve(1);
60     if(mct<n-1){printf("-1
");return 0;}//不能生成树
61     double l=-1e5,r=1e5;
62     while(l+eps<r && tot!=k){
63         mid=(l+r)/2;
64         solve(1);
65         if(tot<k)r=mid;
66         else l=mid;
67     }
68     if(tot!=k)mid=(l+r)/2;
69     solve(0);
70     printf("%d
",mct);
71     for(i=1;i<=mct;i++)printf("%d ",ans[i]);
72     return 0;
73 }