太傅博客 - POJ
type: channel
link: https://acm.taifua.com/tag/poj/
items: POJ2449 Remmarguts' Date（k短路/A*+Dijkstra）
items: POJ3169 Layout（差分约束+最短路）
items: POJ3255 Roadblocks（次短路）
items: POJ3660 Cow Contest（floyd传递闭包）
items: POJ1860 Currency Exchange（最短路）
items: POJ2195 Going Home（二分图最优匹配）
items: POJ2195 Going Home（最小费用最大流）
items: POJ1094 Sorting It All Out（拓扑排序）
items: POJ3177 Redundant Paths（Tarjan求有重边双连通分量缩点）
items: POJ3352 Road Construction（Tarjan求双连通分量缩点）

POJ2449 Remmarguts' Date（k短路/A*+Dijkstra）
type: item
date: 2018-09-09T20:47:00+08:00
description: Remmarguts' DateTime Limit: 4000MSMemory Limit: 65536KTotal Submissions: 37019Accepted: 10204Description"Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story. "Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission." "Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)" Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help! DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.InputThe first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T. The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).OutputA single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1" (without quotes) instead.Sample Input2 2 1 2 5 2 1 4 1 2 2Sample Output14SourcePOJ Monthly,Zeyuan Zhu链接http://poj.org/problem?id=2449题意n个点m条边有向带权图，求s到t的k短路，不能到达输出-1。本题需要特判一下s==t的情况。题解K短路模…

POJ3169 Layout（差分约束+最短路）
type: item
date: 2018-09-05T21:02:00+08:00
description: LayoutLike everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate). Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated. Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.InputLine 1: Three space-separated integers: N, ML, and MD. Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart. Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.OutputLine 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.Sample Input4 2 1 1 3 10 2 4 20 2 3 3Sample Output27HintExplanation of the sample: There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units a…

POJ3255 Roadblocks（次短路）
type: item
date: 2018-08-30T19:59:43+08:00
description: RoadblocksTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 19715 Accepted: 6914DescriptionBessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).InputLine 1: Two space-separated integers: N and R Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)OutputLine 1: The length of the second shortest path between node 1 and node NSample Input4 4 1 2 100 2 4 200 2 3 250 3 4 100Sample Output450HintTwo routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)SourceUSACO 2006 November Gold链接http://poj.org/problem?id=3255题意求1到N的次短路。题解两种办法。在求最短路的时候记录次短路，先更新最短路，然后更新次短路具体可参考：传送门。如果dist[v]表示s->v的最短距离，dist2[v]表示s->v的次短距离，d为s->v的第k短距离(k>1)。那么一定满足这样一个关系，dist[v] < dist2[v] <= k[雾]。看到这个等式的时候我们可以发现，如果dist2[v] > d2 > dist[v]，显然这时候我们需要将dist2[v]更新为d2。那么我们只要找到不满足dist[v] < dist2[v] <= k[雾]这个的式子的dist2[v]，那么我们就更新他。一直更新到所以式子都满足这个式子，那么dist2[v]就为源点s->v的次短路。到此我们已经推出了求解次短路的方法。两次最短路（起点$\rightarrow$终点，终点$\rightarrow$起点），然后再枚举每一条边，如果dist1[A] + $W_{AB}$ + dist2[B] > dist…

POJ3660 Cow Contest（floyd传递闭包）
type: item
date: 2018-08-23T23:07:00+08:00
description: Cow ContestTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 15880 Accepted: 8852DescriptionN (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.Input* Line 1: Two space-separated integers: N and M* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and BOutput* Line 1: A single integer representing the number of cows whose ranks can be determinedSample Input5 5 4 3 4 2 3 2 1 2 2 5Sample Output2SourceUSACO 2008 January Silver链接http://poj.org/problem?id=3660题意n头奶牛，每头奶牛都有一个唯一的技能排名，如果奶牛A能打败奶牛B，说明A的排名比B高，具有传递性，现在给定m场比赛信息，问有多少头奶牛能确定技能排名。题解Floyd传递闭包。跑一遍floyd就得到了任意两头奶牛之间是否能确定关系，如果一头奶牛与其余的n-1头奶牛都能确定关系，那么它的排名就一定能确定。代码StatusAcceptedTime32msMemory700kBLength1053#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1010; int G[maxn][maxn]; int n, m; void floyd() // floyd求传递闭包 { for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (G[i][k] && G[k][j]) // i->k->j G[i][j] = 1; } } } } int main() { int u, v; while (scanf("%d%d", &n, &m) != EOF) { memset(G, 0, sizeof(G)); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); G[u][v] = 1; } floyd(); int cnt, ans = 0; for (int i = 1; i <= n; ++i) { cnt = 0; for (int j =…

POJ1860 Currency Exchange（最短路）
type: item
date: 2018-08-14T11:07:00+08:00
description: Currency ExchangeTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 36534 Accepted: 14029DescriptionSeveral currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency. For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 - 0.39) * 29.75 = 2963.3975RUR. You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B - numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA - exchange rates and commissions when exchanging A to B and B to A respectively. Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.InputThe first line of the input contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=103. For each point exchange rates and commissions are real, given wit…

