0%

19.5.15 Educational CF Round 65 (Div. 2) (4 / 7)

A. Telephone Number

  • 判断下8出现的第一个位置然后剪一下再判断就行了
  • 11打成8wa了一发..
  • ac代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*************************************************************************
> File Name: a.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年05月15日 星期三 22时28分36秒
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define MAXN 200100
using namespace std;
typedef long long ll;
bool book[15];
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
string in;
cin >> in;
memset(book, 0, sizeof(book));
int min8 = 0x3f3f3f3f;
for(int i = 0; i < n; i++){
book[in[i] - '0'] = 1;
if(in[i] == '8'){
min8 = min(min8, i);
}
}
if(!book[8]) {
cout << "NO" << endl;
continue;
}
if(n - min8 >= 11){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}

B. Lost Numbers

  • 第一次做交互体题, 懵逼. 不过看了下别人的代码马上理解是个什么东西了
  • 题意 :
    • 总共有6个数, 每一个可能为4 8 15 16 23 42中的一个, 并且每个数出现仅一次. 四次询问, 每次输出形如? a b, 系统会返回第a个数与第b个数的乘积
    • 按顺序输出这6个数
  • 知道了意思就很好做了, 设这 6 个数为ans[6], 问ans[0] * ans[1], ans[1] * ans[2], ans[2] * ans[3], ans[3] * ans[4]. 然后就可以判断出所有的数了.
  • ac代码
    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    /*************************************************************************
    > File Name: b.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月16日 星期四 10时18分14秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int sum12, sum23, sum34, sum45;
    int ans[6];
    int nums[6] = {4, 8, 15, 16, 23, 42};
    int book[6];
    int main(){
    cout << "? 1 2" << endl;
    cin >> sum12;
    cout << "? 2 3" << endl;
    cin >> sum23;
    cout << "? 3 4" << endl;
    cin >> sum34;
    cout << "? 4 5" << endl;
    cin >> sum45;
    for(int i = 0; i < 6; i++){
    bool flag = 0;
    for(int j = 0; j < 6; j++){
    if(nums[i] * nums[j] == sum12){
    flag = 1;
    book[i]++;
    book[j]++;
    break;
    }
    }
    if(flag) break;
    }
    for(int i = 0; i < 6; i++){
    bool flag = 0;
    for(int j = 0; j < 6; j++){
    if(nums[i] * nums[j] == sum23){
    flag = 1;
    book[i]++;
    book[j]++;
    break;
    }
    }
    if(flag) break;
    }
    for(int i = 0; i < 6; i++){
    if(book[i] == 2){
    ans[1] = nums[i];
    }
    }
    ans[0] = sum12 / ans[1];
    ans[2] = sum23 / ans[1];
    ans[3] = sum34 / ans[2];
    ans[4] = sum45 / ans[3];
    ans[5] = 4 + 8 + 15 + 16 + 23 + 42 - ans[0] - ans[1] - ans[2] - ans[3] - ans[4];
    cout << "! ";
    for(int i = 0; i < 6; i++){
    cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
    }

C. News Distribution

  • 很明显的并查集, 但是重点是时间复杂度的优化, 刚开始朴素写法超时了几次, 后来再unite
  • ac代码
    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    /*************************************************************************
    > File Name: c.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月15日 星期三 22时56分29秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #define MAXN 500500
    using namespace std;
    typedef long long ll;
    int n, m;
    int par[MAXN];
    int hi[MAXN];
    int num[MAXN];//储存集合元素的个数
    void init(int n){
    for(int i = 0; i < n; i++){
    num[i] = 1;
    par[i] = i;
    hi[i] = 0;
    }
    }
    int find(int x){
    if(par[x] == x){
    return x;
    }else{
    return par[x] = find(par[x]);
    }
    }
    void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return ;
    if(hi[x] < hi[y]){
    par[x] = y;
    num[y] += num[x];//合并
    }else{
    par[y] = x;
    if(hi[x] == hi[y]) hi[x]++;
    num[x] += num[y];//合并
    }
    }
    bool same(int x, int y){
    return find(x) == find(y);
    }
    int book[500500];
    bool mark[500500];
    int main(){
    cin >> n >> m;
    init(n);
    for(int i = 0; i < m; i++){
    int ge;
    int in[MAXN];
    scanf("%d", &ge);
    int last, now;
    for(int j = 0; j < ge; j++){
    //if(j) last = now;
    scanf("%d", in + j);
    /*
    if(j){
    if(mark[last - 1] && mark[now - 1]) continue;
    unite(last - 1, now - 1);
    mark[last - 1] = 1;
    mark[now - 1] = 1;
    }
    */
    }
    for(int j = 0; j < ge - 1; j++){
    int a = in[j] - 1;
    int b = in[j + 1] - 1;
    unite(a, b);
    }
    }
    for(int i = 0; i < n; i++){
    int x = find(i);
    printf("%d ", num[x]);
    }
    return 0;
    }

