LOJ 2997 「THUSCH 2017」巧克力——思路+随机化+斯坦纳树

想到斯坦纳树。但以为只能做 “包含一些点” 而不是 “包含一些颜色” 。而且不太会处理中位数。

其实 “包含一些颜色” 用斯坦纳树做也和普通的一模一样……只是赋初值的时候，遇到该颜色的点就可以更新一下罢了……

中位数可以二分。每个点除了 “块数” 这个关键字之外，再带一个关键字表示 “a[ ][ ]是否大于二分值” ，用 -1 表示不大于，1表示大于，然后普通地跑一个斯坦纳树，看看第二关键字那一维是否 <= 0 即可。

至于处理 “从 m 个颜色中选 k 个颜色 ”，可以用随机化的算法！就是每次给每种颜色一个 0~k-1 的映射，然后直接求 “ 0~k-1 都出现 ” 的答案即可。同一种颜色会映射到同一种颜色，所以映射后的 k 种不同颜色，在映射前也是 k 种不同颜色。

相当于把颜色分成 k 组，要求每组选至少一种颜色。要随机多分几遍组才行。据说 100 次之后正确率就很高了。

一开始求了两点间距离，然后做斯坦纳树的时候，一个点把所有点都用那个距离更新一遍。非常慢。

不用求两点间距离，做斯坦纳树，更新的时候只更新四相邻的格子即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<ctime>

#include<queue>

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

const int N=,INF=1e6+,K=(<<)+;

int n,m,k,tot,bh[N][N],dy[N][],c[N],a[N],tp[N],R;

int bin[],tp2[N],cb[N],ans,prn; bool vis[N];

int xx[]={-,,,},yy[]={,-,,};

struct Node{

  int x,y;

  Node(int x=,int y=):x(x),y(y) {}

  void init(){x=y=N;}

  bool operator< (const Node &b)const

  {return x==b.x?y<b.y:x<b.x;}

  Node operator+ (const Node &b)const

  {return Node(x+b.x,y+b.y);}

  Node operator- (const Node &b)const

  {return Node(x-b.x,y-b.y);}

}vl[N],dp[N][K];

priority_queue<pair<Node,int> >q;

queue<int> q2;

Node Mn(Node u,Node v){return u<v?u:v;}

Node Inv(Node u){return Node(-u.x,-u.y);}

void init()

{

  ans=N; prn=INF;

  bin[]=;for(int i=;i<=k;i++)bin[i]=bin[i-]<<;

  for(int i=;i<=tot;i++)tp[i]=a[i];

  sort(tp+,tp+tot+); R=unique(tp+,tp+tot+)-tp-;

}

Node chk(int mid)

{

  for(int i=;i<=tot;i++)vl[i]=Node(,a[i]<=mid?-:);

  for(int i=;i<=tot;i++)

    {

      for(int j=;j<bin[k];j++)dp[i][j].init();

      if(c[i]!=-)dp[i][bin[cb[i]]]=vl[i];//if

    }

  for(int s=;s<bin[k];s++)

    {

      for(int i=;i<=tot;i++)

    for(int t=(s-)&s;t;t=(t-)&s)

      dp[i][s]=Mn(dp[i][s],dp[i][t]+dp[i][s^t]-vl[i]);

      for(int i=;i<=tot;i++)q2.push(i),vis[i]=;

      while(q2.size())

    {

      int k=q2.front(); q2.pop(); vis[k]=;

      int x=dy[k][], y=dy[k][];

      for(int i=,tx,ty;i<;i++)

        {

          tx=x+xx[i]; ty=y+yy[i];

          if(!tx||tx>n||!ty||ty>m)continue;

          int v=bh[tx][ty]; if(c[v]==-)continue;

          if(dp[k][s]+vl[v]<dp[v][s])

        {

          dp[v][s]=dp[k][s]+vl[v];

          if(!vis[v])q2.push(v),vis[v]=;

        }

        }

    }

    }

  int U=bin[k]-; Node ret=dp[][U];

  for(int i=;i<=tot;i++)ret=Mn(ret,dp[i][U]);

  return ret;

}

void solve()

{

  for(int i=;i<=tot;i++) tp2[i]=rand()%k;

  for(int i=;i<=tot;i++) cb[i]=tp2[c[i]];

  int l=,r=R,ret=N,r2=N;

  while(l<=r)

    {

      int mid=l+r>>;

      Node d=chk(tp[mid]); ret=d.x;

      if(ret==N||ret>ans)break;//

      if(d.y<=)r2=tp[mid],r=mid-;

      else l=mid+;

    }

  if(ret<ans)ans=ret,prn=r2;

  else if(ret==ans)prn=Mn(prn,r2);

}

int main()

{

  int T=rdn(); srand(time());

  while(T--)

    {

      n=rdn();m=rdn();k=rdn(); tot=;

      for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

      bh[i][j]=++tot,dy[tot][]=i,dy[tot][]=j;

      for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)c[bh[i][j]]=rdn();

      for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)a[bh[i][j]]=rdn();

      init();

      for(int t=;t<=;t++)solve();

      if(ans==N)puts("-1 -1");

      else printf("%d %d\n",ans,prn);

    }

  return ;

}

秒客网

LOJ 2997 「THUSCH 2017」巧克力——思路+随机化+斯坦纳树

相关文章