题解 P5425 【[USACO19OPEN]I Would Walk 500 Miles】
Great_Influence
2019-05-29 21:14:15
算法 $1$:
我们将所有的边选出来,然后从小到大一条条加入,当剩下集合数量 $< K$ 的时候就结束。答案为加入的最后一条边的大小。
复杂度 $O(N^2\log N)$ 。
过不去,不贴代码。
算法 $2$:
观察上述算法,发现导致集合数量下降的边一定在最小生成树上。(算法 $1$ 其实等价于 $kruskal$) 因此,我们选择将最小生成树求出,然后答案就是最小生成树上边权第 $N-K+1$ 小的边长。
利用 $prim$ 求解,复杂度 $O(N^2)$ 。
代码:
```cpp
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iostream>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mp make_pair
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;
namespace IO
{
const uint32 Buffsize=1<<15,Output=1<<23;
static char Ch[Buffsize],*S=Ch,*T=Ch;
inline char getc()
{
return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
}
static char Out[Output],*nowps=Out;
inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
template<typename T>inline void read(T&x)
{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
x*=f;
}
template<typename T>inline void write(T x,char ch='\n')
{
if(!x)*nowps++='0';
if(x<0)*nowps++='-',x=-x;
static uint32 sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
}
}
using IO::read;
using IO::write;
using IO::getc;
using IO::flush;
inline void Chkmin(int&u,int v){u>v?u=v:0;}
inline void Chkmax(int&u,int v){u<v?u=v:0;}
inline void file()
{
#ifndef ONLINE_JUDGE
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
#endif
}
const int MAXN=7507;
static int n,k;
inline void init()
{
read(n),read(k);
}
static int dis[MAXN][MAXN];
static int ds[MAXN],vs[MAXN];
static int w[MAXN];
inline void solve()
{
Rep(i,1,n-1)Rep(j,i+1,n)dis[j][i]=dis[i][j]=(2019201913ll*i+2019201949ll*j)%2019201997;
Rep(i,2,n)ds[i]=dis[1][i];
vs[1]=1,ds[0]=2147483647;
register int rt=1;
Rep(i,1,n-1)
{
Rep(j,1,n)Chkmin(ds[j],dis[rt][j]);
rt=0;
Rep(j,2,n)if(!vs[j]&&ds[j]<ds[rt])rt=j;
vs[rt]=1,w[i]=ds[rt];
}
sort(w+1,w+n);
cout<<w[n-k+1]<<endl;
}
int main()
{
file();
init();
solve();
return 0;
}
```
算法 $3$:
观察边权,可以发现 $(i,j)$ 之间连的边长度为 $2019201997-84i-48j$ 。
因此,这棵最小生成树的形态一定为一朵以 $N$ 为根的菊花树,且边权分别为 $2019201997-84i-48N$ 。
那么,第 $N-K+1$ 小的边长度就是:
$$2019201997-84(K-1)-48N$$
$$=2019202081-84K-48N$$
复杂度 $O(1)$ 。
代码就不贴了。