P5425 [USACO19OPEN] I Would Walk 500 Miles G

*原题链接*

很离谱的题。首先可以想到暴力连边，整个图为一个完全图，将所有的边选出来，然后从小到大一条条加入，当剩下集合数量 <K 的时候就结束。答案为加入的最后一条边的大小。如果用prim算法的话时间复杂度为。足以通过此题。

不过我又打了个表，发现了一个性质。设为题目中的那大长式子，通过打表观察，注意到当x/y固定时，的值随y/x的增大而减小。于是我们选前k-1个点构成k-1个集合，最后的k到n为第k个集合，的值就是最优的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=2019201997;int n,k;signed main(){cin>>n>>k;
//	for(int i=1;i<=n;i++){
//		for(int j=i+1;j<=n;j++){
//			cout<<i<<" "<<j<<" "<<(2019201913*i+2019201949*j)%mod<<endl;
//		}
//	}打表cout<<(2019201913*(k-1)+2019201949*n)%mod<<endl;return 0;
}