poj2686 状压dp入门

状压dp第一题：很多东西没看懂，慢慢来，状压dp主要运用了位运算，二进制处理

集合｛0，1，2，3，....，n-1｝的子集可以用下面的方法编码成整数

像这样，一些集合运算就可以用如下的方法来操作：

1.空集....................0

2.只含有第i个元素的集合｛i｝................1 << i

3.含有全部n个元素的集合{0,1,2,3,....,n - 1}.............(1 << n) - 1

4.判断第i个元素是否属于集合S.................................if(S >> i & 1)

5.向集合中加入第i个元素S ∪ {i}...............................S | 1 << i

6.从集合中除去第i个元素S \ {i}..................................S & ~(1 << i)

7.集合S和T的并集S∪T...............................................S | T

8.集合S和T的交集S∩T................................................S & T

题意：一个人在m个城市的国家旅行，他有n张车票，这个国家有p条路，一条路连接两个城市，他要从a城市到b城市，从一个城市到另一个城市所需要的时间是路的长度除以车票的面值，面值表示可以有多少匹马来拉，求最短的时间。

题解：看代码，主要就是状压dp+dijkstra

还有一点就是min只能用于整形，这样的话要算float的话就只能用宏定义了

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 10007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define MIN(a,b) a<b ? a:b

using namespace std;

const double g=10.0,eps=1e-;

const int N=,maxn=,inf=<<;

int n,m,p,a,b,t[maxn];

int d[maxn][maxn];

double dp[<<N][maxn];

void solve()

{

    for(int i=;i< <<n;i++)//从0到1<<n是所以子集

        fill(dp[i],dp[i]+m,inf);//把dp初始化

    dp[(<<n)-][a-]=;//起始点设为0，就是dijkstra算法

    double res=inf;

    for(int s=(<<n)-;s>=;s--)

    {

        res=MIN(res,dp[s][b-]);//记录答案

        for(int v=;v<m;v++)//起点

            for(int i=;i<n;i++)//这是车票

                if(s>>i&)//判断第i个元素是否属于s

                    for(int u=;u<m;u++)//终点

                        if(d[v][u]>=)//使用车票i，从v到u

                            dp[s& ~(<<i)][u]=MIN(dp[s& ~(<<i)][u],dp[s][v]+(double)d[v][u]/t[i]);

    }

    if(res==inf)cout<<"Impossible"<<endl;

    else cout<<res<<endl;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cout<<setiosflags(ios::fixed)<<setprecision();

    while(cin>>n>>m>>p>>a>>b){

        if(!n&&!m)break;

        for(int i=;i<n;i++)cin>>t[i];

        memset(d,-,sizeof d);//距离初始化为-1

        for(int i=;i<p;i++)

        {

            int x,y,z;

            cin>>x>>y>>z;

            x--;

            y--;

            d[x][y]=d[y][x]=z;//保存距离信息，这是无向无环图

        }

        solve();

    }

    return ;

}

巴特西

poj2686 状压dp入门

最新文章

热门文章