2015-2016-petrozavodsk-winter-training-camp-spb-su-spb-au-contest F-Colored Path(状压DP)

题面:

Colored Path

									Time limit: 1.5 seconds
								  Memory limit: 256 mebibytes

Problem Description

You have a board of size n × n. Each cell of the board has weight and color. Both weight and color are
positive integers. Rows and columns are enumerated from 1 to n. Let (i, j) be j-th cell of i-th row. In one
step you can move from cell (i, j) to cells (i, j + 1) and (i + 1, j).

Consider all paths from (1, 1) to (n, n) that obey the rule above. Obviously each such path contains
exactly 2n − 1 cells. Let’s define the weight of the path as the sum of the weights of the cells on the path.
Let’s define the colorness of the path as the number of different colors among the colors of the cells on
the path.

Given the weights and the colors of all cells, find the smallest colorness among all paths with weight no
more than W or report that there are no such paths.

Input

The first line contains three integers: n (1 ≤ n ≤ 400), k (1 ≤ k ≤ 10) which is the number of possible
colors, and W (1 ≤ W ≤ $10^9$109). Each of the next n lines contains n integers, j-th integer on i-th line is the
weight of the cell (i, j) (1 ≤ $w_{ij}$wij​ ≤ $10^6$106). The last n lines contain n integers each, j-th integer on i-th line
is the color of the cell (i, j) (1 ≤ $c_{ij}$cij​ ≤ k).

Output

On the first line output the minimal colorness of the path. On the second line output the path with
the minimal colorness in the format $i_1$i1​ $j_1$j1​ $i_2$i2​ $j_2$j2​ . . . $i_{2n−1}$i2n−1​ $j_{2n−1}$j2n−1​. If there are several paths with minimal
colorness, output any of them. If there are no paths with weight no more than W, output −1 on a single
line.

Sample Input

3 3 10
1 1 1
5 3 1
5 3 1
1 2 3
2 2 1
3 3 2

Sample Output

2
1 1 1 2 2 2 2 3 3 3

题意描述

给出一个$N*N$N∗N的网点图,每个点都有两条单向路,通向相邻的左方的点和相邻的下方的点.每个点都有权值和一种颜色.求出从$(1 , 1)$(1,1)出发达到$(N , N)$(N,N)的路径中权值和不超过$W$W的情况下颜色种类最少而且权值和最小的那个路径,并把路径经过的点坐标输出.

题目分析

因为颜色只有$10$10种,最多有$160000$160000个点,考虑用状压来代表哪些颜色会在路径中出现,并按照当前的颜色状态进行状态转移.

枚举0 , 1 , 2 … k 种颜色的全排列,然后O($N^2$N2)时间内进行状态转移.
能够进行状态转移的前提条件是当前枚举的颜色的全排列中,要进行状态转移的点的颜色为存在状态

状态转移方程为
$ans_{i,j}$ansi,j​ = $min(ans_{i-1 , j}+W_{i , j} , ans_{i , j-1}+W_{i , j} , ans_{i , j})$min(ansi−1,j​+Wi,j​,ansi,j−1​+Wi,j​,ansi,j​)
而且需要注意权值和不能超过$W$W.

具体代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, k, W, NUM;
ll w[405][405];
int c[405][405];
ll ans[405][405];
bool f[405][405]; // 0从左边走右边, 1从上面走下来
bool vis[5000];

void pre_do()
{
    NUM = 0;
    memset(vis , 0 , sizeof(vis));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            c[i][j] = 1 << c[i][j];
}

void init()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            ans[i][j] = inf;
}

bool DFS(int status)
{
    init();
    memset(f , 0 , sizeof(f));
    if(status&c[1][1])
        ans[1][1] = w[1][1];
    else
        return 0;
    for(int x = 1; x <= n; x++)
    {
        for(int y = 1; y <= n; y++)
        {
            ll dans = ans[x-1][y]+w[x][y];
            ll lans = ans[x][y-1]+w[x][y];
            if(x > 1 && c[x][y]&status && ans[x][y] > dans && dans <= W)
            {
                ans[x][y] = dans;
                f[x][y] = 1;
            }
            if(y > 1 && c[x][y]&status && ans[x][y] > lans && lans <= W)
            {
                ans[x][y] = lans;
                f[x][y] = 0;
            }
        }
    }
    if(ans[n][n] == inf)
    {
        return 0;
    }
    else
    {
        while(status)
        {
            if(status&1)
                NUM++;
            status >>= 1;
        }
        return 1;
    }
    return 0;
}

bool solve()
{
    queue < int > que;
    que.push(0);
    while(!que.empty())
    {
        if(!vis[que.front()])
        {
            vis[que.front()] = 1;
            if(DFS(que.front())) return 1;
            for(int i = 1; i <= k; i++)
                if((que.front()>>i)&1)
                    continue;
                else
                    que.push(que.front()+(1<<i));
        }
        que.pop();
    }
    return 0;
}

int main()
{
    scanf("%d %d %d", &n, &k, &W);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%lld", &w[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &c[i][j]);
    pre_do();
    if(w[1][1] > W)
    {
        printf("-1");
        return 0;
    }
    if(n == 1)
    {
        printf("1\n");
        printf("1 1\n");
        return 0;
    }
    if(solve())
    {
        printf("%d\n", NUM);
        int x = n, y = n;
        stack < pair < int , int > > stk;
        while(x != 1 || y != 1)
        {
            pair < int , int > tmp;
            tmp.first = x, tmp.second = y;
            stk.push(tmp);
            if(f[x][y])
                x--;
            else
                y--;
        }
        printf("1 1 ");
        while(!stk.empty())
        {
            printf("%d %d ", stk.top().first, stk.top().second);
            stk.pop();
        }
        return 0;
    }
    printf("-1");
    return 0;
}