题解 P5425 【[USACO19OPEN]I Would Walk 500 Miles】

Great_Influence

2019-05-29 21:14:15

Solution

算法 $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)$ 。 代码就不贴了。