题目描述

原题地址：A1150 Travelling Salesman Problem

解题思路

• 用一个二维数组存储两个城市间的距离，如不存在这样的边，则距离为 0.
• 遍历每条路径，判断是否存在这样的边，如果存在，累加距离，同时更新城市访问次数。如果不存在，则修改标记另 flag = -1，表示不构成一个 cycle 并且无法计算距离。
• 判断路径的首尾城市是否一致，不一致则不能构成 cycle，修改对应标记。
• 遍历访问数组，根据所有城市是否只访问一次，判断是否为 simple TS cycle ，修改对应标记。
• 更新最短路径距离以及对应路径序号。

易错点：

• 因为起点和终点是同一个城市，对应计数值会多 1，因此需要修正。

也许陌生的知识点

• vector<int> path(p);
  • 创建了一个指定长度为 p 的数组。
  • 所需头文件：vector

代码示例：

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

#include <cstdio>
#include <vector>
using namespace std;
int main(){
  int N, M, K, G[202][202] = {{0}};
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++){
    int c1, c2, d;
    scanf("%d %d %d", &c1, &c2, &d);
    G[c1][c2] = d;
    G[c2][c1] = d;
  }
  scanf("%d", &K);
  int min_id = -1, min_dis = -1;
  for(int i = 1; i <= K; i++){
    int p, vis[202] = {0}, total = 0, flag = 1;
    scanf("%d", &p);
    vector<int> path(p);
    for(int j = 0; j < p; j++){
      scanf("%d", &path[j]);
      vis[path[j]]++;
      if(j != 0) {
        if(G[path[j]][path[j-1]] == 0) flag = -1;// not a cycle
        else total += G[path[j]][path[j-1]];
      }
      if(j == p-1 && flag > 0){
        if(path[j] != path[0]) flag = -2;// not a cycle
        else vis[path[j]]--;
      }
    }
    for(int j = 1; flag > 0 && j <= N; j++){
      if(vis[j] == 0) flag = -2;// not TS cycle
      if(vis[j] > 1) flag = 2; // TS cycle
    }
    printf("Path %d: ", i);
    if(flag == 1) printf("%d (TS simple cycle)\n", total);
    else if(flag == 2) printf("%d (TS cycle)\n", total);
    else if(flag == -2) printf("%d (Not a TS cycle)\n", total);
    else if(flag == -1) printf("NA (Not a TS cycle)\n");
    if(min_dis == -1 || (flag > 0 && min_dis > total)){
      min_dis = total;
      min_id = i;
    }
  }
  printf("Shortest Dist(%d) = %d\n", min_id, min_dis);
  return 0;
}

在微博上看到有人写出充满想象力的很可爱的诗句，觉得也太棒了吧，原来诗也可以这样写，想学！

在推特上看到一名日本的年轻画家的画作，觉得画面也好情感表达也好想象力也好，都太精彩了吧，我也想尝试，将自己脑海里的画面表达出来！

前两天看星际迷航，知道了克林贡语，是制作组特意为了剧里的外星人创造的语言，甚至提供了该剧的克林贡语字幕。而且克林贡字典已经卖出超过 25 万本，Google 搜索引擎还有克林贡语的版本，多邻国甚至提供了该语种的课程。心想，能够把科幻周边发展到这份上，也太酷了吧！想学！

这两天看 My Brilliant Friend ，被 Lila 的气质吸引，感叹她们之间微妙的友谊，还觉得意大利语怎么这么好听，想学！

诸如此类还有很多，这就是我的日常，每隔几个月就会打开一个新世界的大门。

即便绝大多数时间我都是独自呆着，但是我完全不会感觉到所谓无聊和寂寞，因为有趣的事物是如此之多。我会对一切我未知的事物产生好奇，想要去尝试，去了解，想去学习一切我认为很酷的事情。

当然，我对于“酷”的定义与常人不太一样，我认为只要是我觉得有趣的就是酷的。比如我觉得看很多书的人很酷，我觉得写诗的人很酷，能画出好看的画的人很酷，能拍出好看照片的人很酷，能拍出好看的电影和电视剧的人很酷，能写出很多优秀软件的人很酷，能说出新颖观点的人很酷，愿意自由表达自己想法的人很酷，愿意挑战权威的人很酷。也许其他人不一定这么想，但我觉得自己也很酷。

刚进大学的时候我也是充满热情，后来在环境的潜移默化中，老师的照本宣科中，杂七杂八的毫无意义的管理条例下，热情逐渐丧失殆尽。

我可以毫不负责任地说，中国普通大学就是扼杀学生好奇心和学习热情的地方，那不是教育，不过是换一个地方继续管理。 在我看到所谓中国顶尖高校面对类似年初的沈阳事件后的做派，看到北大对于那些敢于站出来为工人维权的北大学子的打压，取缔马会，就觉得，呵，所谓名校也不过如此，同样乌烟瘴气。当最应当倡导自由和正义的大学校园中不允许出现自由的时候，我就已经对这类学校非常失望了。

