精华内容
下载资源
问答
  • 链接传送门 状压dp 我对状态压缩的理解:把当前的情况,转化为一个二进制数(或许有其他形式?暂时还没见到),用二进制的0和1来代表当前的情况 AC代码 #include <bits/stdc++.h> using namespace std;...

    链接传送门
    状压dp
    我对状态压缩的理解:把当前的情况,转化为一个二进制数(或许有其他形式?暂时还没见到),用二进制的0和1来代表当前的情况
    AC代码

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 20, M = 1 << N;
    int dp[M][N];    //一维代表的是当前的状态,二维代表的是最后一个到达的点是n
    int w[N][N];
    int n;
    int main()
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> w[i][j]; //建图
        memset(dp, 0x3f, sizeof(dp));//首先初始化为0x3f
        dp[1][0] = 0; //只有起点的时候是0
        for (int i = 0; i < 1 << n; i++)         //一共有1<<n种走法
        {
            for (int j = 0; j < n; j++)
            {
                if (i >> j & 1) //用二进制下的1表示这个点走过
                {
                    for (int k = 0; k < n; k++)
                    {
                        if (i - (1 << j) >> k & 1)
                            dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
                        /*
                        写一个例子
                        比如 011001   代表的是0 3 4走过的
                             001001   代表的是0 3走过
                             然后从第二个状态到第一个状态差的就是4
                        */
                    }              
                }
            }
        }
        cout << dp[(1 << n) - 1][n - 1] << endl;
    
        return 0;
    }
    
    
    展开全文
  • 最短哈密顿回路,在无向图中由一个顶点出发,不重复的遍历所有顶点,最后回到出发点,找到最短的回路,用C语言实现,
  • 题意:求从点0到点n-1的最短哈密顿路径,即0~n-1这n个点每个点必须且只能经过一次。 起点为0,终点为n-1,问你最短路径长度 题解: 设f[i][j]表示从0开始,途中经过了i这个二进制表示的数中位为1的所有点后,...

    原题链接:https://www.acwing.com/problem/content/description/93/

     

    题意:求从点0到点n-1的最短哈密顿路径,即0~n-1这n个点每个点必须且只能经过一次。

    起点为0,终点为n-1,问你最短路径长度

     

    题解: 设f[i][j]表示从0开始,途中经过了i这个二进制表示的数中位为1的所有点后,到达了j这个点的最短路径

    举个例子i为111001110,那么这时候第1,2,3和6,7,8这6个点就经历过了。这时候到达了j这个点,其中j可能是123678中任意一个

     

    那么我们需要考虑:在到达j这个点之前,到达的点是k,即到达f[i][j]这个状态的时候我们先到达了f[i - (1 << j)][k]这个状态

    那么f[i][j] = f[i - (1 << j)][k] + a[k][j]

     

    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 21;
    int a[N][N];
    int f[1 << N][N];
    int n;
    
    int main()
    {
        scanf("%d", &n);
        
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &a[i][j]);
                
        memset(f, 0x3f, sizeof f);
        f[1][0] = 0;
        
        int len = 1 << n;
        for(int i = 1; i < len; i++)
            for(int j = 0; j < n; j++)
                if(i >> j & 1)//当要到达的点存在,这个状态才会存在
                    for(int k = 0; k < n; k++)
                        if((i - (1 << j)) >> k & 1) //去掉j这个点后,如果k这个点存在,这个状态才会存在
                            f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);
                            
        printf("%d\n", f[(1 << n) - 1][n - 1]);
        
        return 0;
    }

     

     

     

    展开全文
  • 题意:给一副n个点的无向图(完全图),求从点0到n-1的最短哈密顿路径 思路:状压DP入门题,这题的子问题其实是每个点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i个点的时候,所有...

    题意:给一副n个点的无向图(完全图),求从点0到n-1的最短哈密顿路径

    思路:状压DP入门题,这题的子问题其实是每个点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i个点的时候,所有的点的使用状况,先枚举状态,然后枚举当前的点,再在剩下的点中枚举尚未使用过的点,复杂度O(n^2 * 2^n)

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    int a[25][25];
    int dp[22][1<<20];//当前第i个点,20个点的经过状态
    int main()
    {
       int n;
       cin>>n;
       memset(dp,0x3f,sizeof(dp));
       dp[1][1]=0;
       for(int i=1;i<=n;++i)
           for(int j=1;j<=n;++j)
               cin>>a[i][j];
       for(int i=1;i<(1<<n);++i)
       {
           for(int j=1;j<=n;++j)
           {
              if(i&(1<<j-1))
              {
                 for(int k=1;k<=n;++k)
                 {
                    if(!(i&(1<<k-1)))
                        dp[k][i|(1<<k-1)]=min(dp[k][i|(1<<k-1)],dp[j][i]+a[j][k]); 
                 } 
              } 
           } 
       } 
       cout<<dp[n][(1<<n)-1]<<endl;
       return 0; 
    }
    
    展开全文
  • 题目大意:给定一个 N 个点的无向图,点有点权,求从 0 号点走到 N-1 号点的最短哈密顿路径是多少。 题解:由于哈密顿路径的定义是每个顶点必须经过且仅能经过一次,因此,可用当前是否经过了这些点和当前在哪个点来...

    题目大意:给定一个 N 个点的无向图,点有点权,求从 0 号点走到 N-1 号点的最短哈密顿路径是多少。

    题解:由于哈密顿路径的定义是每个顶点必须经过且仅能经过一次,因此,可用当前是否经过了这些点和当前在哪个点来表示出一个状态,则一共有 \(O(n2^n)\) 个状态。考虑转移方式,对于在 j 这个点的情况来说,可以从以下与 j 相邻的节点 k 转移来,k 必须满足在当前状态已经走到。因此,时间复杂度为 \(O(n^22^n)\)

    update at 2019.3.29
    注意,由于状态转移方程为 \[dp[i][S]=min\{dp[k][S']+dis(i,k)\},k\in [1,n],S'\subset S\],从中可以看出 i 的决策是不具有阶段性的,即:i 并不是从小到大进行的,而对于集合来说是从小到大进行转移的,因此应该以走过的点的集合作为阶段,即:集合应该是循环的第一层。今天被这个搞到自闭了。。QAQ

    代码如下

    #include <bits/stdc++.h>
    using namespace std;
    
    int dp[1<<20][20];
    int n,G[20][20];
    
    int main(){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&G[i][j]);
        memset(dp,0x3f,sizeof(dp));
        dp[1][0]=0;
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i>>j&1)
                for(int k=0;k<n;k++)if((i^1<<j)>>k&1)
                    dp[i][j]=min(dp[i][j],dp[i^1<<j][k]+G[k][j]);
        printf("%d\n",dp[(1<<n)-1][n-1]);
        return 0;
    }

    转载于:https://www.cnblogs.com/wzj-xhjbk/p/10552681.html

    展开全文
  • 题目分析:最短哈密顿路径的模板题,比赛的时候为什么没看出来呢。。好像是被 n * m 很小所迷惑了,感觉像是一道搜索题,但想了半天没什么思路就不想做了,赛后回顾一下的时候发现,k 给的特别小,最大只有 11 ,而....
  • 题意:给一副n个点的无向图(完全图),求从点0到n-1的最短哈密顿路径 思路:状压DP入门题,这题的子问题其实是每个点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i个点的时候,所有...
  • 最短哈密顿路径

    2021-12-01 22:38:07
    最短Hamilton路径 给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n...
  • 最短哈密顿路径 给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数n。 接下来n...
  • =200)个顶点坐标,求一个最短哈密顿路径的长度。 解法:求最短哈密顿本身是一个NP问题,可是由于是凸包上,能够利用这个做;有一个性质:凸包上的最短哈密顿路径不会出现交叉。所以能够看出来从一点出发,他...
  • 导入eclipse就可以使用,用两种方式实现了寻找哈密顿路径
  • = 题意翻译: 哈密顿路径:经过图上的每个点一次且仅一次的路径 给你n个点之间的距离,和m个约束关系,约束关系输入为 a b,表示a一定要在b之前先走,求出在这个约束条件下的最短哈密顿路径 思路: 正常的哈密顿路径...
  • 题目大意:求从0开始的最短哈密顿路径,并且要求了某些点的先后顺序 题目分析:哈密顿路径:由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次(百度百科) 既然按照一定的次序求最短路,可以模仿...
  • 给定一张n个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数n。 接下来n行每行n个整数,...
  • hdu3538(最短哈密顿路径)

    千次阅读 2016-07-03 16:41:37
    题意:求从0点开始的最短哈密顿路径,要求某些点必须在某些点之前经过 代码:#include #include #include #include #include using namespace std; const int INF=3000000; int d[25][25],dp[2500000][25],f...
  • 问从1出发的最短哈密顿路径(从起点出发,经过所有的点一次) 概述: 从本质理解状压DP, DP[state] [ u ] 表示已经走过的状态为state , 且当前的节点处于 u ,那么刷表拓展,找出u节点的下一个合法节点,并且...
  • 给定一张 nn 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数nn。 接下来nn行每行nn个...
  • 最短Hamilton路径

    千次阅读 2019-02-06 14:23:07
    给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数n。 接下来 n 行每行n个整数...
  • 最短哈密顿回路(旅行商问题)

    千次阅读 2018-04-20 13:49:13
    哈密顿回路:不重复地经过每个点,并最终能回到起始点的回路 有别于欧拉回路:不重复经过每条边的回路 哈密顿回路是点遍历 旅行商问题:求一条经过图中所有点且边权和最小的回路。 以下解法: 模拟退火 状压dp ...
  • 哈密顿最短路径即为从起点到终点,计算出经过图中所有点的最短路径。(点较少的情况) 简单理解 由于途中点较少,可能会直接想到暴力枚举所有点的全排列,然后计算最短距离,其时间复杂度为 O(n∗n!)O(n * n !)O(n∗...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,678
精华内容 671
关键字:

最短哈密顿路径