算法竞赛入门经典 图论部分题解

发表评论

UVa 10801 电梯换乘

题意:

有5个以内电梯，分别可以到达不同的楼层，且速度不同，同一层次如果有两部电梯，就可以换乘，从一部电梯到任意一部电梯都花60s。求0层到某层花费的时间。

解法:

开始我想到的是把每一层不同的电梯看成一个点，但是建图会非常麻烦。看见网上题解用邻接矩阵，代码很简洁。
把每一层视为一个点，邻接矩阵储存每一个点i到另一个点j的最短距离，这个最短距离是未换乘的最短距离。任意i，j都是用了同一部电梯,但同一行或同一列不一定是同一部电梯。d[]刚好等价于G[0][]，接下来就是dijkstra算法，如：G0存在，说明0到i的最短距离就是G0，此时再更新所有邻接点，如果0，j无边，或者换乘后距离小于未换乘的最短距离，那就更新。
原代码在邻接点加了判断vis[y]是为了电梯可以一直向上走。

UVa 1664 Conquer a New Region

题意：

n个城镇，有n-1条路，c(i,j)表示两个城镇之间的交通容量，一条路径的容量的最大值是这条路径所有路的最小值，找出一个中心点，使得它到其他n-1个城镇的容量最大。

解法：

最小生成树的定义是边权总和最小的的生成树。这里并不是求边权总和最大的生成树，而是路径上权最小值，利用Kruskal算法，按照它排序做生成树。怎么求路径最小值？边从大到小排序，如果第一个是(u, v, c)，显然u到v的最小权值和v到u的都是等于c，对于新加入的边呢？新加入的(u, v1, c1)，和u，v属于同一个连通分量，那么c1肯定是u到v1和v到v1的最小权值，因为是从大到小排序。本来想的是计算每一个点的到其他点的权值和，然后排序找最大的，在每个连通分量添加新点时，更新他们的权值和，结果TLE。
看了网上类似贪心的做法，因为不需要求出具体哪个点作为中心，所以在每次添加新点时，比较两个点（孤立点或者连通分量代表元）谁作为中心时会更大，把并查集的代表元改为中心点。
其依据是：每加入一个点，由于排序，它的权值必然小于等于连通分量内所有边的权值，所以当新点作为中心点时，连通分量的每个点都必须加上新点带来的权值。

UVA 1279 Asteroid Rangers

题意：

n个点在三维空间，每个点会匀速移动，在xyz方向上有恒定速度，相同时间每个点都移动到不同坐标，图有唯一的最小生成树，且最小生成树在10^-6s内不会改变，求最小生成树的个数。

解法：

p1(x1 + dx1 t, y1 + dy1t, z1 + dz1 * t)
p2(x2 + dx2 t, y2 + dy2t, z2 + dz2 * t)
IMG_20180114_194304.jpg

UVa Live 6039 Let’s Go Green

题意：

有n个城市，城市与城市构成树形结构（每个城市之间只有唯一一条路）简单起见，自行车不会走同样的路两次（一个城市路过一次），给出每条路上自行车经过的次数，求自行车最少能有多少。

解法1：

先求所有边的权的和sum，sum肯定是大于等于总单车数的，一辆车可以增加很多边权。把输入的单向边变为双向的，这样来遍历每一个点，这里把边权定义为经过边的单车数，让点权值等于经过该点的单车数，发现：点权和 = 边权和 + 最少单车数（难不成这是图论的某个定理？），点权的计算：如果有一条边的权比其余边权的和还要大，即maxm > esum – maxm，那么让这条边的单车往其他边走，点权（经过该点的单车）最少是maxm；如果没有出现这种情况，只能让边上的自行车的一半，经过该点然后去抵消另一半边，偶数自行车一半到另一半，奇数有一个在该点经过就不走了，剩下的一半去抵消另一半，对于整形除法都是(esum + 1) / 2。

STL学习总结

发表评论

这段时间的学习之后，掌握了容器、string类还有几个算法函数的基本用法，知道更多的字符串处理方法。

其中，不懂的题有：
K Smallest Sums

仍然还有bug的题有：
Borrowers
Updating a Dictionary
PGA Tour Prize Money
Bug Hunt

未做的题有：
The Letter Carrier’s Rounds
Do You Know the Way to San Jose?
Boring Game
USACO ORZ
Use of Hospital Facilities
Revenge of Fibonacci
Exchange
Queue and A

C到C++的输入方式

发表评论

Tips

  • 不要使用getch()和conio.h
  • 输出%d可以用printf(“%%d”);
  • printf(“\n”);输出n
  • “\n” 比 endl 快。

