图论算法

妖狐艹你老母 2022-01-06 22:13 247阅读 0赞

**Problem1一笔画问题**

**题目描述**

给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出‘No solution’

**输入**

输入的第一行为边数F(<=1024)，后面F行每行表示一条边（定点标号范围为1-500）

**输出**

输出一条合法的欧拉回路（路径），若有多条满足要求，输出其字典序最小的那一个。

**Problem2 Car的旅行路线**

**题目描述**

住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费，求其最少花费

**输入**

第一行有四个正整数s，t，A，B。

S(0<S<=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。

接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。

**输出**

输出最小花费，保留一位小数

**Problem3求割点与桥**

**题目描述**

给定一个图，求其割点与桥

**输入**

第一行有两个整数，n、e，即点数与边数

后面e行，每行两个整数v1、v2，表示点v1与v2相连

**输出**

首先输出所有割点，每行输出一个

然后输出所有桥，每行一条

(不用考虑顺序)

**Problem4十字绣**

**题目描述**

布是一个n\*m的网格，线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一，而在绣的过程中，一针中连续的两段线必须分处布的两面。给出布两面的图案(实线代表该处有线,虚线代表背面有线)，问最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。

**输入**

输入第1行两个数N和M(1<=N,M<=200)。

接下来N行每行M个数描述正面。

再接下来N行每行M个数描述反面。

每个格子用.（表示空）,/（表示从右上角连到左下角）,\\（表示从左上角连到右下角）和X（表示连两条对角线）表示。

**输出**

输出一个数，最少要用的针数

**Problem5舞会**

**题目描述**

一个舞会邀请n个人，这n个人每一个人都有一个小花名册，名册里面写着他所愿意交流的人的名字。比如说在A的人名单里写了B，那么表示A愿意与B交流；但是B的名单里不见的有A，也就是说B不见的想与A交流。但是如果A愿意与B交流，B愿意与C交流，那么A一定愿意与C交流。也就是说交流有传递性。现在觉得需要将这n个人分为m组，要求每一组的任何一人都愿意与组内其他人交流。并求出一种方案以确定m的最小值是多少。

注意：自己的名单里面不会有自己的名字。

**输入**

输入第一行一个数n。接下来n行，每i+1行表示编号为i的人的小花名册名单，名单以0结束。1<=n<=200。

**输出**

输出即m的最小值

**Problem6休息中的小呆**

**题目描述**

NOIP备战之际，小呆正在悠闲（欠扁）地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫pass的有志少年在不同的时空穿越对抗传说中的大魔王chinesesonic的故事。小呆发现这个游戏的故事流程设计得很复杂，它有着很多的分支剧情，但不同的分支剧情是可以同时进行的，因此游戏可以由剧情和剧情的结束点组成，某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢？所以就请你来解决这个问题了。

**输入**

输入会给你一个剧情流程和完成条件的列表，其中第一行有一个数n（0<n<100），表示总共有n个剧情结束点，第二行一个数m(0<m<=120)，表示由m个不同的剧情，下面的m行中每行有三个数i0<i<=100),j0<j<=100),k0<k<=1000)，表示从剧情结束点i必须完成一个耗费时间为k的剧情才能到达剧情结束点j。注意，这m行中出现的1不是剧情结束点而是游戏的开始，而n+1表示游戏结束。

**输出**

输出第一行为一个数，即你要告诉小呆完成整个游戏至少需要多少时间，第二韩有若干个数，即要经过的所有可能的剧情结束点（按升序输出）。

**Problem7最优布线问题**

**题目描述**

校园里有n台计算机，要将它们用数据线连接起来。由于计算机所处的位置不同，连接2台计算机的费用往往是不同的。如果将每2 台计算机都用数据线连接，势必造成浪费。为了节省费用，可以采用数据的间接传输手段，即一台计算机可以间接通过若干台计算机(作为中转)来实现与另一台计算机的连接。如何用最少费用连接n台计算机。

**输入**

输入数据。第一行有1个正整数n，表示计算机数。此后n行，每行有n个正整数。第x+1行，第y列的正整数表示直接连接第x台计算机和第y台计算机的费用。

**输出**

输出最小费用

**Problem8磁盘碎片整理**

**题目描述**

出于最高安全性考虑，司令部采用了特殊的安全操作系统。该系统采用一个特殊的文件系统。在这个文件系统中所有磁盘空间都被分配了相同尺寸的N块，用整数1到N表识，每个文件占用磁盘上任意区域的一块或多块存储区，未被文件占用的存储块被认为是可以使用的。如果文件存储在磁盘上自然连续的存储块中，则能被以最快的速度读出。

因为磁盘是均匀转动的，所以存取上面的不同的存储快需要的时间也不同。读取磁盘开头处的存储比读取磁盘结尾处的存储块快。根据以上现象，我们事先将文件按其存取频率的大小用整数1到K标识。按文件在磁盘上最佳的存储方法，1号文件将占用1，2……，S1的存储块，2号文件占用S1+1,S1+2……S1+S2的存储块，依次类推。为了将文件以最佳形式存储在磁盘上，需要执行存储酷块移动操作。操作后，原空间将被释放，新空间将被占用。

问对于一个文件序列，最少需要多少次移动操作才能以最佳方式存储到磁盘上

**输入**

输入第一行包含两个整数N，K，接下来K行每行描述一个文件，第一个数为Si，表示其存储块数量，后面有Si个整数，每个整数之间用空格隔开，表示该文件按自然顺序在磁盘上占用的存储块标识，所有这些数都介于1和N之间，包括1和N。

所有磁盘空间的表识都不相同

**输出**

输出一个数，即最小移动次数

**Problem9说谎岛**

**题目描述**

哥仑布在到达美州后，发现了一个奇特的岛屿。这个岛屿上的人狡猾且喜欢说谎，由于完全的谎言较易为人所识破，所以为了更加能够迷惑别人，他们的言语往往是半真半假的。

由于对于环境的不熟悉，哥仑布有许多问题要请教岛上的居民。当然他已经知道了岛上居民的这一说谎习俗。

幸好，哥仑布的所有问题都只需回答“是”或者“否”，这样便免去了许多繁复。假设哥仑布询问了N个居民，对于每个居民只问两个问题，每个居民只需对于每个问题回答“是”或“否”。根据居民的习俗，可以断定两个回答中必有一个是正确的，而另一个是错误的。同一个问题可以反复问多人。

哥仑布根据这N个人的回答，需要整理推断出他所有问题的答案。但这一过程实在太复杂与困难了，因此希望你能够编程求出所有可能答案的种数。