c/c++语言开发共享[WC2008] 游览计划

这题斯坦纳树的做法详见，此处写插头dp的做法。

用最小表示法来描述轮廓线上的连通性（如果某个点不选，记标号为0），与“括号表示法”不同，此轮廓线长度位m而非m+1，即轮廓线里不在有当前格子左侧的边上的插头（与左边格子的插头本质相同）。
设当前格子为(x,y),左侧格子上的插头p1，当前上方格子的插头p2。显然仅当(x,y)是不是景点且不选这个格子不会使得p2（如果有）脱离轮廓线时，(x,y)可以不选。（因为要保证最终所选的点联通）
就酱。

#include <bits/stdc++.h> const int inf=0x3f3f3f3f;  struct hash_map {     static const int p=23333;     int siz,hsh[p],key[p],val[p];     void clear() {         siz=0;         memset(hsh,0,sizeof hsh);         memset(key,-1,sizeof key);         memset(val,0x3f,sizeof val);     }     void new_hsh(int id,int sta) {         hsh[id]=++siz,key[siz]=sta;     }      int get(int sta) {         for(int i=sta%p; ; i=(i+1==p?0:i+1)) {             if(!hsh[i]) new_hsh(i,sta);             if(key[hsh[i]]==sta) return hsh[i];         }     }  } f[2];  int n,m; int a[11][11],edx,edy; bool slc[11][11];  int find(int sta,int bit) {     if(bit==0) return 0;     return (sta>>(3*(bit-1)))&7; }  void set(int&sta,int bit,int val) {     bit=3*(bit-1);     sta|=7<<bit;     sta^=7<<bit;     sta|=val<<bit; } int cnt(int sta,int val) {     int c=0;     for(int i=1; i<=m; ++i,sta>>=3)          c+=(sta&7)==val;     return c; } int relabel(int sta) {     static int hs,cnt,w[11],id[11];     memset(id,-1,sizeof id);     hs=cnt=id[0]=0;     for(int i=1; i<=m; ++i,sta>>=3) w[i]=sta&7;     for(int i=m; i; --i) {         if(id[w[i]]==-1) id[w[i]]=++cnt;         hs=hs<<3|id[w[i]];     }      return hs; } bool unicom(int sta) { //存再标号>1 不只一个连通块     for(int i=1; i<=m; ++i,sta>>=3)          if((sta&7)>1) return 0;     return 1; }  struct state { //输出方案     int x,y,last;     bool select; } q[10*10*23333];  int bas,lbas,cur,ans=inf,now,lst=1;  void p_dp(int x,int y) {     now=lst,lst^=1;     f[now].clear();     lbas=bas, bas+=f[lst].siz;     for(int i=1; i<=f[lst].siz; ++i) {         int sta=f[lst].key[i];         int val=f[lst].val[i];         int p1=find(sta,y-1);         int p2=find(sta,y);         if(a[x][y]&&(!p2||cnt(sta,p2)>1)) {             int tmp=sta;             set(tmp,y,0);             int c=f[now].get(tmp);             if(f[now].val[c]>val) {                 f[now].val[c]=val;                 q[bas+c]=(state){x,y,lbas+i,false};             }         }          if(!p1&&!p2) set(sta,y,7);         else if(!p1&&p2);         else if(p1&&!p2) set(sta,y,p1);         else if(p1!=p2) {             for(int tmp=sta,i=1; i<=m; ++i,tmp>>=3)                  if((tmp&7)==p1) set(sta,i,p2);         }         int c=f[now].get(relabel(sta));         if(f[now].val[c]>val+a[x][y]) {             f[now].val[c]=val+a[x][y];             q[bas+c]=(state){x,y,lbas+i,true};         }     }     if(x<edx||(x==edx&&y<edy)) return;     for(int i=1; i<=f[now].siz; ++i) {         if(f[now].val[i]<ans&&unicom(f[now].key[i]))             ans=f[now].val[i],cur=bas+i;     } }  int main() {     scanf("%d%d",&n,&m);     int tot=0;     for(int i=1; i<=n; ++i) {         for(int j=1; j<=m; ++j) {             scanf("%d",&a[i][j]);             if(!a[i][j]) edx=i,edy=j,tot++;         }     }     if(tot<2) return puts("0"),0;     f[now].clear();     f[now].val[f[now].get(0)]=0;     for(int i=1; i<=n; ++i) {         for(int j=1; j<=m; ++j) p_dp(i,j);     }     printf("%dn",ans);     for(int i=cur; i; i=q[i].last) {         if(q[i].select) slc[q[i].x][q[i].y]=1;     }     for(int i=1; i<=n; ++i,puts("")) {         for(int j=1; j<=m; ++j) {             if(!a[i][j]) putchar('x');             else if(slc[i][j]) putchar('o');             else putchar('_');         }     }     return 0; }