D. Bicolored RBS

  • 思维题, 想出来就很好写了
  • 刚开始用的dfs, 然后超时了几发, 后来经dalao指点, 发现可以遍历一次就出答案
  • 思路 : 从string[1]开始遍历, 如果与上一个字符相同就换颜色涂, 不同就不换颜色涂
  • ac代码
    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
    31
    32
    33
    34
    35
    36
    /*************************************************************************
    > File Name: d2.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月16日 星期四 09时57分33秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #define MAXN 200100
    using namespace std;
    typedef long long ll;
    int n;
    string in;
    bool ans[MAXN];
    int main(){
    cin >> n >> in;
    bool cr = 0;
    ans[0] = cr;
    for(int i = 1; i < n; i++){
    if(in[i] == in[i - 1]) cr = !cr;
    ans[i] = cr;
    }
    for(int i = 0; i < n; i++){
    cout << ans[i];
    }
    cout << endl;
    return 0;
    }

#排列组合以及相关STL总结

相关链接

有关组合数学的公式

  1. 排列公式P(n,r)=n!/r!
  2. 组合公式C(n,r)=n!/(r!*(n-r)!)
    C(n,r)=C(n-1,r)+C(n-1,r-1)
  3. 错排公式
    1
    2
    d[1]=0,d[2]=1
    d[n]=(n-1)*(d[n-1]+d[n-2])
  4. 卡特兰数
    • 前几项 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012…
    • 公式C(n)=C(2n,n)/(n+1)

STL中的全排列函数

  • 函数声明 : #include<algorithm>

    bool next_permutation( iterator start, iterator end);

  • next_permutation()函数功能是输出全部比当前排列大的排列。顺序是从小到大
  • prev_permutation()函数功能是输出全部比当前排列小的排列,顺序是从大到小
  • 复杂度
    • 至多 N/2 次交换,其中 N = std::distance(first, last)
    • 典型实现在排列的整个序列上,平均每次调用使用约 3 次比较和 1.5 次交换
  • 例题 : hdu-1027
  • next_permutation()就可以简单的解决
    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
    31
    32
    33
    34
    35
    36
    37
    /*************************************************************************
    > File Name: p.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月10日 星期五 10时23分37秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int n, m;
    int num[1010];
    int main(){
    while(cin >> n >> m){
    for(int i = 0; i < n; i++){
    num[i] = i + 1;
    }
    m--;
    while(m--){
    next_permutation(num, num + n);
    }
    for(int i = 0; i < n; i++){
    if(i) printf(" ");
    printf("%d", num[i]);
    }
    cout << endl;
    }
    return 0;
    }

STL-map 总结

文档链接

map基本操作

  • 在STL的头文件中<map>中定义了模版类map和multimap,用有序二叉树表存储类型为pair<const Key, T>的元素对序列. 序列中的元素以 const Key 部分作为标识, map 中所有元素的Key值必须是唯一的,multimap 则允许有重复的 Key 值.
  • 可以将map看作是由Key标识元素的元素集合,这类容器也被称为“关联容器”,可以通过一个Key值来快速决定一个元素,因此非常适合于需要按照Key值查找元素的容器.
  • map模版类需要四个模版参数,第一个是键值类型,第二个是元素类型,第三个是比较算子,第四个是分配器类型。其中键值类型和元素类型是必要的.
  • 定义map对象的代码示例:
    1
    map<string, int> m;
  • 基本操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /*  向map中插入元素  */
    // [key]操作是map很有特色的操作,如果在map中存在键值为key的元素对, 则返回该元素对的值域部分,否则将会创建一个键值为key的元素对,值域为默认值。所以可以用该操作向map中插入元素对或修改已经存在的元素对的值域部分.
    m[key] = value;
    m.insert(make_pair(key, value)); // 也可以直接调用insert方法插入元素对,insert操作会返回一个pair,当map中没有与key相匹配的键值时,其first是指向插入元素对的迭代器,其second为true;若map中已经存在与key相等的键值时,其first是指向该元素对的迭代器,second为false。

    /* 查找元素 */
    // 要注意的是,当与该键值相匹配的元素对不存在时,会创建键值为key(当另一个元素是整形时,m[key]=0)的元素对.
    int i = m[key];
    // 如果map中存在与key相匹配的键值时,find操作将返回指向该元素对的迭代器,否则,返回的迭代器等于map的end()(参见vector中提到的begin()和end()操作).
    map<string, int>::iterator it = m.find(key);

    /* 删除元素 */
    // 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数.
    m.erase(key);
    // 删除由迭代器it所指定的元素对,并返回指向下一个元素对的迭代器.
    m.erase(it);

    /* 其他操作 */
    m.size(); // 返回元素个数
    m.empty(); // 判断是否为空
    m.clear(); // 清空所有元素

map的排序

  • 为了实现快速查找, map内部本身就是按序存储的(比如红黑树). 在我们插入<key, value>键值对时, 就会按照key的大小顺序进行存储, 这也是作为key的类型必须能够进行<运算比较的原因. 但有些时候需要用特殊的规则进行排序, 这时可以用vector进行间接地排序

  • map中通过pair储存数据, 所以定义

    1
    2
    3
    4
    map<key, value> m;
    typedef pair<key, value> pa;
    //把m中的值复制到vec中
    vector<pa> vec(m.begin(), m.end());
  • 之后定义排序函数通过vector排序

  • 例题hdu-1236

    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    /*************************************************************************
    > File Name: c.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月06日 星期一 19时40分20秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef pair<string, int> pa;
    int fen[20];
    //定义比较函数
    bool cmp(const pa &a, const pa &b){
    if(a.second != b.second)
    return a.second > b.second;
    else{
    return a.first.compare(b.first) < 0 ? 1 : 0;
    }
    }
    int main(){
    int n, m, g;
    while(scanf("%d", &n) && n){
    scanf("%d %d", &m, &g);
    int ans = 0;
    map<string, int> jifen;
    for(int i = 0; i < m; i++){
    scanf("%d", fen + i + 1);
    }
    for(int i = 0; i < n; i++){
    string hao;
    int num;
    cin >> hao >> num;
    jifen[hao] = 0;
    for(int j = 0; j < num; j++){
    int in;
    scanf("%d", &in);
    jifen[hao] += fen[in];
    }
    if(jifen[hao] >= g){
    ans++;
    }
    }
    cout << ans << endl;
    vector<pa> vec(jifen.begin(), jifen.end());
    // 排序
    sort(vec.begin(), vec.end(), cmp);
    for(pa vecc : vec){
    if(vecc.second >= g)
    cout << vecc.first << " " << vecc.second << endl;
    }
    }
    return 0;
    }

BigInteger

常用操作

进制转换

1
2
3
BigInteger a = BigInteger.ValueOf("1111111");
System.out.println(a.toString(n));
// n == 2 时转二进制 n == 3 时转三进制 以此类推

运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
valueOf(parament); 将参数转换为指定类型
add(); //大数加法
substract(); //减法
multiply(); //乘法
divided(); //相除取整
remainder(); //取余
pow(); //a.pow(b) = a ^ b
gcd(); //最大公约数
abs(); //绝对值
negate(); //取反数
mod(); //a.mod(b) = a % b = a.remainder(b)
max(); min();
public int compareTo(); //比较
boolean equals(); //比较是否相等

BigDecimal

运算

  • BigInteger的差不多

link

带权并查集做法 (向量)

  • 参考博文
  • 带权并查集与普通并查集的区别主要在find()uni()上 在进行两项操作的同时要对节点的权值进行更新, 参考参考博文的做法, 使用了类似向量的思想

变量解释

  • node中
    • per父节点
    • rel与父节点(即向量指向的节点)的关系
      • 0=>同类 1=>被父节点吃 2=>吃父节点
    • high高度, 本题中没有 (至少我的码里没用..)

合并

-假设有 pa, a, pb, b 四个节点, a 与 b 有关系, 具体如图

  • 将 pb 连接到 pa 时侯, 就可以很容易的得到 pa 与 pb 的关系

  • b->pb + pb->pa = b->a + a->pa 推出pb->pa = b->a + a->pa - b->pb
    转化为代码 node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3;

find() (同时压缩路径)

  • 假设有 a, b, c 三个节点, 关系如图

  • 将 c 连接到 a 时

  • c->a = c->b + b->a
    转化为代码node[a].rel = (node[a].rel + node[tmp].rel + 3) % 3;

  • 通过 tmp 进行递归迭代进行路径压缩

code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/**********************************************************
> File Name : poj-1182-jq.cpp
> Author : Wqr_
> Mail : xueduanwei@126.com
> Created Time : 19 03 22 09:57:18
**********************************************************/
// 282ms
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
struct nodep{
int per;
int high;
//0=>同类 1=>被父节点吃 2=>吃父节点
int rel;
}node[50100];
int n, k;
int D[100010];
int X[100010];
int Y[100010];

