题意是说，给定一个有向图，对于每一条边，问是否是s到t的最短路上一定会经过的边． 如果是就输出yes 如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边． 对于一条边是否一定是最短路上的边，我们可以从s做一遍最短路，然后反响建边，从t再做一遍最短路． 得到两个d1,d2数组 如果一条边d1[u] + d2[v] + w(u, v) = 最短路，那这条边在最短路上的边．但是未必不能缺少． 我们还要判断这条边是否是不能缺少的． 不能缺少的意思是说，如果没有这条边，就不能构成最短路． 那么这条边一定是桥． 我们可以用tarjan算法求桥． 据说是水题，不过图论还没怎么刷，所以对我来说还是很有难度 …

http://poj.org/problem?id=1028 1 2 3 4 /* *********************************************** 5Author :111qqz 6Created Time :2016年02月19日 星期五 15时45分01秒 7File Name :1028.cpp 8************************************************ */ 9 10 #include <algorithm>11 #include <cstdio>12 #include <iostream>13 #include …

题目链接：http://poj.org/problem?id=2643 在考stl的map... 我是定义了一个string 指向string的，表示参选人和党派的关系，和一个string 指向int的，表示某个党派被投票的次数。 需要注意的是！！！ 需要注意的是！！！ 需要注意的是！！！ 字符串读入部分... 在输入n和m之后，会有一个回车符没读进去...(大概是这样？) 如果不处理一下的话，后面的字符串就会少读入一个...(sad) 解决的办法是在读完n和m之后写一个getchar(); 把回车符读掉。 1 2 3 /* *********************************************** …

http://acm.hdu.edu.cn/showproblem.php?pid=1908 看到有两个优先级，然后题目中又有queue。。。就想到了优先队列。。。 但是优先队列的cmp函数没搞懂，因为比较的是结构体，好像要重载< 什么的。 然而并不会。 其实用map就可以做。。。 map在插入的时候可以自动按关键字排序，简直好评如潮！ 1 2 3 /* *********************************************** 4Author :111qqz 5Created Time :2016年02月19日 星期五 15时44分06秒 6File Name :3481.cpp …

http://poj.org/problem?id=1833 还是next_permutation. 这次是Int类型的 需要注意的是next_permutation是先判断时候有后继，返回一个bool值，如果为true，就转化到后继。 而next_permutation函数本书不考虑其值，就具有转化成后继的作用。 而且默认最后一个排列的下一个排列是第一个排列。 1 2 3 /* *********************************************** 4Author :111qqz 5Created Time :2016年02月19日 星期五 15时43分58秒 6File Name :1833.cpp …

http://poj.org/problem?id=1256 题意是说求出一个字符串的全排列，按字典序 需要注意的是字典序和传统意义上的字典序不同 重新定义了,A 需要自己重写cmp函数。 next_permutation好神....直接求出全排列..... 1 2 3 /* *********************************************** 4Author :111qqz 5Created Time :2016年02月19日 星期五 15时43分31秒 6File Name :code/poj/1256.cpp …