题目大意

　　有一个网格（或者你可以认为这是一个图），每个点都有颜色 \(c_i\) 和点权 \(a_i\)。

　　求最小的连通块，满足这个连通块内点的颜色数量 \(\geq k\)。在满足点数最少的前提下，要求点权的中位数最少。

　　\(n\leq 233,c_i\leq n,k\leq 5\)

题解

　　如果 \(c_i\) 很小，就可以直接用斯坦纳树做。

　　本题要求在满足点数最少的前提下，要求点权的中位数最少。那么可以二分中位数 \(s\)，将 \(a_i\leq s\) 的点的权值设为 \(M-1\)，\(a_i>s\) 的点的权值设为 \(M+1\)，其中 \(M\) 是一个很大的数。这样就可以在满足点数最小的前提下求出最小中位数是否 \(\leq s\)。

　　还有一个问题是 \(c_i\) 比较大。我们可以把每一种颜色随机映射到 \([1,k]\) 中，当答案的 \(k\) 种颜色映射到 \([1,k]\) 中不同的值的时候就能求出正确答案。求一次正确的概率是 \(\frac{k!}{k^k}\)，多求几次就好了。

　　时间复杂度：\(O(T(3^kn+2^kn\log n)\log n)\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef long double ldb;typedef std::pair
              
                pii;typedef std::pair
               
                 pll;void open(const char *s){#ifndef ONLINE_JUDGE char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}void open2(const char *s){#ifdef DEBUG char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}int upmin(int &a,int b){if(b
                
                 a){a=b;return 1;}return 0;}const int inf=0x3fffffff;const int N=300;int _n,_m;int n,k;int t;int a[N],c[N],d[N],e[N],b[N],vis[N];int a2[N],c2[N];int f[1<<5][N];vector
                 
                   g[N];pii ans;queue
                  
                    q1,q2,q3;//priority_queue
                   
                    
                     ,greater
                     
                       > q;int id(int x,int y){ return (x-1)*_m+y;}vector
                      
                        h;int check(int v){ for(int i=1;i<=n;i++) if(a[i]<=v) a2[i]=100000-1; else a2[i]=100000+1; for(int i=0;i<1<