void init(){
for(int i = 0 ; i < n; i++){
node[i].per = i;
node[i].rel = 0;
}
}


int find(int a){
if(node[a].per == a) return a;
else{
int tmp = node[a].per;
node[a].per = find(node[a].per);
node[a].rel = (node[a].rel + node[tmp].rel + 3) % 3;
return node[a].per;
}
}

void uni(int a, int b, int d){
int pa = find(a);
int pb = find(b);
if(pa == pb) return ;
/*
if(node[pa].high > node[pb].high){
node[pb].per = pa;
node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3;
}else if(node[a].high < node[b].high){
node[a].per = b;
node[pa].rel = (d + node[b].rel - node[a].rel + 3) % 3;
}else{
node[a].per = b;
node[pa].rel = (d + node[b].rel - node[a].rel + 3) % 3;
node[pb].high++;
}
合并树 注意:被 a 吃,所以以 a 的根为父
也就是说, 不能按照白书上介绍的那样进行压缩操作
*/

node[pb].per = pa;
node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3;
}

bool same(int a, int b){
return find(a) == find(b);
}

int getrel(int a, int b){
// 所求为 a => b 的关系
find(a);
find(b);
return (node[a].rel - node[b].rel + 3) % 3;
}
void solve(){
init();
int ans = 0;
for(int i = 0; i < k; i++){
int d = D[i];
int x = X[i] - 1;
int y = Y[i] - 1;
if(d == 2 && x == y){
ans++;
continue;
}
if(x < 0 || x >= n || y < 0 || y >= n){
ans++;
continue;
}

if(same(x, y)){
if(d == 1 && getrel(x, y) != 0) ans++;
if(d == 2 && getrel(x, y) != 2) ans++;
}
uni(x, y, d - 1);
}
printf("%d", ans);
}
int main(){
cin >> n >> k;
for(int i = 0; i < k; i++){
scanf("%d %d %d", D + i, X + i, Y + i);
}
solve();
return 0;
}

白书做法 (分类)

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**********************************************************
> File Name : poj-2236.cpp
> Author : Wqr_
> Mail : xueduanwei@126.com
> Created Time : 19 03 20 21:09:04
**********************************************************/
// 329ms
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int par[150010];
int high[150010];
int D[100010];
int X[100010];
int Y[100010];

int n, k;
void init(int n){
for(int i = 0; i < n; i++){
par[i] = i;
high[i] = 0;
}
}

int find(int a){
if(par[a] == a) return a;
else{
return par[a] = find(par[a]);
}
}

void unite(int a, int b){
a = find(a);
b = find(b);
if(a == b) return ;

if(high[a] > high[b]){
par[b] = a;
}else if(high[a] < high[b]){
par[a] = b;
}else{
par[a] = b;
high[b]++;
}
}

bool same(int a, int b){
return find(a) == find(b);
}

void solve(){
init(n * 3);
int ans = 0;
for(int j = 0; j < k; j++){
int d = D[j];
int x = X[j] - 1;
int y = Y[j] - 1;
if(x < 0 || x >= n || y < 0 || y >= n){
ans++;
continue;
}

if(d == 1){
if(same(x, y + n) || same(x, y + 2 * n)){
ans++;
}else{
unite(x, y);
unite(x + n, y + n);
unite(x + 2 * n, y + 2 * n);
}
}

if(d == 2){
if(same(x, y) || same(x, y + 2 * n)){
ans++;
}else{
unite(x, y + n);
unite(x + n, y + 2 * n);
unite(x + 2 * n, y);
}
}
}
cout << ans << endl;
}

int main(){
cin >> n >> k;
int din, xin, yin;
for(int i = 0; i < k; i++){
scanf("%d %d %d", D + i, X + i, Y + i);
}
solve();
return 0;
}

poj-1860

题目大意

有多个兑换点, 每个兑换点可以兑换两种货币. 假设本来有的货币种类为s, 问能否通过不断兑换最终回到s并且使总金增加

理解

  • 如果存在正权回路则说明可以钱无限增加, 找到正权回路直接输出YES就行了, 否则输出NO

code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**********************************************************
> File Name : poj-1860.cpp
> Author : Wqr_
> Mail : xueduanwei@126.com
> Created Time : 19 03 24 15:43:13
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
struct poin{
int a, b;
double r, c;
}expp[220];
// 刚开始定义的是exp[220], 不知道这是个关键字, 报错了

