拯救莫莉斯

问题描述

莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。

圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市（1<=x<= n, 1<=y<=m）。两座城市间相邻的定义为：对于城市(Ax, Ay)和城市(Bx, By)，满足(Ax - Bx)²+ (Ay - By)² = 1。

由于圣域的石油贸易总量很大，莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率，莫莉斯·乔决定在其中一些城市里建造油库，最终使得每一个城市X都满足下列条件之一：

1.该城市X内建有油库，

2.某城市Y内建有油库，且城市X与城市Y相邻。

与地球类似，圣域里不同城市间的地价可能也会有所不同，所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案，为了方便管理，莫莉斯会选择建造较少的油库个数。

输入格式

第一行两个正整数n,m ( n * m <= 50 且m<=n)，表示矩阵的大小。

接下来一个n行m列的矩阵F，F_{i, j}表示在城市(i,j)建造油库的代价。

输出格式

输出两个数，建造方案的油库个数和方案的总代价。

输入样例：

输出样例：

3 3

6 5 4

1 2 3

7 8 9

3 6

数据范围

对于30%数据满足 n * m <= 25;

对于100%数据满足n * m <= 50; 0 <= F_{i, j}<= 100000

solution

考试的时候吧n*m=50 看成n，m<=50了，结果想了半天网络流......

正解是状压以为m最大是7

f[i][j][k]：到了第i行前一个i-1行状态为j，i行状态为k

从当前往后推 f[i+1][k][x]=min(f[i][j][k]+cost[i+1][x]) ( j|k|x|(k<<1)|(k>>1) )&maxp==maxp

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define mem(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int N=(1<<7)+30;
 7 inline int minn(int a,int b){return a<b?a:b;}
 8 
 9 int n,m,maxp,ans,sum;
10 int v[56][56],cost[56][N],num[56][N];
11 int f[56][N][N],g[56][N][N];
12 //f：代价 g:数目 
13 void chu()
14 {
15     for(int i=1;i<=n;++i)
16         for(int j=0;j<=maxp;++j)
17           for(int k=1;k<=m;++k)
18                 if((1<<(k-1))&j)
19                 {
20                   cost[i][j]+=v[i][k];
21                   ++num[i][j];
22                 }
23 }
24 
25 void out11()
26 {
27     printf("
");
28     for(int i=1;i<=n;++i)
29     {
30       for(int j=0;j<=maxp;++j)
31         for(int k=0;k<=maxp;++k)
32           cout<<f[i][j][k]<<' ';
33       printf("
");
34     }
35     printf("
");
36 }
37 
38 int main(){
39     //freopen("1.txt","r",stdin);
40     //freopen("proj7.in","r",stdin);
41     scanf("%d%d",&n,&m);
42     maxp=(1<<m)-1;
43     for(int i=1;i<=n;++i)
44       for(int j=1;j<=m;++j)
45         scanf("%d",&v[i][j]);
46     chu();
47     mem(f,0x7f);mem(g,0x7f);
48     for(int i=0;i<=maxp;++i)
49     {
50       f[1][0][i]=cost[1][i];
51       g[1][0][i]=num[1][i];
52     }
53     for(int i=1;i<=n;++i)
54       for(int j=0;j<=maxp;++j)
55         for(int k=0;k<=maxp;++k)
56           for(int l=0;l<=maxp;++l)
57           {
58               if( ((j|k|l|(k<<1)|(k>>1))&maxp)==maxp )
59               {
60                         //if(i==2&&j==0&&k==maxp&&l==0)system("pause");
61                         if(f[i+1][k][l]>f[i][j][k]+cost[i+1][l])
62                         {
63                             f[i+1][k][l]=f[i][j][k]+cost[i+1][l];
64                             g[i+1][k][l]=g[i][j][k]+num[i+1][l];
65                         }
66                         else
67                           if(f[i+1][k][l]==f[i][j][k]+cost[i+1][l])
68                               g[i+1][k][l]=minn(g[i+1][k][l],g[i][j][k]+num[i+1][l]);
69                     }
70                 }
71     
72     //cout<<f[2][0][maxp]<<endl;
73     //cout<<f[3][maxp][0];
74     //out11();
75     ans=0x7fffffff;
76     sum=0x7fffffff;
77     for(int i=0;i<=maxp;++i)
78     {
79         if(ans>f[n+1][i][0])
80         {
81             ans=f[n+1][i][0];
82             sum=g[n+1][i][0];
83         }
84         else
85           if(ans==f[n+1][i][0])
86             sum=minn(sum,g[n+1][i][0]);
87         //printf("ans=%d sum=%d
",ans,sum);
88     }
89     printf("%d %d",sum,ans);
90     //while(1);
91     return 0;
92 }

code