C语言输入函数

  • getchar函数接受所有字符包括回车。（单个字符）
  • gets函数是以回车符作为输入结束的标志，容易越界。

C++输入函数

bool eof(); 判断输入流是否结束
int peek(); 返回下一个字符,但不从流中去掉.
istream & putback(char c); 将字符ch放回输入流
istream & ignore( int nCount = 1, int delim = EOF ); 从流中删掉最多nCount个字符，遇到EOF时结束。

cin>>

结束条件：[enter],[space],[tab]
处理方法：cin遇到缓冲区中的[enter],[space],[tab]会结束当前输入，不会移除[enter],[space],[tab]，继续下一项输入，当有连续[space],[enter,[tab]也只是将其放回缓冲区。
利用ios::sync_with_stdio(false);取消cin与stdin的同步可以更加快。

cin.getline

接受一个字符串，可以接收空格并输出。

char src[18];
cin.getline(src, 5);
cin.getline(src, 5, 'a');

结束条件：超过数量限制，输入[enter]，或者输入自定义终止符。
处理方法：若超过限制，则其余字符不做处理。若输入[enter]或输入自定义终止符则移除（取其一）。
第一个函数默认只接收char*地址，且限制在4个字符以内。第5个是0。若输入1234回车，超过限制字符，cin.getline会把n从流中移除，输入其他字符则不会被移除。
第二个函数:结束条件为a与上述一致，直到输入a终止，此时a会被移除，n会继续留在流中。或者超过限制数量时，剩余的字符留在流中。
显然因为规定了限制数量，不会越界，比gets好多了。

cin.get

结束条件：输入字符足够后回车。或者输入自定义终止符。
函数的返回值就是读入的字符。 若遇到输入流中的文件结束符，则函数值返回文件结束标志EOF(End Of File)，一般以-1代表EOF，用-1而不用0或正值，是考虑到不与字符的ASCII代码混淆，但不同的C++系统所用的EOF值有可能不同。

char ch;
char src[18];
cin.get(ch);
cin.get(src, 5);
cin.get(src, 5, 'a');

第一个函数接受任意字符与getchar类似。
第二、三个函数与cin.getline类似。
显然不会越界。

cin.getline 与 cin.get 的区别

cin.get(arrayname,size)当遇到[enter]时会结束目前输入，不会删除缓冲区中的[enter]
cin.getline(arrayname,size)当遇到[enter]时会结束当前输入，会删除缓冲区中的[enter]

cin.get（arrayname,size,s）当遇到s时会结束输入，不会删除缓冲区中的s
cin.getline(arrayname,size,s)当遇到s时会结束输入，并把s从缓冲区中删除

getline()

需要#incldue < string >

string s;
getline(cin, s);
getline(cin, s, 'a');
// input    -    获取数据来源的流
// str    -    放置数据的目标 string
// delim    -    分隔字符

适用于string类，和cin.getline一样会移除终止的[enter]（第一个函数），或者移除a（第二个函数）。
（用std::basic_istream::operator>>释出）

从scanf说起

scanf(“”，)

1. %d格式输入，默认分隔符是所有的 white-spaces(空格、回车、制表)；

2. %c格式输入，则按ASCII字符考虑，无分隔符。可能会受到之前输入的影响，必要时用fflush(stdin);清除缓冲区；

3. %s 是 字符串格式，默认分隔符是所有的 white-spaces，输入后自动加入结束符"\0"。

scanf函数的与后面的是必须严格匹配的。注意，是严格匹配，可以说不能有丝毫差别，但对于连续多个空格可以等同于一个空格。如：

scanf("%d, %d", &num1, &num2);  
scanf("%d,%d", &num1, &num2);

第一条要想输入正确，必须输入一个整数，然后输入一个逗号(,)，之后是第二个整数。最后是回车结束。
第二条语句中的中的两个%d之间没有空格，如果此时输入：12 ，13回车（12后面先有一个空格后由逗号），那么num2并不等于13。反过来，输入：“12”、“，”、“空格”、“13”，则不会出现错误。(自动跳过whitespace)

scanf("%d %d", &i, &j);

返回值是成功读取变量的个数，如果输入8 8.1 返回1，输入8 d返回1，输入d 8返回0。出错时则返回EOF。

scanf(" %c",&ch);

%c是个较为特殊的说明符。 %c前没空格，scanf()将读取标准输入流中的第一个字符，%c前有空格，scanf()则读取标准输入流中第一个非空白字符。

scanf("%[A-Z]", s); //输入除A到Z的任何字符（包括空格、回车）都会停止。
scanf("%[^A-Z]", s);
scanf("%[^\n]", s);

第一条的意思是读入一个字符集合。[ ]是个集合的标志，%[ ]特指读入此集合所限定的那些字符，比如%[A-Z]是输入大写字母，一旦遇到不在此集合的字符便停止。
如果集合的第一个字符是“^”，这说明读取不在”^”后面集合的字符，即遇到”^”后面集合的字符便停止。如第二条，为大写字母就停止。
第三天遇到回车停止。

scanf("%d ", &num);/*scanf("%d\n", &num);*/

输入一个整数后，无论在输入多少个空格、回车、Tab，都没有输出；但是当再次输入非空白字符时，如输入2 然后输入空格然后输入4，最后输入回车，则会有输出。

scanf("%s", &s)

%s默认分隔符是所有的 white-spaces，输入后自动加入结束符”0″，使其成为一个字符串(之所以加上0，是和字符数组char[]的结束符有关的，C中是没有string这个类型的，是使用char[]结构实现字符串)。值得注意的是，即使输入字符的长度足够，%s是宁愿舍弃输入字符，也要把/0加上去的，作为字符串的结束。并且，scanf会忽略缓冲区开头的空格，直到遇到一个非空格字符，才开始向内存中读取数据。
想要输入”The C Programming Language.n”中间的空格怎么处理呢？
其中一个解决方法是使用gets函数，这个函数是以回车符作为输入结束的标志的；还有一种解决方式是：

scanf("%[^\n]", str);

scanf之后就可以将char[]转换为string，以防oj不对cin进行优化导致速度变慢的问题。

cin 与 scanf 测试（未完）

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
    freopen("dataout.txt","w", stdout);
    int start = clock();
    for(int i = 0; i < 1000000; i++)
    {
        printf("%d", i);
    }
    return 0;
}

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
    freopen("dataout.txt","r", stdin);
    int a;
    int start = clock();
    for(int i = 0; i < 1000000; i++)
    {
        scanf("%d\n", &a);
    }
    printf("%.3lf\n",double(clock()-start)/CLOCKS_PER_SEC);
    return 0;
}

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    freopen("dataout.txt","r", stdin);
    int a;
    int start = clock();
    for(int i = 0; i < 1000000; i++)
    {
        cin >> a;
    }
    printf("%.3lf\n",double(clock()-start)/CLOCKS_PER_SEC);
    return 0;
}