int nume;
int n, m, s;
double v;
// 到第[]种货币的最大值
double dis[101];
bool bell(){
memset(dis, 0, sizeof(dis));
dis[s] = v;
for(int i = 0; i < n - 1; i++){
bool flag = false;
for(int j = 0; j < nume; j++){
if(dis[expp[j].b] < (dis[expp[j].a] - expp[j].c) * expp[j].r){
dis[expp[j].b] = (dis[expp[j].a] - expp[j].c) * expp[j].r;
flag = true;
}
}
if(!flag) break;
}
for (int j = 0; j < nume; j++) {
if (dis[expp[j].b] < (dis[expp[j].a] - expp[j].c) * expp[j].r) {
return true;
}
}
return false;
}
int main(){
while(cin >> n >> m >> s >> v){
nume = 0;
int exa, exb;
double exra, exca, exrb, excb;
for(int i = 0; i < m; i++){
scanf("%d %d %lf %lf %lf %lf", &exa, &exb, &exra, &exca, &exrb, &excb);
expp[nume].a = exa;
expp[nume].b = exb;
expp[nume].r = exra;
expp[nume++].c = exca;
expp[nume].a = exb;
expp[nume].b = exa;
expp[nume].r = exrb;
expp[nume++].c = excb;
}
if(bell()) printf("YES\n");
else printf("NO\n");
}
return 0;
}

poj-3295

题目大意

有f个农场, 每个农场有n个点m条路, 有w个虫洞, 问针对每个农场能否看到以前的自己

理解

  • 判断是否有负权回路, 有就可以

code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**********************************************************
> File Name : poj-3295.cpp
> Author : Wqr_
> Mail : xueduanwei@126.com
> Created Time : 19 03 24 17:15:01
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#define INF 1<<28
using namespace std;
int n, m, w;
int eee;
struct edge{
int a, b, cost;
}es[10010];

int dis[10010];

bool bell(){
fill(dis, dis + n, INF);
dis[1] = 0;
for(int i = 0; i < n - 1; i++){
bool flag = false;
for(int j = 0; j < eee; j++){
if(dis[es[j].b] > dis[es[j].a] + es[j].cost){
dis[es[j].b] = dis[es[j].a] + es[j].cost;
flag = true;
}
}
if(!flag) break;
}
for (int j = 0; j < eee; j++) {
if (dis[es[j].b] > dis[es[j].a] + es[j].cost) {
return true;
}
}
return false;
}
int main(){
int f;
cin >> f;
while(f--){
eee = 0;
cin >> n >> m >> w;
int a, b, c;
for(int i = 0; i < m; i++){
scanf("%d %d %d", &a, &b, &c);
es[eee].a = a;
es[eee].b = b;
es[eee++].cost = c;
es[eee].a = b;
es[eee].b = a;
es[eee++].cost = c;
}
for(int i = 0; i < w; i++){
scanf("%d %d %d", &a, &b, &c);
es[eee].a = a;
es[eee].b = b;
es[eee++].cost = -c;
}
if(bell()) printf("YES\n");
else printf("NO\n");
}
return 0;
}

前言

1. gcc的安装

  • 输入pkg install clang
  • 这个我不确定对不对了,如果出了错误请按照如下操作

    输入gcc
    会弹出一些信息,其中有一个pkg install ***
    输入就可以了

2. vimrc的配置

  1. 输入命令vim ~/.vimrc

  2. 在vimrc中添加如下代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
nmap <c-c> :w! ~/storage/shared/copy.txt

set tabstop=4
set softtabstop=4
set shiftwidth=4
set autoindent
set cindent
set smarttab
:set ts=4
:set expandtab
:%retab!
syntax on
set laststatus=0
set number
filetype on
set showcmd
if version >= 603
set helplang=cn
set encoding=utf-8
endif
autocmd BufNewFile *.cpp,*.[ch],*.sh,*.java exec ":call SetTitle()"
func SetTitle()
if &filetype == 'sh'
call setline(1,"\#########################################################################")
call append(line("."), "\# File Name: ".expand("%"))
call append(line(".")+1, "\# Author: Wqr_")
call append(line(".")+2, "\# mail: xueduanwei@126.com")
call append(line(".")+3, "\# Created Time: ".strftime("%c"))
call append(line(".")+4, "\#########################################################################")
call append(line(".")+5, "\#!/bin/bash")
call append(line(".")+6, "")
else
call setline(1, "/*************************************************************************")
call append(line("."), " > File Name: ".expand("%"))
call append(line(".")+1, " > Author: Wqr_")
call append(line(".")+2, " > Mail: xueduanwei@126.com ")
call append(line(".")+3, " > Created Time: ".strftime("%c"))
call append(line(".")+4, " ************************************************************************/")
call append(line(".")+5, "")
endif
if &filetype == 'cpp'
call append(line(".")+6, "#include<iostream>")
call append(line(".")+7, "#include<cstdio>")
call append(line(".")+8, "#include<cstring>")
call append(line(".")+9, "#include<string>")
call append(line(".")+10, "#include<vector>")
call append(line(".")+11, "#include<algorithm>")
call append(line(".")+12, "using namespace std;")
call append(line(".")+13, "")
endif
if &filetype == 'c'
call append(line(".")+6, "#include<stdio.h>")
call append(line(".")+7, "")
endif
autocmd BufNewFile * normal G
endfunc
map <c-g> :call CompileRunGcc()<CR>
func! CompileRunGcc()
exec "w"
if &filetype == 'c'
exec "!g++ % -o %<"
exec "! ./%<"
elseif &filetype == 'cpp'
exec "!g++ % -o %<"
exec "! ./%<"
elseif &filetype == 'java'
exec "!javac %"
exec "!java %<"
elseif &filetype == 'sh'
:!./%
endif
endfunc
map <c-d> :call Rungdb()<CR>

func! Rungdb()

exec "w"

exec "!g++ % -g -o %<"

exec "!gdb ./%<"

endfunc
autocmd FileType c,cpp map <buffer> <leader><space> :w<cr>:make<cr>
set completeopt=preview,menu

"允许插件
filetype plugin on
"共享剪贴板

set clipboard+=unnamed
set autowrite
set enc=utf-8
set fencs=utf-8,ucs-bom,shift-jis,gb18030,gbk,gb2312,cp936
"语言设置

set langmenu=zh_CN.UTF-8

set helplang=cn
filetype plugin on
filetype indent on
set iskeyword+=_,$,@,%,#,-
:inoremap ( ()<ESC>i

:inoremap ) <c-r>=ClosePair(')')<CR>

:inoremap { {<CR>}<ESC>O

:inoremap } <c-r>=ClosePair('}')<CR>

:inoremap [ []<ESC>i

:inoremap ] <c-r>=ClosePair(']')<CR>

