随机化算法!!!
中位数可以二分, 把 \(a_{i,j}\leq mid\) 赋为 - 1, 否则为 1, 若 DP 最小值后 \(\leq0\) 则可以继续往更小的地方 DP
假设我们已经知道答案了,\(k\leq5\) 又要最小代价联通, 斯坦纳树!
我们可以把每个颜色随机放入 \(k\) 个盒子, 每个盒子选一个, 那么至少有 \(k\) 种颜色
每次成功的概率为 \(\frac{k!k^{col-k}}{k^{col}}=\frac{k!}{k^k}\),col 为总颜色数
次成功概率为 \(1-(1-\frac{k!}{k^k})^T\),200 次后就非常高了
步骤:
随机
二分
检查 (两个 DP 数组, 第一个为个数 (先保证个数, 每次 DP 一定不变), 第二个为关于中位数的那个)
- #include<bits/stdc++.h>
- using namespace std;
- mt19937 gen(chrono::steady_clock().now().time_since_epoch().count());
- #define rand(r) (uniform_int_distribution<int>(1, r)(gen))
- inline int read(){
- int x=0,f=1;char c=getchar();
- while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
- while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
- return f==1?x:-x;
- }
- const int N=240,inf=0x3f3f3f3f;
- int n,m,k,cn,num,mn,mk,ans1,ans2;
- int b[N],bel[N],vis[N],a[N][N],c[N][N],d[N][N],f[N][40],g[N][40];
- int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
- queue<int>q;
- inline bool upt(int x,int s,int ff,int gg){
- if(ff<f[x][s]||(ff==f[x][s]&&gg<g[x][s])){
- f[x][s]=ff;g[x][s]=gg;
- return 1;
- }
- return 0;
- }
- inline int id(int i,int j){
- return (i-1)*m+j;
- }
- inline bool check(int mid){
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- d[i][j]=(a[i][j]<=mid)?-1:1;
- memset(g,0x3f,sizeof(g));
- memset(f,0x3f,sizeof(f));
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)if(c[i][j]!=-1){
- f[id(i,j)][1<<bel[c[i][j]]-1]=1;
- g[id(i,j)][1<<bel[c[i][j]]-1]=d[i][j];
- }
- for(int s=1,S=(1<<k),x,y,u,v,nx,ny;s<S;s++){
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++){
- x=id(i,j);
- for(int sta=(s-1)&s;sta;sta=(sta-1)&s)
- upt(x,s,f[x][sta]+f[x][s^sta]-1,g[x][sta]+g[x][s^sta]-d[i][j]);
- if(f[x][s]!=inf){q.push(x);vis[x]=1;}
- }
- while(!q.empty()){
- u=q.front();q.pop();
- vis[u]=0;
- y=u%m;if(!y)y=m;
- x=(u-y)/m+1;
- for(int i=0;i<4;i++){
- nx=x+dx[i];ny=y+dy[i];
- v=id(nx,ny);
- if(nx<1||nx>n||ny<1||ny>m||c[nx][ny]==-1)continue;
- if(upt(v,s,f[u][s]+1,g[u][s]+d[nx][ny])&&!vis[v]){q.push(v);vis[v]=1;}
- }
- }
- }
- num=mn=inf;
- for(int i=1,s=(1<<k)-1,x;i<=n;i++)
- for(int j=1;j<=m;j++){
- x=id(i,j);
- if(f[x][s]<num||(f[x][s]==num&&g[x][s]<mn)){
- num=f[x][s];mn=g[x][s];
- }
- }
- return mn<=0;
- }
- inline void stn(){
- for(int i=1;i<=mk;i++)bel[i]=rand(k);
- static int l,r,mid;
- l=1;r=cn;
- while(l<r){
- mid=l+r>>1;
- if(check(mid))r=mid;
- else l=mid+1;
- }
- if(num<ans1||(ans1==num&&r<ans2)){ans1=num;ans2=r;}
- }
- inline void solve(){
- n=read();m=read();k=read();
- mk=0;ans1=ans2=inf;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++){c[i][j]=read();mk=max(mk,c[i][j]);}
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)b[id(i,j)]=a[i][j]=read();
- sort(b+1,b+n*m+1);
- cn=unique(b+1,b+n*m+1)-b-1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- a[i][j]=lower_bound(b+1,b+cn+1,a[i][j])-b;
- for(int T=150;T;T--)stn();
- cout<<ans1<<""<<b[ans2]<<"\n";
- }
- int main(){
- int T=read();
- while(T--)solve();
- return (0-0);
- }
来源: http://www.bubuko.com/infodetail-3518995.html