容器适配器 stack, queue, priority_queue

发表评论

容器适配器

  • 可以用某种顺序容器来实现(让已有的顺序容器以栈/队列的方式工作)

1) stack: 头文件 < stack >
栈 — 后进先出
2) queue: 头文件 < queue >
队列 — 先进先出
3) priority_queue: 头文件 < queue >
优先级队列 — 最高优先级元素总是第一个出列

都有3个成员函数:

  • push: 添加一个元素;
  • top: 返回栈顶部或队头元素的引用
  • pop: 删除一个元素

容器适配器上没有迭代器——STL中各种排序, 查找, 变序等算法都不适合容器适配器

stack

  1. stack 是后进先出的数据结构
  2. 只能插入, 删除, 访问栈顶的元素

  3. 可用 vector, list, deque来实现

    • 缺省情况下, 用deque实现
    • 用 vector和deque实现, 比用list实现性能好
template
class stack {
…
};

stack 中主要的三个成员函数:

void push(const T & x);
将x压入栈顶
void pop();
弹出(即删除)栈顶元素
T & top();
返回栈顶元素的引用. 通过该函数, 可以读取栈顶
元素的值, 也可以修改栈顶元素

queue

  • 和stack 基本类似, 可以用 list和deque实现
  • 缺省情况下用deque实现
template
class queue {
……
};

  • 同样也有push, pop, top函数

    • push发生在队尾
    • pop, top发生在队头, 先进先出

priority_queue

  • 和 queue类似, 可以用vector和deque实现
  • 缺省情况下用vector实现

  • priority_queue 通常用堆排序技术实现, 保证最大的元
    素总是在最前面

    • 执行pop操作时, 删除的是最大的元素
    • 执行top操作时, 返回的是最大元素的引用
      默认的元素比较器是 less

函数对象

发表评论

STL中的函数对象类模板
以下模板可以用来生成函数对象。
equal_to
greater
less
…….
头文件：

greater 函数对象类模板

template
struct greater : public binary_function {
bool operator()(const T& x, const T& y) const 
    {
    return x > y;
    }
};

greater 的应用

list 有两个sort成员函数

 void sort();