:inoremap " ""<ESC>i
:inoremap ' ''<ESC>i
function! ClosePair(char)
if getline('.')[col('.') - 1] == a:char
return "\<Right>"
else
return a:char
endif
endfunction
filetype plugin indent on
"打开文件类型检测, 加了这句才可以用智能补全

set completeopt=longest,menu
  1. 解释

    • 我在根目录下创建了一个名为copy.txt的文件,用来作为系统间复制的桥梁,这个copy.txt需要手动进行创建

      • <c-c>代表ctrl + c 以此类推
      • 在此操作后会执行命令:w! ~/storage/shared/copy.txt将文件保存到copy.txt中
      • 需要注意的是,执行此操作需要文件有相应的权限,使用chmod指令操作,由于条件比较复杂,具体请自行百度
    • ctrl + g可以启用gcc进行编译,ctrl + d可以启用gdb进行调试

    • 预添加了头文件和一些信息,可以按需求修改

3. 插件的安装(可跳过)

1. 安装vundle

  1. link

  2. 首先cd ~/.vim如果没有此文件夹则使用mkdir创建一个

  3. 在.vim文件夹中创建文件夹bundlemkdir bundle

  4. 执行git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim

    • 可能没有git 按提示操作即可
  5. 在.vimrc中前添加如下代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
set nocompatible              " be iMproved, required
filetype off " required

" set the runtime path to include Vundle and initialize
set rtp+=~/.vim/bundle/Vundle.vim
call vundle#begin()
" alternatively, pass a path where Vundle should install plugins
"call vundle#begin('~/some/path/here')

" let Vundle manage Vundle, required
Plugin 'VundleVim/Vundle.vim'

" The following are examples of different formats supported.
" Keep Plugin commands between vundle#begin/end.
" plugin on GitHub repo
Plugin 'tpope/vim-fugitive'
" plugin from http://vim-scripts.org/vim/scripts.html
" Plugin 'L9'
" Git plugin not hosted on GitHub
Plugin 'git://git.wincent.com/command-t.git'
" git repos on your local machine (i.e. when working on your own plugin)
Plugin 'file:///home/gmarik/path/to/plugin'
" The sparkup vim script is in a subdirectory of this repo called vim.
" Pass the path to set the runtimepath properly.
Plugin 'rstacruz/sparkup', {'rtp': 'vim/'}
" Install L9 and avoid a Naming conflict if you've already installed a
" different version somewhere else.
" Plugin 'ascenator/L9', {'name': 'newL9'}

" All of your Plugins must be added before the following line
call vundle#end() " required
filetype plugin indent on " required
" To ignore plugin indent changes, instead use:
"filetype plugin on
"
" Brief help
" :PluginList - lists configured plugins
" :PluginInstall - installs plugins; append `!` to update or just :PluginUpdate
" :PluginSearch foo - searches for foo; append `!` to refresh local cache
" :PluginClean - confirms removal of unused plugins; append `!` to auto-approve removal
"
" see :h vundle for more details or wiki for FAQ
" Put your non-Plugin stuff after this line

2. 安装缩进可视化插件

  1. link
  2. 将文件下载并解压到~/.vim/bundle/目录下
  3. 在前面刚添加的代码块中添加Plugin 'Yggdroot/indentLine'
  4. 在前面添加的代码块后添加let g:indentLine_color_term = 239

  • WSL 通过 clip.exe 可以与 windows 的剪切板连接

  • 通过指令

    1
    :w !clip.exe
  • 通过 vim 的 nmap 可以使用快捷键快速操作

  • 在~/.vimrc中添加

1
namp <c-c> :w !clip.exe
  • 也可以使用同样的方式仅复制一部分内容

前言

  • 思路来源, 这篇文章里介绍的真的是非常详细, 文章中有大连理工大学的pdf, 也可也学到很多

  • 蚁群算法属于智能算法, 并不一定收敛到最优解, 但对75点一下规模的问题能很好的解决

  • 代码参考

思路

  • tsp问题的思路在前言中的文章里已经有了详细的介绍, 所以只介绍我解决不闭合tsp问题的思路

tsp问题的解决

  • 原理见前言文章与code, 仅展示下结果和逻辑图

  • 30个点感觉并不是很好

  • 50点

不闭合tsp问题的解决

  • 与tsp问题类似, 但主要差别只遍历所有的点但不返回原点.
  1. 第一阶段

    1. 在随机的城市生成蚂蚁, 蚂蚁的总数量与城市数量相等
    2. 每一只蚂蚁通过由信息素与能见度共同决定的规则产生前往不同城市的概率, 并以这个概率随机决定下一个城市
    3. 所有蚂蚁回到原点后更新每条路径上的信息素含量
    4. 达到遍历次数后进入第二阶段
  2. 第二阶段

    1. 在随机的城市生成SUPER蚂蚁, SUPER蚂蚁的总数量与城市数量相等
    2. 每一只SUPER蚂蚁通过由信息素与能见度共同决定的规则产生前往不同城市的概率, 并以这个概率随机决定下一个城市
    3. 所有SUPER蚂蚁遍历过除了不闭合tsp问题的起点外的所有的点前往不闭合tsp问题的起点
    4. 计算并不断更新最短路径的SUPER蚂蚁
    5. 达到迭代次数后输出最短路径的SUPER蚂蚁
    • 第一阶段
    • 第二阶段
  • 与简单贪心的比较

    • 30 点
    • 50 点
  • code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
/*************************************************************************
> File Name: YiQun_Tsp.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: Sun Oct 14 22:56:12 2018
************************************************************************/

// 这个是返回的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define random(x)(rand()%x)
const int NUM = 30; // 城市的数量以及蚂蚁的数量
const int ANT_NUM = NUM; // 蚂蚁的数量
const int CITY_NUM = NUM; // 城市
double dis[NUM][NUM];
double info[NUM][NUM];
const double mmax = 1 << 21;
double tanXindis;

#define TNUM 2000
#define ALPHA 1
#define BETA 4

//返回指定范围内的随机整数
int rnd(int nLow, int nUpper)
{
return nLow + (nUpper - nLow)*rand() / (RAND_MAX + 1);
}

//返回指定范围内的随机浮点数
double rnd(double dbLow, double dbUpper)
{
double dbTemp = rand() / ((double)RAND_MAX + 1.0);
return dbLow + dbTemp * (dbUpper - dbLow);
}

// 蚁群的语句

