首页 > 数据结构 > Hash表 > hdu 1964 Pipes-动态规划-[解题报告]C++
2013
12-26

hdu 1964 Pipes-动态规划-[解题报告]C++

Pipes

问题描述 :

The construction of office buildings has become a very standardized task. Pre-fabricated modules are combined according to the customer’s needs, shipped from a faraway factory, and assembled on the construction site. However, there are still some tasks that require careful planning, one example being the routing of pipes for the heating system.

Amodern office building ismade up of squaremodules, one on each floor being a service module from which (among other things) hot water is pumped out to the other modules through the heating pipes. Each module (including the service module) will have heating pipes connecting it to exactly two of its two to four neighboring modules. Thus, the pipes have to run in a circuit, from the service module, visiting each module exactly once, before finally returning to the service module. Due to different properties of the modules, having pipes connecting a pair of adjacent modules comes at different costs. For example, some modules are separated by thick walls, increasing the cost of laying pipes. Your task is to, given a description of a floor of an office building, decide the cheapest way to route the heating pipes.

输入:

The first line of input contains a single integer, stating the number of floors to handle. Then follow n floor descriptions, each beginning on a new line with two integers, 2 <= r <= 10 and 2 <= c <= 10, defining the size of the floor � r-by-c modules. Beginning on the next line follows a floor description in ASCII format, in total 2r + 1 rows, each with 2c + 2 characters, including the final newline. All floors are perfectly rectangular, and will always have an even number of modules. All interior walls are represented by numeric characters, ’0’ to ’9’, indicating the cost of routing pipes through the wall (see sample input).

输出:

The first line of input contains a single integer, stating the number of floors to handle. Then follow n floor descriptions, each beginning on a new line with two integers, 2 <= r <= 10 and 2 <= c <= 10, defining the size of the floor � r-by-c modules. Beginning on the next line follows a floor description in ASCII format, in total 2r + 1 rows, each with 2c + 2 characters, including the final newline. All floors are perfectly rectangular, and will always have an even number of modules. All interior walls are represented by numeric characters, ’0’ to ’9’, indicating the cost of routing pipes through the wall (see sample input).

样例输入:

3
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######
4 4
#########
# 2 3 3 #
#1#9#1#4#
# 2 3 6 #
#1#7#1#5#
# 5 3 1 #
#1#9#1#7#
# 2 3 0 #
#########
2 2
#####
# 1 #
#2#3#
# 4 #
#####

样例输出:

28
45
10

  题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1964

  空白区域之间有权值,求经过所有空白区域的哈密顿回路的最小权值。简单的插头DP,空白区域特殊处理即可。

