題目大意

　　有一個網格（或者你可以認為這是一個圖），每個點都有顏色 \(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<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<ctime> #include<functional> #include<cmath> #include<vector> #include<assert.h> #include<queue> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef std::pair<int,int> pii; typedef std::pair<ll,ll> pll; void open(const char *s){ #ifndef ONLINE_JUDGEchar 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 DEBUGchar 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;} int upmax(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<int> g[N]; pii ans; queue<pii> q1,q2,q3; //priority_queue<pii,vector<pii>,greater<pii> > q; int id(int x,int y) {return (x-1)*_m+y; } vector<pii> h; int check(int v) {for(int i=1;i<=n;i++)if(a[i]<=v)a2[i]=100000-1;elsea2[i]=100000+1;for(int i=0;i<1<<k;i++)for(int j=1;j<=n;j++)f[i][j]=inf;for(int i=1;i<=n;i++)if(c2[i]!=-1)f[1<<(c2[i]-1)][i]=0;for(int i=1;i<1<<k;i++){for(int j=(i-1)&i;j;j=(j-1)&i)for(int l=1;l<=n;l++)f[i][l]=min(f[i][l],f[j][l]+f[i^j][l]);h.clear();for(int j=1;j<=n;j++){h.push_back(pii(f[i][j],j));vis[j]=0;}sort(h.begin(),h.end());for(int i=0;i<n;i++)q3.push(h[i]);while(!q1.empty()||!q2.empty()||!q3.empty()){pii x;if(!q1.empty()&&(q2.empty()||(q1.front()<=q2.front()))&&(q3.empty()||(q1.front()<=q3.front()))){x=q1.front();q1.pop();}else if(!q2.empty()&&(q1.empty()||(q2.front()<=q1.front()))&&(q3.empty()||(q2.front()<=q3.front()))){x=q2.front();q2.pop();}else{x=q3.front();q3.pop();}if(vis[x.second])continue;vis[x.second]=1;f[i][x.second]=min(f[i][x.second],x.first);x.first+=a2[x.second]; // for(auto v:g[x.second])for(vector<int>::iterator it=g[x.second].begin();it!=g[x.second].end();it++){int v=*it;if(!vis[v]){if(a2[x.second]==100000-1)q1.push(pii(x.first,v));elseq2.push(pii(x.first,v));}}}}int res=inf;for(int i=1;i<=n;i++)if(c2[i]!=-1){f[(1<<k)-1][i]+=a2[i];res=min(res,f[(1<<k)-1][i]);}return res; } void gao() {for(int i=1;i<=n;i++)b[i]=rand()%k+1;for(int i=1;i<=n;i++)if(c[i]!=-1)c2[i]=b[c[i]];elsec2[i]=-1;int l=1,r=t;int temp=check(1);if(temp==inf)return;int v=(int)round((db)temp/100000);if(v>ans.first)return;while(l<r){int mid=(l+r)>>1;temp=check(mid);if(temp<=(int)round((db)temp/100000)*100000)r=mid;elsel=mid+1;}ans=min(ans,pii(v,l)); } void solve() {scanf("%d%d%d",&_n,&_m,&k);n=_n*_m;for(int i=1;i<=n;i++)scanf("%d",&c[i]);for(int i=1;i<=n;i++){scanf("%d",&a[i]);d[i]=a[i];}sort(d+1,d+n+1);t=unique(d+1,d+n+1)-d-1;for(int i=1;i<=n;i++)a[i]=lower_bound(d+1,d+t+1,a[i])-d;for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<=_n;i++)for(int j=1;j<=_m;j++)if(c[id(i,j)]!=-1){if(i>1&&c[id(i-1,j)]!=-1)g[id(i,j)].push_back(id(i-1,j));if(i<_n&&c[id(i+1,j)]!=-1)g[id(i,j)].push_back(id(i+1,j));if(j>1&&c[id(i,j-1)]!=-1)g[id(i,j)].push_back(id(i,j-1));if(j<_m&&c[id(i,j+1)]!=-1)g[id(i,j)].push_back(id(i,j+1));}ans=pii(inf,inf);for(int times=200;times;times--)gao();if(ans.first==inf)printf("-1 -1\n");elseprintf("%d %d\n",ans.first,d[ans.second]); } int main() {srand(19260817);open("chocolate");int t;scanf("%d",&t);while(t--)solve();return 0; }z

轉載于:https://www.cnblogs.com/ywwyww/p/10290909.html

總結

以上是生活随笔為你收集整理的【THUSC2017】【LOJ2977】巧克力 斯坦纳树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。