struct Ant
{

int Path[CITY_NUM]; //路径顺序
double length; //路径长度
int visit[CITY_NUM]; //记录城市是否被访问过
int now; //当前城市
int visitNo; //第几个城市
//初始化
void Init()
{
memset(visit, 0, sizeof(visit));
length = 0;
now = rnd(0, CITY_NUM);//随机选择一个出发城市
Path[0] = now;
visit[now] = 1;
visitNo = 1;
}
//选择下一个城市
int chooseNextCity()
{
int next = -1; //下一个城市的编号
//计算当前城市和没去过的城市之间的信息素总和
double dbTotal = 0.0;
double gaiLv[CITY_NUM]; //各个城市被选中的概率
for (int i = 0; i < CITY_NUM; i++)
{
if (!visit[i])
{
gaiLv[i] = pow(info[now][i], ALPHA)
*pow(1.0 / dis[now][i], BETA);
dbTotal += gaiLv[i];
}
else
{
gaiLv[i] = 0;
}
}
//进行轮盘赌博 (随缘
double dbTemp = 0.0;
if (dbTotal > 0.0)
{
dbTemp = rnd(0.0, dbTotal);
for (int i = 0; i < CITY_NUM; i++)
{
if (!visit[i])
{
dbTemp -= gaiLv[i];
if (dbTemp < 0.0)
{
next = i;
break;
}
}
}
}

// 如果信息素含量很小, 就选出现的第一个

if (next == -1)
{
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i])
{
next = i;
break;
}
}
}

return next;
}

void Move()
{
int next = chooseNextCity();
Path[visitNo] = next;
visit[next] = 1;
now = next;
// 计算新的距离
length += dis[Path[visitNo - 1]][Path[visitNo]];
visitNo++;

}

// 搜索
void Search()
{
Init();
// 经过所有城市
while (visitNo < CITY_NUM)
{
Move();
}
// 回到起始点
length += dis[Path[CITY_NUM - 1]][Path[0]];
}
};


struct TSP
{
Ant ants[ANT_NUM]; //一群蚂蚁
Ant bestAnt; // 路径最短的蚂蚁
void Init()
{
//初始化环境信息素
for (int i = 0; i < CITY_NUM; i++)
{
for (int j = 0; j < CITY_NUM; j++)
{
info[i][j] = ANT_NUM * 15 / tanXindis;
}
}
}

void Updateinfo()
{
double tmpinfo[CITY_NUM][CITY_NUM];
memset(tmpinfo, 0, sizeof(tmpinfo));
int m = 0;
int n = 0;
//遍历每只蚂蚁
for (int i = 0; i < ANT_NUM; i++) {
for (int j = 1; j < CITY_NUM; j++)
{
m = ants[i].Path[j];
n = ants[i].Path[j - 1];
tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
tmpinfo[m][n] = tmpinfo[n][m];
}
//最后城市和开始城市之间的信息素
n = ants[i].Path[0];
tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
tmpinfo[m][n] = tmpinfo[n][m];
}

//更新环境信息素
for (int i = 0; i < CITY_NUM; i++)
{
for (int j = 0; j < CITY_NUM; j++) {
//最新的环境信息素 = 留存的信息素 + 新留下的信息素
info[i][j] = info[i][j] * 0.5 + tmpinfo[i][j];

}
}
}
//寻找路径,迭代TNUM次
void Search()
{
bestAnt.length = 1 << 21;
for (int i = 0; i < TNUM; i++) {
for (int j = 0; j < ANT_NUM; j++) {
ants[j].Search();
}
for (int j = 0; j < ANT_NUM; j++) {
if (bestAnt.length > ants[j].length) {
bestAnt = ants[j];
}
}
Updateinfo();
}

for (int i = 0; i < CITY_NUM; i++) {
if (i) cout << "->";
cout << bestAnt.Path[i];
}
cout << "->" << bestAnt.Path[0];
cout << endl;
cout << "距离为 : ";
cout << bestAnt.length << endl;
}
};



// 贪心法的语句
double TanXin(int from, int* visit, double sum, int* shunXv, int pointNum) {
int flag = true;
for (int i = 0; i < NUM; i++) {
if (visit[i] == 0) {
flag = false;
break;
}
}

if (flag) return sum;

double min = 1000000;
int to;
for (int i = 0; i < NUM; i++) {
if (dis[from][i] < min && visit[i] == 0) {
min = dis[from][i];
to = i;
}
}
sum += dis[from][to];
visit[to] = 1;
shunXv[pointNum++] = to;
return TanXin(to, visit, sum, shunXv, pointNum);
}

double qiujv(int x1, int y1, int x2, int y2) {
return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}

struct point {
int x;
int y;
};

// 主函数
int main() {
// fanWei 代表范围
// chuShi 代表起始位置, 即0
int fanWei;
int chuShi = 0;
cout << "请输入范围 : ";
cin >> fanWei;
point point[NUM];
for (int i = 0; i < NUM; i++) {
point[i].x = random(fanWei);
point[i].y = random(fanWei);
}
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
dis[i][j] = qiujv(point[i].x, point[i].y, point[j].x, point[j].y);
}
}
double min = 100000; // 最小值
int to; //要去的
double sum = 0; //总数
int shunXv[NUM] = { 0 }; // 顺序
int visit[NUM] = { 0 }; // 储存访问过的点
for (int i = 1; i < NUM; i++) {
if (dis[0][i] < min) {
min = dis[0][i];
to = i;
}
}
sum += dis[0][to];
shunXv[1] = to;
visit[0] = 1;
visit[to] = 1;
tanXindis = TanXin(to, visit, sum, shunXv, 2);
tanXindis += dis[shunXv[49]][0];
cout << endl;
cout << "*********** 贪心的结果 **********" << endl;
for (int i = 0; i < NUM; i++) {
if (i) cout << "->";
cout << shunXv[i];
}
cout << "->" << 0;
cout << endl;
cout << "距离为 : " << tanXindis << endl;
cout << endl;
cout << "*********** 蚁群的结果 **********" << endl;
TSP tsp;
tsp.Init();
tsp.Search();
return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
/*************************************************************************
> File Name: YiQun.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: Sun Oct 14 22:56:12 2018
************************************************************************/
// 这个是不返回起点的
#include"pch.h"
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define random(x)(rand()%x)
const int NUM = 30; // 城市的数量以及蚂蚁的数量
const int ANT_NUM = NUM; // 蚂蚁的数量
const int CITY_NUM = NUM; // 城市
double dis[NUM][NUM];
double info[NUM][NUM];
const double mmax = 1 << 21;
double tanXindis;

