江门有什么网站推广,数字营销策划,企业邮箱263,网站备案作用*原题链接*
很离谱的题。首先可以想到暴力连边#xff0c;整个图为一个完全图#xff0c;将所有的边选出来#xff0c;然后从小到大一条条加入#xff0c;当剩下集合数量 K 的时候就结束。答案为加入的最后一条边的大小。如果用prim算法的话时间复杂度为。足以通过此题…*原题链接*
很离谱的题。首先可以想到暴力连边整个图为一个完全图将所有的边选出来然后从小到大一条条加入当剩下集合数量 K 的时候就结束。答案为加入的最后一条边的大小。如果用prim算法的话时间复杂度为。足以通过此题。
不过我又打了个表发现了一个性质。设为题目中的那大长式子通过打表观察注意到当x/y固定时的值随y/x的增大而减小。于是我们选前k-1个点构成k-1个集合最后的k到n为第k个集合的值就是最优的。
#includebits/stdc.h
using namespace std;
#define int long long
const int mod2019201997;int n,k;signed main(){cinnk;
// for(int i1;in;i){
// for(int ji1;jn;j){
// couti j (2019201913*i2019201949*j)%modendl;
// }
// }打表cout(2019201913*(k-1)2019201949*n)%modendl;return 0;
}
