0%

关于haywire的题解

【题目】有N头奶牛,还有N个房间。恰好,每一头奶牛都有3个好朋友,每对好朋友之间要铺电话线,电话线的长度就是他们房间的距离。问如何安排房间,使电话线长度最小。

【输入】

6

6 2 5

1 3 4

4 2 6

5 3 2

4 6 1

1 5 3

【输出】

17

【分析】首先,我们要意识到,这一题,我们用得是状态压缩的集合动态规划来完成。

那么,我们首先要看,如何定下状态呢?我们用集合s来表示当前状态(1表示已经入住房间,0表示尚未入住房间)。那么,我们枚举最后一个入住房间的奶牛p,如图:

他不见了。

现在,我们要看看,奶牛p入住后,会造成怎么样的变化?

如图:

他不见了。

假设奶牛p进入了集合s,为了给奶牛p一个位置,所有尚未入住的奶牛,都要左移一个单位。那么,入住的奶牛和未入住的奶牛的距离,就要加上一个单位。那么,枚举入住了的奶牛和未入住的奶牛,如果双方是朋友,那么增加的距离加1。

因此,状态转移方程就是

他不见了。

,而find_dist就是当前状态下,需要增加多长的电话线。注意的是,调用find_dist是,要默认p也在集合内,因为p自身也有朋友,也需要电话线。

然而,这一道题就是小问题改进大问题。

【程序】

```c++
#include
using namespace std;

ifstream fin(“haywire.in”);
ofstream fout(“haywire.out”);

#define maxn 15
#define oo 100000000

int F[1<<maxn];
int fri[maxn][3];
int N;

void in_() {
fin >> N;
for (int i=0; i<=N; ++i) {
int a, b, c;
fin >> a >> b >> c;

    fri[i][0] = --a;
    fri[i][1] = --b;
    fri[i][2] = --c;//序号从0到N-1比较好处理
}

}

int find_dist(int s) {
int dist=0;
for (int p=0; p!=N; ++p)//枚举p
if (s & (1<<p))//p要在集合内
for (int i=0; i!=3; ++i) {
int q=fri[p][i]; //枚举q
if (!(s & (1<<q))) //q要不在集合内
dist++;//增加的距离加1
}

return dist;

}

void solve() {
for (int i=0; i<=(1<<N); i++)
F[i] = oo;//全部初始化为正无穷

F[0]=0;
for (int s=0; s!=(1<<N); s++)//枚举状态
    for (int p=0; p!=N; ++p) //枚举入住的奶牛
        if (!(s & (1<<p))) {
            int tmp_s=s+(1<<p);

            F[tmp_s] <?= F[s]+find_dist(tmp_s);//状态转移方程
        }

}

void out_() {
fout << F[(1<<N)-1] << endl;
}

int main() {
in_();

solve();//DP

out_();
return 0;

}

Thank you so much.