#define TNUM 2000
#define ALPHA 1
#define BETA 4

//返回指定范围内的随机整数
int rnd(int nLow, int nUpper)
{
return nLow + (nUpper - nLow)*rand() / (RAND_MAX + 1);
}

//返回指定范围内的随机浮点数
double rnd(double dbLow, double dbUpper)
{
double dbTemp = rand() / ((double)RAND_MAX + 1.0);
return dbLow + dbTemp * (dbUpper - dbLow);
}

// 蚁群的语句

struct Ant
{

int Path[CITY_NUM]; //路径顺序
double length; //路径长度
int visit[CITY_NUM]; //记录城市是否被访问过
int now; //当前城市
int visitNo; //第几个城市
//初始化
void Init()
{
memset(visit, 0, sizeof(visit));
length = 0;
now = rnd(1, CITY_NUM);//随机选择一个除0的城市出发城市
Path[0] = now;
visit[now] = 1;
visitNo = 1;
}
//选择下一个城市
int chooseNextCity()
{
int next = -1; //下一个城市的编号
//计算当前城市和没去过的城市之间的信息素总和
double dbTotal = 0.0;
double gaiLv[CITY_NUM]; //各个城市被选中的概率
// 因为0点作为起点, 所以不计入循环
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i])
{
gaiLv[i] = pow(info[now][i], ALPHA)
*pow(1.0 / dis[now][i], BETA);
dbTotal += gaiLv[i];
}
else
{
gaiLv[i] = 0;
}
}
//进行轮盘赌博 (随缘
double dbTemp = 0.0;
if (dbTotal > 0.0)
{
dbTemp = rnd(0.0, dbTotal);
// 因为0点作为起点, 所以不计入循环
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i])
{
dbTemp -= gaiLv[i];
if (dbTemp < 0.0)
{
next = i;
break;
}
}
}
}

// 如果信息素含量很小, 就选出现的第一个

if (next == -1)
{
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i])
{
next = i;
break;
}
}
}

return next;
}

void Move()
{
int next = chooseNextCity();
Path[visitNo] = next;
visit[next] = 1;
now = next;
// 计算新的距离
length += dis[Path[visitNo - 1]][Path[visitNo]];
visitNo++;

}

// 搜索
void Search()
{
Init();
// 经过除去零点的所有城市
while (visitNo < CITY_NUM - 1)
{
Move();
}
// 回到0点
Path[CITY_NUM - 1] = 0;
visit[0] = 1;
length += dis[Path[CITY_NUM - 1 - 1]][Path[CITY_NUM - 1]];
}

};

// 从零点出发的超级蚂蚁
struct SuperAnt {

int Path[CITY_NUM]; //路径顺序
double length; //路径长度
int visit[CITY_NUM]; //记录城市是否被访问过
int now; //当前城市
int visitNo; //第几个城市
//初始化
void Init()
{
memset(visit, 0, sizeof(visit));
length = 0;
now = 0; // 以0为起始城市
Path[0] = now;
visit[now] = 1;
visitNo = 1;
}

int chooseNextCity()
{
int next = -1;
double dbTotal = 0.0;
double gaiLv[CITY_NUM];
// 因为 0 已经被选中 , 不再重复选择
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i])
{
gaiLv[i] = pow(info[now][i], ALPHA)
*pow(1.0 / dis[now][i], BETA);
dbTotal += gaiLv[i];
}
else
{
gaiLv[i] = 0;
}
}
//进行轮盘赌博 (随缘
double dbTemp = 0.0;
if (dbTotal > 0.0)
{
dbTemp = rnd(0.0, dbTotal);
// 因为 0 已经被选中 , 不再重复选择
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i])
{
dbTemp -= gaiLv[i];
if (dbTemp < 0.0)
{
next = i;
break;
}
}
}
}

if (next == -1)
{
for (int i = 1; i < CITY_NUM; i++)
{
if (!visit[i]) //城市没去过
{
next = i;
break;
}
}
}
return next;
}

void Move()
{
int next = chooseNextCity();
Path[visitNo] = next;
visit[next] = 1;
now = next;
length += dis[Path[visitNo - 1]][Path[visitNo]];
visitNo++;

}
//搜索
void Search()
{
Init();
// 让超级蚂蚁经过所有城市
while (visitNo < CITY_NUM)
{
Move();
}
}
};

struct TSP
{
Ant ants[ANT_NUM]; //一群蚂蚁
SuperAnt SuperAnts[ANT_NUM]; //一群超级蚂蚁
SuperAnt bestSuperAnt; // 路径最短的超级蚂蚁
void Init()
{
//初始化环境信息素
for (int i = 0; i < CITY_NUM; i++)
{
for (int j = 0; j < CITY_NUM; j++)
{
info[i][j] = ANT_NUM * 15 / tanXindis;
}
}
}

void Updateinfo()
{
//puts("update info");
double tmpinfo[CITY_NUM][CITY_NUM];
memset(tmpinfo, 0, sizeof(tmpinfo));
int m = 0;
int n = 0;
//遍历每只蚂蚁
for (int i = 0; i < ANT_NUM; i++) {
//puts("");
for (int j = 1; j < CITY_NUM; j++)
{
m = ants[i].Path[j];
n = ants[i].Path[j - 1];
//printf("%d %d\n", m, n);
tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
tmpinfo[m][n] = tmpinfo[n][m];
}
//最后城市和开始城市之间的信息素
n = ants[i].Path[0];
tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
tmpinfo[m][n] = tmpinfo[n][m];
}

//更新环境信息素
for (int i = 0; i < CITY_NUM; i++)
{
for (int j = 0; j < CITY_NUM; j++) {
//最新的环境信息素 = 留存的信息素 + 新留下的信息素
info[i][j] = info[i][j] * 0.5 + tmpinfo[i][j];

}
}
}
//寻找路径,迭代TMAC次
void Search()
{

for (int i = 0; i < TNUM; i++) {
for (int j = 0; j < ANT_NUM; j++) {
ants[j].Search();
}
//更新环境信息素
Updateinfo();
}
bestSuperAnt.length = 1 << 21;
// 从起点出发多只蚂蚁
for (int j = 0; j < TNUM; j++) {
for (int i = 0; i < ANT_NUM; i++) {
SuperAnts[i].Search();
if (SuperAnts[i].length < bestSuperAnt.length) {
bestSuperAnt = SuperAnts[i];
}
}

}
for (int i = 0; i < CITY_NUM; i++) {
if (i) cout << "->";
cout << bestSuperAnt.Path[i];
}
cout << endl;
cout << "距离为 : ";
cout << bestSuperAnt.length << endl;
}
};



