题意：
给定一个有 n 个点、m 条边的无向带权图，求 1 号点度数为 k 的最小生成树。(n, k <= 5e3, m <= 1e5)
链接：
https://vjudge.net/problem/CodeForces-125E#author=0
解题思路：
度限制最小生成树。先求出除 1 号结点外的最小生成森林，记有 m 个最小生成森林联通块，若 m > k，则无解。否则，贪心地连 m 条边，得到一个初始解。接下来循环 k - m 次，每次让 1 号结点度数增加 1，遍历所有连接 1 号结点的边，若要加入这条边，则必然形成一个环，故需删去此环上的最大边，每次贪心选取增加量最小的边加入最小生成树。此过程可以用 dp 优化找环上最大边，即在最小生成树上 dp 预处理，每次加入新边时再更新。
参考代码：
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
typedef pair
<int, int> pii
;
#define pb push_back
#define sz(a) ((int)a.size())
#define mem(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn
= 5e3 + 5;
const int maxm
= 1e5 + 5;
const int mod
= 1e9 + 7;
const int inf
= 0x3f3f3f3f;
struct Edge
{
int u
, v
, w
, p
;
bool operator < (const Edge
&o
) const{
return w
< o
.w
;
}
} e1
[maxm
], e2
[maxm
], ei
[maxm
];
int G
[maxn
][maxn
], dp
[maxn
];
int pre
[maxn
], vis
[maxm
];
int n
, m
, k
, m1
, m2
;
int fin(int x
){
return x
== pre
[x
] ? x
: pre
[x
] = fin(pre
[x
]);
}
void kruskal(){
sort(e2
+ 1, e2
+ 1 + m2
);
for(int i
= 1; i
<= n
; ++i
) pre
[i
] = i
;
for(int i
= 1; i
<= m2
; ++i
){
int u
= e2
[i
].u
, v
= e2
[i
].v
, p
= e2
[i
].p
;
int x
= fin(u
), y
= fin(v
);
if(x
== y
) continue;
G
[u
][v
] = G
[v
][u
] = p
;
pre
[x
] = y
, vis
[p
] = 1;
}
}
void dfs(int u
, int f
){
for(int i
= 1; i
<= n
; ++i
){
if(!G
[u
][i
] || i
== f
) continue;
dp
[i
] = ei
[G
[u
][i
]].w
> ei
[dp
[u
]].w
? G
[u
][i
] : dp
[u
];
dfs(i
, u
);
}
}
int main(){
scanf("%d%d%d", &n
, &m
, &k
);
m1
= m2
= 0;
for(int i
= 1; i
<= n
; ++i
)
for(int j
= 1; j
<= n
; ++j
) G
[i
][j
] = 0;
for(int i
= 1; i
<= n
; ++i
) vis
[i
] = 0, dp
[i
] = -1;
for(int i
= 1; i
<= m
; ++i
){
int u
, v
, w
; scanf("%d%d%d", &u
, &v
, &w
);
if(u
> v
) swap(u
, v
);
if(u
== 1) e1
[++m1
] = { u
, v
, w
, i
};
else e2
[++m2
] = { u
, v
, w
, i
};
ei
[i
] = { u
, v
, w
, i
};
}
kruskal();
int cnt
= 0;
sort(e1
+ 1, e1
+ 1 + m1
);
for(int i
= 1; i
<= m1
; ++i
){
int u
= e1
[i
].u
, v
= e1
[i
].v
, p
= e1
[i
].p
;
int x
= fin(u
), y
= fin(v
);
if(x
== y
) continue;
G
[u
][v
] = G
[v
][u
] = p
;
dp
[v
] = -1, dfs(v
, 1);
pre
[x
] = y
, vis
[p
] = 1, ++cnt
;
}
int tot
= 0;
for(int i
= 1; i
<= n
; ++i
) tot
+= pre
[i
] == i
;
if(tot
> 1 || m1
< k
|| cnt
> k
) return printf("-1\n"), 0;
for(int d
= cnt
+ 1; d
<= k
; ++d
){
int mn
= inf
, p
;
for(int i
= 1; i
<= m1
; ++i
){
if(vis
[e1
[i
].p
]) continue;
if(mn
> e1
[i
].w
- ei
[dp
[e1
[i
].v
]].w
){
mn
= e1
[i
].w
- ei
[dp
[e1
[i
].v
]].w
;
p
= i
;
}
}
vis
[e1
[p
].p
] = 1, vis
[dp
[e1
[p
].v
]] = 0;
int u
= ei
[dp
[e1
[p
].v
]].u
, v
= ei
[dp
[e1
[p
].v
]].v
;
G
[u
][v
] = G
[v
][u
] = 0;
G
[1][e1
[p
].v
] = G
[e1
[p
].v
][1] = e1
[p
].p
;
dp
[e1
[p
].v
] = -1, dfs(e1
[p
].v
, 1);
}
printf("%d\n", n
- 1);
for(int i
= 1; i
<= m
; ++i
) if(vis
[i
]) printf("%d ", i
);
printf("\n");
return 0;
}
