poj3229（图论+状压dp）

题意：n个城市，一些城市之间有铁路或者公交双向相连。一个人要从0号城市出发，游览其中的m个城市，游览第i个城市需要cost[i]的时间，问此人是否能在特定的时间内游览完这m个城市并返回0市，如果可以输出可以最多游览的城市数量（m个城市包括在里面），否则输出"No Solution"。

解法：状压dp，首先floyd求出两两城市之间的最短路径。

           dp[state][i]表示游览城市集state并以i结束需要的时间，记忆化搜索所有状态并更新答案即可。

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
typedef long long LL;
const int INF=1000000000;
double Map[20][20];
double cost[20];
double dp[1<<17][17];
int N,M,K;
int pass=0;
void init()
{
    for(int i=0; i<(1<<N); i++)
        for(int j=0; j<N; j++)
            dp[i][j]=INF;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            Map[i][j]=INF;
}

void floyd()
{
    for(int k=0; k<N; k++)
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]);
}
int out=0;
int change(int state)
{
    int res=0;
    for(int i=0; i<N; i++)
        if(state&(1<<i))
            res++;
    return res;
}
double dfs(int state,int end)
{
    if(dp[state][end]!=INF)
        return dp[state][end];
    double ans=INF;
    for(int i=0; i<N; i++)
    {
        if(state&(1<<i)&&i!=end)
        {
            if(i!=0)
                ans=min(ans,dfs(state-(1<<end),i)+Map[i][end]+cost[end]);
            else if(i==0&&state-(1<<end)==1)
                ans=min(ans,dfs(state-(1<<end),i)+Map[0][end]+cost[end]);
        }
    }
    if(((state&pass)==pass)&&(ans+Map[end][0])<=K*12)
        out=max(out,change(state));
    //cout<<pass<<" "<<state<<"  "<<ans<<endl;
    return dp[state][end]=ans;
}

int main()
{
    while(scanf("%d%d%d",&N,&M,&K)==3)
    {
        out=0;
        if(N==0&&M==0&&K==0)
            break;
        pass=0;
        for(int i=0; i<M; i++)
        {
            int a;
            scanf("%d",&a);
            a--;
            pass+=(1<<a);
        }
        for(int i=0; i<N; i++)
            scanf("%lf",cost+i);
        int x,y,kind;
        double len;
        init();
        while(scanf("%d%d%lf%d",&x,&y,&len,&kind)==4)
        {
            if(x==0&&y==0&&len==0&&kind==0)
                break;
            x--,y--;
            if(kind)
            {
                Map[x][y]=min(Map[x][y],len/120);
                Map[y][x]=min(Map[y][x],len/120);
            }
            else
            {
                Map[x][y]=min(Map[x][y],len/80);
                Map[y][x]=min(Map[y][x],len/80);
            }
        }
        floyd();
        dp[1][0]=cost[0];
        for(int i=1; i<N; i++)
            dfs((1<<N)-1,i);
        if(out>0)
            cout<<out<<‘\n‘;
        else
            cout<<"No Solution\n";
    }

    return 0;
}

poj3229（图论+状压dp）,布布扣,bubuko.com

poj3229（图论+状压dp）

原文：http://blog.csdn.net/xiefubao/article/details/24302249