// 贪心法的语句
double TanXin(int from, int* visit, double sum, int* shunXv, int pointNum) {
int flag = true;
for (int i = 0; i < NUM; i++) {
if (visit[i] == 0) {
flag = false;
break;
}
}

if (flag) return sum;

double min = 1000000;
int to;
for (int i = 0; i < NUM; i++) {
if (dis[from][i] < min && visit[i] == 0) {
min = dis[from][i];
to = i;
}
}
sum += dis[from][to];
visit[to] = 1;
shunXv[pointNum++] = to;
return TanXin(to, visit, sum, shunXv, pointNum);
}

double qiujv(int x1, int y1, int x2, int y2) {
return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}

struct point {
int x;
int y;
};

// 主函数
int main() {
// fanWei 代表范围
// chuShi 代表起始位置, 即0
int fanWei;
int chuShi = 0;
cout << "请输入范围 : ";
cin >> fanWei;
point point[NUM];
for (int i = 0; i < NUM; i++) {
point[i].x = random(fanWei);
point[i].y = random(fanWei);
}
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
dis[i][j] = qiujv(point[i].x, point[i].y, point[j].x, point[j].y);
}
}
double min = 100000; // 最小值
int to; //要去的
double sum = 0; //总数
int shunXv[NUM] = { 0 }; // 顺序
int visit[NUM] = { 0 }; // 储存访问过的点
for (int i = 1; i < NUM; i++) {
if (dis[0][i] < min) {
min = dis[0][i];
to = i;
}
}
sum += dis[0][to];
shunXv[1] = to;
visit[0] = 1;
visit[to] = 1;
tanXindis = TanXin(to, visit, sum, shunXv, 2);
cout << endl;
cout << "*********** 贪心的结果 **********" << endl;
for (int i = 0; i < NUM; i++) {
if (i) cout << "->";
cout << shunXv[i];
}
cout << endl;
cout << "距离为 : " << tanXindis << endl;
cout << endl;
cout << "*********** 蚁群的结果 **********" << endl;
TSP tsp;
tsp.Init();
tsp.Search();
return 0;
}

poj-2253

题意

  • 复制一下别人的题意,有两只青蛙和若干块石头,现在已知这些东西的坐标,两只青蛙A坐标和青蛙B坐标是第一个和第二个坐标,现在A青蛙想要到B青蛙那里去,并且A青蛙可以借助任意石头的跳跃,而从A到B有若干通路,问从A到B的所有通路上的最大边

  • 从a到b有n条路径, 寻找n条路经中边最大长度最小的

  • code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**********************************************************
> File Name : 2253.cpp
> Author : Wqr_
> Mail : xueduanwei@126.com
> Created Time : 19 03 19 18:47:31
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#define INF 1<<28
using namespace std;
typedef pair<int , int> point;
point ps[250];
int n;
double d[250];
bool used[250];
double map[250][250];
void getdis(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = INF;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j){
map[i][j] = 0;
continue;
}else{
double dis;
dis = sqrt(pow((double)(ps[i].first - ps[j].first), 2) + pow((double)(ps[i].second - ps[j].second), 2));
map[i][j] = dis;
map[j][i] = dis;
}
}
}
}
void diji(int f){
fill(d, d + n, INF);
memset(used, 0, sizeof(used));
d[f] = 0;
while(true){
int v = -1;
double mind = INF;
for(int u = 0; u < n; u++){
if(!used[u] && (v == - 1 || d[u] < mind)){
v = u;
mind = d[u];
}
}
if(v == -1) break;
used[v] = 1;
for(int u = 0; u < n; u++){
// 更新的是f号石头到u号石头最长边中的最小边
d[u] = min(d[u], max(d[v],map[v][u]));
}
}
}
int main(){
int kase = 0;
while(cin >> n){
if(n == 0) break;
int a, b;
for(int i = 0; i < n; i++){
cin >> a >> b;
ps[i].first = a;
ps[i].second = b;
}
getdis();
diji(0);
printf("Scenario #%d\n", ++kase);
printf("Frog Distance = %.3f", d[1]);
printf("\n");
printf("\n");
}
return 0;
}

poj-1797

题意

  • 上一个是找所有路径中最长路径最短的, 这个是找所有路径中最短路径最长的

  • code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**********************************************************
> File Name : 1797.cpp
> Author : Wqr_
> Mail : xueduanwei@126.com
> Created Time : 19 03 19 20:58:42
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#include <queue>
#define INF 1<<28
#define MINF -1
using namespace std;
int map[1050][1050];
int book[1050];
int n, k;
int d[1050];
void diji(){
for(int i = 0; i < n; i++){
d[i] = map[0][i];
book[i] = 0;
}
d[0] = 0;
for(int i = 0; i < n; i++){
int maxd = -1;
int t;
for(int j = 0; j < n; j++){
if(!book[j] && d[j] > maxd){
maxd = d[j];
t = j;
}
}
book[t] = 1;
for(int j = 1; j < n; j++){
if(!book[j] && d[j] < min(d[t], map[t][j])){
d[j] = min(d[t], map[t][j]);
}
}
}
}
int main(){
int kase = 0;
int num;
cin >> num;
while(num--){
cin >> n >> k;
int a, b, c;
memset(map, -1, sizeof(map));
for(int i = 0; i < k; i++){
cin >> a >> b >> c;
map[a - 1][b - 1] = c;
map[b - 1][a - 1] = c;
}
diji();
/*
for(int i = 0; i < n; i++){
cout << d[i] << " ";
}
*/
printf("Scenario #%d:\n", ++kase);
printf("%d\n\n", d[n - 1]);
}
return 0;
}