最短Hamilton路径

给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n

接下来 n 行每行 n 个整数,其中第i行第j个整数表示点 ij 的距离(记为a[i,j])。

对于任意的 x , y , z ,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

数据范围

1 ≤ n ≤ 20 0 ≤ a[i , j] ≤ 10^7

输入样例:

5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0

输出样例:

18

分析:

NP完全问题 + 状态压缩

按照一般思路是直接DFS,这样的话时间达到了20!,大大超过了限制。

用状态压缩,一个二维数组分别存储当前取的点的状态、当前在哪个点上,数组自身的值为最短的路径值。

这样时间复杂度就到了2^20,在状态转移中每层再耗费20次遍历,最终复杂度为 2^20 × 20 = 2 × 10^7大约等于4亿,相当于4秒的耗时,小于题目的时限7秒。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;
const int N= 20, M = 1 << 20;
int f[M][N],weight[N][N];
int n;
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> weight[i][j];
        }
    }
    memset(f,0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; 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){
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }
    cout << f[(1 << n) -1][n - 1];
    return 0;
}

String类型

有关的头文件有

例题:输入数据的每行包含若干个(至少一个)以空格隔开的整数,输入每行中所有整数之和。只用字符和字符数组。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>

#include <string>

#include <sstream>

using namespace std;
int main() {
    string line;
    while(getline(cin, line)) {
        int sum = 0, x;
        stringstream ss(line);
        while (ss >> x) sum += x;
        cout << sum << "\n";
    }
    return 0;
}

一些函数

sort函数,存在于头文件中,可以给任意对象排序,默认排序从小到大,在需要按照特殊依据进行排序时需要传入额外的比较函数。

lower_bound函数,查找大于或等于x的第一个位置。

unique函数,删除有序数组中的重复元素。

例题:

Raju and Meena love to play with Marbles. They have got a lot of marbles with numbers written on them. At the beginning, Raju would place the marbles one after another in ascending order of the numbers written on them. Then Meena would ask Raju to find the first marble with a certain number. She would count 1…2…3. Raju gets one point for correct answer, and Meena gets the point if Raju fails. After some fixed number of trials the game ends and the player with maximum points wins. Today it’s your chance to play as Raju. Being the smart kid, you’d be taking the favor of a computer. But don’t underestimate Meena, she had written a program to keep track how much time you’re taking to give all the answers. So now you have to write a program,which will help you in your role as Raju.

Input: There can be multiple test cases. Total no of test cases is less than 65. Each test case consists begins with 2 integers: N the number of marbles and Q the number of queries Mina would make. The next N lines would contain the numbers written on the N marbles. These marble numbers will not come in any particular order. Following Q lines will have Q queries. Be assured, none of the input numbers are greater than 10000 and none of them are negative. Input is terminated by a test case where N = 0 and Q = 0.

Output: For each test case output the serial number of the case. For each of the queries, print one line of output. The format of this line will depend upon whether or not the query number is written upon any of the marbles. The two different formats are described below: • ‘x found at y’, if the first marble with number x was found at position y. Positions are numbered 1, 2, . . . , N. • ‘x not found’, if the marble with number x is not present. Look at the output for sample input for details.

Sample Input: 4 1 2 3 5 1 5 5 2 1 3 3 3 1 2 3 0 0

Sample Output: CASE# 1: 5 found at 4 CASE# 2: 2 not found 3 found at 3

需要注意的地方:输入 0 0 的时候结束,对应在代码中的体现在 cin 的时候要 && n来保证程序的结束。用sort(.begain , .end)和lower_bound(.begain , .end , x)先对数组从小到大排序再查找首个大于或等于x的数组值下表,在使用lower_bound函数时将其返回值减去实参数组名得到找到的整型数组下标,此外输出的时候要注意输出格式对应题目要求。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;
const int maxn = 100000;
int main() {
    int n, m, a[maxn], find,found;
    int kase = 0;
    while(cin >> n >> m && n ) {
        cout << "CASE# " << ++kase << ":" <<endl;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a,a + n);
        while(m--) {
            cin >> find;
            found = lower_bound(a, a + n, find) - a;
            if(a[found] == find)
                cout << find << " found at " << found + 1 << endl;
            else
                cout << find << " not found" << endl;
        }
    }
    return 0;
}

关于vector

vector是一个不定长数组,一些操作封装在了该类型内。e.g :.size()读取大小 .resize()改变大小 .push_back()向尾部添加元素 .pop_back()删除最后一个元素。

该类型用vector的方式来声明一个类似于int a[]的整数数组,同样vector类似与string a[]。此外,该类型可以直接赋值,还可以作为函数的参数或者返回值,不需要像传递数组那样永外用一个变量指定元素个数。