毕业之后的这几个月，有充足的时间面对自己之后，我又逐渐找回了自我，找回了那份原本属于自己的好奇心，那份对于未知事物的热情，探索的欲望，尝试的动力。我想去看更大的世界，想表达自我。

我时不时会写点什么，80% 是为了表达， 20% 是为了交流。不是为了标新立异特立独行，只是有时候一些想法若是不记录下来，就会一直萦绕在脑海中，一天两天，一周两周，久久不能散去。想交流，又害怕交流，害怕自己不知道如何回应。

我认为表达自我不一定要拘泥于某种形式，有时候我用文字，有时候是绘画，还有摄影，也尝试写诗，以及写程序，未来也可能去拍一些几分钟的视频，只是想用最合适的方式、更能传达内心的想法的方式去表达。不一定要被多少人看到，但还是至少会希望有那么几个观众。

我从小写作文就拿不到高分，也没学过画画，刚开始折腾摄影，但是我一点也不害怕去尝试，不害怕被笑话，因为我的目的更多地是在于表达，而不是表现。说实话，我这个只要不讲话就没有人会注意到我的人，存在感极低的人，能被看到就很难得了。也正因为存在感低，没有出众的才华和外貌，也没有一大堆朋友推不掉的聚会，没有多余的关注，我获得了比其他人更大的自由，能够自由地行动和思考。

我自己购买 VPS 搭建 VPN ，这样我就能看到一个更大更精彩的世界。我看教程学习搭建博客，给博客添加小功能并搭建图床，这样我就能随心所欲地书写，不用考虑敏感词不需要担心被删贴被封号。我学习数据科学，机器学习，准备当数据方向的程序员，计算机是万能工具，有了它我就能做到很多原来不能做的事。

我想知道世界是如何运转的，为什么我们看到的世界是这个样子，想知道外星人到底存不存在，想知道马斯克是不是真的会移民去火星；想知道不同的文化是如何形成的，不同的制度是怎样演变的，贸易到底在国家之间扮演着怎样的角色，为什么会有战争，黑市到底是怎样形成的，为什么大多数历史时期女性地位都处于弱势常常被压迫；想知道人类为什么有喜怒哀乐，性格到底是天生因素比较多还是后天影响比较多，基因到底有哪些奥妙，为什么有婚姻以及婚姻制度是否合理，为什么有如此多的性倾向，福柯的书里到底说了些什么……

因为好奇，因为想知道，这些是我活下去的动力，所以我想尽量活得久一点，知道的就能多一点。

我对社会很绝望，每天看那些社会新闻，除了难过和愤怒我不知道自己还能做什么。为什么还有如此多的人在受不合理的压迫，为什么他们还没有等到属于他们的正义降临，为什么人性可以如此邪恶，为什么他们可以喝人血可以喝得理所应当，为什么那些自己的血正在被人喝着的人还要咒骂那些不想喝血并且呼吁大家不要喝的人，为什么被统治者被训练成为了动不动就要站在统治者角度思考问题的人。我很难过，我很愤怒，我还想知道这些问题的答案。

人类就是矛盾的集合体。我对社会很绝望，但仍然可以对生活对世界充满热情，这是我在这个令人绝望的环境下让自己的灵魂不死去的途径。

网络是我的双眼，亦是我的双腿，他能带我去到我暂时不能去到之处，能让我看到在各个角落闪闪发光的人，能让我领略不同文化并感受不同观点间的碰撞。

GoodBye 2018，Hello 2019，新的一年我也希望能继续按照自己喜欢的方式去生活。

我们只对未知的事物产生畏惧，知道越多，畏惧越少。
by Lila 《我的天才女友》

相关阅读:我居然错过了考研正式报名

题目描述

原题地址：A1148 Werewolf - Simple Version
中文版：B1089 狼人杀-简单版

解题思路

暴力破解。

• 每次假设其中两名玩家为狼人，并按照该假设设置所有人的身份。
• 然后判断每个人是否说谎，即他声称的玩家身份是否与其当前设定身份一致，如果不一致则说谎。并记录每个说谎的人的编号。
• 每人的话判断结束，如果只有两人说谎，且他们的身份为一名好人一名狼人，则输出结果并退出循环。否则调整假设继续遍历。
• 如果遍历结束还没有找到结果，则无解。

易错点

• 如何判断一个玩家是否说谎
  • 判断一个人是否说谎，即他声称的玩家身份是否与其当前设定身份一致，如果不一致则说谎。因为当前设定身份就是假定的真实情况，不一致说明他讲的与实际不符。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int main() {
  int n, s[105];
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
  for(int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      vector<int> ans, id(n + 1, 1);// id 用于记录当前状态下所有人的身份
      id[i] = id[j] = -1;
      for (int k = 1; k <= n; k++) // 记录说谎的人
        if (s[k] * id[abs(s[k])] < 0) ans.push_back(k);
      if (ans.size() == 2 && id[ans[0]] + id[ans[1]] == 0){
        printf("%d %d\n", i, j);//只有两个人说谎且一个是狼人一个是好人
        return 0;
      }
    }
  }
  printf("No Solution\n");
  return 0;
}