//STATUS:C++_AC_203MS_664KB
 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<iostream>
 #include<string>
 #include<algorithm>
 #include<vector>
 #include<queue>
 #include<stack>
 #include<map>
 using namespace std;
 #define LL long long
 #define pii pair<int,int>
 #define Max(a,b) ((a)>(b)?(a):(b))
 #define Min(a,b) ((a)<(b)?(a):(b))
 #define mem(a,b) memset(a,b,sizeof(a))
 #define lson l,mid,rt<<1
 #define rson mid+1,r,rt<<1|1
 const int N=21,INF=0x3f3f3f3f,MOD=40001,STA=8000010;
 const double DNF=1e13;
 
 int g[N][N],code[N],ma[N];
 int T,n,m,ex,ey;
 
 struct Hash{     //Hash表,MOD为表长,STA为表大小
     int first[MOD],next[STA],size;
     int f[STA];
     LL sta[STA];
     void init(){
         size=0;
         mem(first,-1);
     }
     void add(LL st,int ans){
         int i,u=st%MOD;
         for(i=first[u];i!=-1;i=next[i]){
             if(sta[i]==st){
                 f[i]=Min(f[i],ans);
                 return;
             }
         }
         sta[size]=st;
         f[size]=ans;
         next[size]=first[u];
         first[u]=size++;
     }
 }hs[2];
 
 void shift(int p)    //换行移位
 {
     int k;
     LL sta;
     for(k=0;k<hs[!p].size;k++){
         sta=hs[!p].sta[k]<<3;
         hs[p].add(sta,hs[!p].f[k]);
     }
 }
 
 LL getsta()   //最小表示法
 {
     LL i,cnt=1,sta=0;
     mem(ma,-1);
     ma[0]=0;
     for(i=0;i<=m;i++){
         if(ma[code[i]]==-1)ma[code[i]]=cnt++;
         code[i]=ma[code[i]];
         sta|=(LL)code[i]<<(3*i);
     }
     return sta;
 }
 
 void getcode(LL sta)
 {
     int i;
     for(i=0;i<=m;i++){
         code[i]=sta&7;
         sta>>=3;
     }
 }
 
 void unblock(int i,int j,int p)
 {
     int k,t;
     LL cnt,x,y;
     for(k=0;k<hs[!p].size;k++){
         getcode(hs[!p].sta[k]);
         x=code[j],y=code[j+1];
         cnt=hs[!p].f[k];
         if(x && y){     //合并连通分量
             code[j]=code[j+1]=0;
             if(x!=y){
                 for(t=0;t<=m;t++)
                     if(code[t]==y)code[t]=x;
                 hs[p].add(getsta(),cnt+(g[i][j]<10?g[i][j]:0));
             }
             else if(i==ex && j==ey){   //最后一个点特殊处理
                 hs[p].add(getsta(),cnt);
             }
         }
         else if(x&&!y || !x&&y){   //延续连通分量
             t=x?x:y;
             if(g[i+1][j]>=0){
                 code[j]=t;code[j+1]=0;
                 hs[p].add(getsta(),cnt+(g[i][j]<10?g[i][j]:0));
             }
             if(g[i][j+1]>=0){
                 code[j]=0;code[j+1]=t;
                 hs[p].add(getsta(),cnt+(g[i][j]<10?g[i][j]:0));
             }
         }
         else {  //创建新连通分量
             if(g[i][j]>=0 && g[i][j]<=9){
                 hs[p].add(getsta(),cnt);
             }
             if(g[i+1][j]>=0 && g[i][j+1]>=0){
                 code[j]=code[j+1]=8;
                 hs[p].add(getsta(),cnt);
             }
         }
     }
 }
 
 void block(LL j,int p)
 {
     int k;
     for(k=0;k<hs[!p].size;k++){
         getcode(hs[!p].sta[k]);
         if(code[j]==0 && code[j+1]==0)
             hs[p].add(getsta(),hs[!p].f[k]);
     }
 }
 
 int slove()
 {
     int i,j,p;
     hs[0].init();
     hs[p=1].init();
     hs[0].add(0,0);
     for(i=0;i<n;i++){
         for(j=0;j<m;j++){
             if(g[i][j]>=0)unblock(i,j,p);
             else p=!p;
             hs[p=!p].init();
         }
         shift(p);   //换行移位
         hs[p=!p].init();
     }
     for(i=0;i<hs[!p].size;i++)
         if(hs[!p].sta[i]==0)return hs[!p].f[i];
     return 0;
 }
 
 int main()
 {
  //   freopen("in.txt","r",stdin);
     int i,j,ans;
     char s[N];
     scanf("%d",&T);
     while(T--)
     {
         scanf("%d%d",&n,&m);
         mem(g,-1);
         n=n*2-1;
         m=m*2-1;
         scanf("%s",s);
         getchar();
         for(i=0;i<n;i++){
             gets(s);
             for(j=1;j<=m;j++){
                 if(s[j]==' ')g[i][j-1]=10;
                 else if(s[j]=='#')g[i][j-1]=-1;
                 else g[i][j-1]=s[j]-'0';
             }
         }
         scanf("%s",s);
         ex=n-1,ey=m-1;
 
         ans=slove();
 
         printf("%d\n",ans);
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/zhsl/archive/2013/04/07/3003852.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