POJ2195 Going Home（二分图最优匹配）
type: item
date: 2018-08-01T16:53:00+08:00
description: Going HomeTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 24963Accepted: 12509DescriptionOn a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man. Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point. You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.InputThere are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.OutputFor each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.Sample Input2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0Sample Output2 10 28SourcePacific Northwest 2004链接http://poj.org/problem?id=2195题意n个小人回到n间房子，一对一，现要使移动的总距离最少。题解建图，转化为“二分图最大权值匹配”，实际上是最小权值，边权为人到房的“最短移动距离”，取负数即可。代码StatusAcceptedTime32msMemory716kBLength3171#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int …

POJ2195 Going Home（最小费用最大流）
type: item
date: 2018-07-31T15:13:00+08:00
description: Going HomeTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 24963Accepted: 12509DescriptionOn a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man. Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point. You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.InputThere are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.OutputFor each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.Sample Input2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0Sample Output2 10 28SourcePacific Northwest 2004链接http://poj.org/problem?id=2195题意n个小人回到n间房子，一对一，现要使移动的总距离最少。题解建图，转化为最小费用最大流，容量为1，费用为人到房的“最短移动距离”。代码StatusAcceptedTime141msMemory800kBLength3412#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn = 10010; // 点…

POJ1094 Sorting It All Out（拓扑排序）
type: item
date: 2018-07-20T17:01:00+08:00
description: Sorting It All Out总时间限制: 1000ms内存限制: 65536kB描述An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.输入Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.输出For each problem instance, output consists of one line. This line should be one of the following three:Sorted sequence determined after xxx relations: yyy...y.Sorted sequence cannot be determined.Inconsistency found after xxx relations.where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.样例输入4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0样例输出Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.来源East Central North America 2001链接http://bailian.openjudge.cn/practice/1094?lang=en_US【POJ同题号】题意给定一个字符序列，我们可以确定每个字符的大小顺序，比如给定ABCD，有A<B、B<C、C<D。现在，给定多组字符大小顺序的关系式，问能否通过这些关系式确定一个有序序列。如果能确定有序序列，输出最早能够确定顺序的关系式的数量以及该序列如果出现冲突，输出最早能够确定冲突的关系式的数量如果不能确定也不存在冲突，输出无法得到题解每来一个小于关系就进行一次拓扑排序…

POJ3177 Redundant Paths（Tarjan求有重边双连通分量缩点）
type: item
date: 2018-07-18T15:15:00+08:00
description: Redundant PathsTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 18207Accepted: 7554DescriptionIn order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another. Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way. There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.InputLine 1: Two space-separated integers: F and R Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.OutputLine 1: A single integer that is the number of new paths that must be built.Sample Input7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7Sample Output2HintExplanation of the sample: One visualization of the paths is: 1 2 3 +---+---+ | | | | 6 +---+---+ 4 / 5 / / 7 + Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions. 1 2 3 +---+---+ : | | : | | 6 +---+---+ 4 / 5 : / : / : 7 + - - - - Check some of the routes: 1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2 1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4 3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7 Every pair of fie…

POJ3352 Road Construction（Tarjan求双连通分量缩点）
type: item
date: 2018-07-18T14:56:00+08:00
description: Road ConstructionTime Limit: 2000MSMemory Limit: 65536KTotal Submissions: 13401Accepted: 6758DescriptionIt's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.InputThe first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. …