- 博客(19)
- 收藏
- 关注
RSS订阅原创 POJ3041 - Asteroids
此题说难也难说简单也简单。关键就看有没有理解这样的一条定理： 最小点覆盖数=最大匹配数 解题思路如下： 1、以行和列分别建立两个顶点集V1，V2 2、将障碍物（x1，y1）视为两个顶点集中的两点V1(x1)，V2(y1)的边 3、求V1和V2的最大二分匹配，由最小点覆盖数=最大匹配数可知，此即为答案(the minimum number of times Bessie
2015-01-06 22:00:59
239
原创 POJ1094 - Sorting It All Out
从A到Z中给出n个字母和m个关系 问根据这m关系能否找到n个字母的关系，有以下三种情况： 1、可以确定n个字母的排序，输出 按序排列的字母，以及通过前几个关系发现，输出样例如下 Sorted sequence determined after 4 relations: ABCD. 2、有矛盾，输出通过前几个关系发现的矛盾，样例： Inconsistency found aft
2014-12-21 23:16:14
278
原创 POJ3026 - Borg Maze
此题可以分为拆分为两个问题： 1、求起止点S和n个外星人A，共n+1个顶点的两两距离 2、求这n+1个顶点的最小生成树 //Memory Time //220K 16MS #include #include #include using namespace std; #define MAXCONST 2000000000; char s[100][10
2014-12-19 23:04:06
291
原创 POJ1258 - Agri-Net
求最小生成树总权值 //Memory Time //196K 16MS #include #define MAXCONST 2000000000 int dis[100][100]; int cost[100]; int que[100]; int main() { int N; while(scanf("%d", &N) != EOF) { for(int j = 0
2014-12-19 23:01:47
271
原创 POJ2485 - Highways
用prim求最小生成树 //Memory Time //552K 157MS #include #define MAXCONST 2000000000 int dis[500][500]; int cost[500]; int que[500]; int main() { int T; scanf("%d", &T); for(int i = 0; i < T; i++) {
2014-12-11 23:29:48
292
原创 POJ2240 - Arbitrage
又是各种钱币换来换去，问能不能赚钱。 Floyd算法判环。 //Memory Time //228K 32MS #include #include using namespace std; char dollarName[30][30]; float edge[30][30]; int outMatch(char src[30], char dst[][30], int dollarT
2014-12-08 23:37:25
281
原创 POJ1125 - Stockbroker Grapevine
果然还是写一题发一个博客好一点，现在都有点记不清自己写的是什么了。。。 Floyd算法的题，需要判环 //Memory Time //224K 0MS #include using namespace std; void floyd(int dis[][101], int vexNum); int dis[101][101]; int main() { int sto
2014-12-08 23:34:03
286
原创 POJ2253 - Frogger
有两只青蛙A和B，以及n-2个节点，这n个节点两两相连，边权为节点之间的距离。显然，青蛙A是必定可以到达青蛙B的，设所有路径集合为S，求路径a属于S，使路径a的最大边权在路径集合S中最小。 这题当时是借鉴了bellman-ford算法的思路解决的，现在发现用dijkstra的思路也可以解。。。 核心思路是 edge[s][d] = max( min( edge[s][k]), min
2014-12-08 23:13:23
292
原创 POJ1062 - 昂贵的聘礼
非负权的单源最短路径，果断用dijkstra算法 需要注意的是这里是有交易的双方是有等级限制的，假设族长等级为Level0，最大可交易等级差为M，解决方案是，依次假设旅行者的等级为 Level0-M、Level0-M+1、Level0-M+2.......Level0+M，然后让旅行者只和等级不低于他的人交易，然后比较这2M+1次的结果，取最小值。 //Memory Time /
2014-12-08 22:56:46
282
原创 POJ3259 - Wormholes
bellman-ford算法判断环。 //Memory Time //1260K 360MS //不添加delete //488K 985MS //添加delete之后 #include #include using namespace std; struct edge{ edge* next; int dst; int cost; }; struct vexte
2014-12-08 22:52:50
236
原创 POJ1860 - Currency Exchange
给定N种货币，某些货币之间可以相互兑换，现在给定一些兑换规则，问能否从某一种货币开始兑换，经过一些中间货币之后，最后兑换回这种货币，并且得到的钱比之前的多。 可以把初始兑换的货币看成源点，采用bellman-ford进行求解，若可以实现要求，则说明图中存在可以无限增大的环，这个可以通过bellman-ford算法判断环是否存在求出来，若在求解过程中发现已经兑换回原货币，并且钱比之前多，则可以
2014-11-24 22:15:49
344
原创 POJ2996 - Help Me with the Game
//Memory Time //216K 0MS #include #include using namespace std; /* 1、输出先列后行 2、行号是从下往上计数的，最上面的行是8 3、：黑 .白 4、白 行号为从小到大 黑相反 */ struct chess { char name; char row; char c
2014-11-22 23:03:22
326
原创 POJ1068-Parencodings
对于给出的原括号串，存在两种数字密码串： 1.p序列：当出现匹配括号对时，从该括号对的右括号开始往左数，直到最前面的左括号数，就是pi的值。 2.w序列：当出现匹配括号对时，包含在该括号对中的所有右括号数（包括该括号对）,就是wi的值。 题目的要求：对给出的p数字串，求出对应的s串。
2014-11-19 21:35:54
252
原创 POJ3295-Tautology
大致题意： 输入由p、q、r、s、t、K、A、N、C、E共10个字母组成的逻辑表达式， 其中p、q、r、s、t的值为1（true）或0（false），即逻辑变量； K、A、N、C、E为逻辑运算符， K --> and: x && y A --> or: x || y N --> not : !x C --> implies : (!x)||y
2014-11-17 22:47:59
241
转载 IOS获取屏幕分辨率
获取屏幕分辨率是个很有用的功能，尤其在一些游戏相关的开发中，图形的绘制与屏幕分辨率密不可分。得到当前屏幕的分辨率是必不可少的支持。 获取屏幕分辨率可以两步走 1、得到当前屏幕的尺寸： CGRect rect_screen = [[UIScreenmainScreen]bounds]; CGSize size_screen = rect_screen.size; 2、获
2014-09-20 14:27:29
273
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人