太傅博客 - UVA
type: channel
link: https://acm.taifua.com/tag/uva
items: UVA1201 Taxi Cab Scheme（最小路径覆盖）
items: UVA1175 Ladies' Choice（稳定婚姻问题）
items: UVA1006 Fixed Partition Memory Management（二分图最优匹配/最小权值匹配）
items: UVA1411 Ants（二分图最优匹配/最小权值匹配）
items: UVA10537 The Toll! Revisited（最短路）
items: UVALive8456 The Maximum Unreachable Node Set（floyd传递闭包+二分图最大匹配）
items: UVA1416 Warfare And Logistics（最短路/树）
items: UVA11374 Airport Express（最短路）
items: UVA11367 Full Tank? （最短路+dp）
items: UVA10054 The Necklace（欧拉回路）

UVA1201 Taxi Cab Scheme（最小路径覆盖）
type: item
date: 2018-08-30T12:36:00+08:00
description: Taxi Cab SchemeTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 7529 Accepted: 3083DescriptionRunning a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as possible,there is also a need to schedule all the taxi rides which have been booked in advance.Given a list of all booked taxi rides for the next day, you want to minimise the number of cabs needed to carry out all of the rides. For the sake of simplicity, we model a city as a rectangular grid. An address in the city is denoted by two integers: the street and avenue number. The time needed to get from the address a, b to c, d by taxi is |a - c| + |b - d| minutes. A cab may carry out a booked ride if it is its first ride of the day, or if it can get to the source address of the new ride from its latest,at least one minute before the new ride's scheduled departure. Note that some rides may end after midnight.InputOn the first line of the input is a single positive integer N, telling the number of test scenarios to follow. Each scenario begins with a line containing an integer M, 0 < M < 500, being the number of booked taxi rides. The following M lines contain the rides. Each ride is described by a departure time on the format hh:mm (ranging from 00:00 to 23:59), two integers a b that are the coordinates of the source address and two integers c d that are the coordinates of the destination address. All coordinates are at least 0 and strictly smaller than 200. The booked rides in each scenario are sorted in order of increasing departure time.OutputFor each scenario, output one line containing the minimum number of cabs required to carry out all the booked taxi rides.Sample Input2 2 08:00 10 11 9 16 08:07 9 16 10 11 2 08:00 10 11 9 16 08:06 9 16 10 11Sample Output1 2SourceNorthwestern Europe 2004链接https://cn.vjudge.net/problem/UVA-1201题意给定一些客人的出行计划（开始时间，起点位置，终点位置），派最少的出租车去接这些客人。出租车接人的条件是…

UVA1175 Ladies' Choice（稳定婚姻问题）
type: item
date: 2018-08-28T20:01:44+08:00
description: Ladies' ChoiceTime Limit: 5 SecondsMemory Limit: 32768 KBTeenagers from the local high school have asked you to help them with the organization of next year's Prom. The idea is to find a suitable date for everyone in the class in a fair and civilized way. So, they have organized a web site where all students, boys and girls, state their preferences among the class members, by ordering all the possible candidates. Your mission is to keep everyone as happy as possible. Assume that there are equal numbers of boys and girls.Given a set of preferences, set up the blind dates such that there are no other two people of opposite sex who would both rather have each other than their current partners. Since it was decided that the Prom was Ladies' Choice, we want to produce the best possible choice for the girls.InputA positive integer P in a single line followed by a sequence of P test cases. Each test case consists of a positive integer N, not greater than 1,000, indicating the number of couples in the class. Next, there are N lines, each one containing the all the integers from 1 to N, ordered according to the girl's preferences. Next, there are N lines, each one containing all the integers from 1 to N, ordered according to the boy's preferences.OutputThe output consists of a sequence of N lines, where the i-th line contains the number of the boy assigned to the i-th girl (from 1 to N).Sample Input1 5 1 2 3 5 4 5 2 4 3 1 3 5 1 2 4 3 4 2 1 5 4 5 1 2 3 2 5 4 1 3 3 2 4 1 5 1 2 4 3 5 4 1 2 5 3 5 3 2 4 1Sample Output1 2 5 3 4SourceSouthwestern Europe 2007链接https://vjudge.net/problem/UVA-1175题意对于每个女生，在所有可能和她跳舞的男生中，找出她最喜欢的那个。题解著名的稳定婚姻问题，只是把“结婚”和“配偶”换成了“跳舞”和舞伴。稳定婚姻问题就是给你n个男的，n个女的，然后给你每个男生中女生的排名，和女生心目中男生的排名，然后让你匹配成n对，使婚姻稳定，假如a和b匹配,c和d匹配，如果a认为d比b好，同时d也认为a比c好，那么ad就有可能私奔，这样就导致了婚姻的不稳定，稳定婚姻就是找到一种解决方案让婚姻稳定。算法：稳定婚姻的解决方法比较简单，通俗易懂，而且还容易实现，具体有没有固定的模板我不知道，没有去找，自己模拟的，在求解的过程中，我们先把所有的男生都加到队列里，队列里的就表示当前还单身的男生，每次从队列里拿出一个男生，然后从她最喜欢的女生开始匹配，如果当前的女生尝试追求过，那么就不用追求了，如果当前的女生没有伴侣，那么可以直接匹配上，如果有伴侣，那么就看看当前这个男生…

UVA1006 Fixed Partition Memory Management（二分图最优匹配/最小权值匹配）
type: item
date: 2018-08-26T13:43:00+08:00
description: Fixed Partition Memory ManagementA technique used in early multiprogramming operating systems involved partitioning the available primary memory into a number of regions with each region having a fixed size, different regions potentially having different sizes. The sum of the sizes of all regions equals the size of the primary memory.Given a set of programs, it was the task of the operating system to assign the programs to different memory regions, so that they could be executed concurrently. This was made difficult due to the fact that the execution time of a program might depend on the amount of memory available to it. Every program has a minimum space requirement, but if it is assigned to a larger memory region its execution time might increase or decrease.In this program, you have to determine optimal assignments of programs to memory regions. Your program is given the sizes of the memory regions available for the execution of programs, and for each program a description of how its running time depends on the amount of memory available to it. Your program has to find the execution schedule of the programs that minimizes the average turnaround time for the programs. An execution schedule is an assignment of programs to memory regions and times, such that no two programs use the same memory region at the same time, and no program is assigned to a memory region of size less than its minimum memory requirement. The turnaround time of the program is the difference between the time when the program was submitted for execution (which is time zero for all programs in this problem), and the time that the program completes execution.InputThe input data will contain multiple test cases. Each test case begins with a line containing a pair of integers m and n. The number m specifies the number of regions into which primary memory has been partitioned (1 ≤ m ≤ 10), and n specifies the number of programs to be executed (1 ≤ n ≤ 50).The next line contains m positive integers gi…

UVA1411 Ants（二分图最优匹配/最小权值匹配）
type: item
date: 2018-08-24T21:24:00+08:00
description: AntsTime Limit: 5000MSMemory Limit: 65536KTotal Submissions: 7479Accepted: 2368DescriptionYoung naturalist Bill studies ants in school. His ants feed on plant-louses that live on apple trees. Each ant colony needs its own apple tree to feed itself.Bill has a map with coordinates of n ant colonies and n apple trees. He knows that ants travel from their colony to their feeding places and back using chemically tagged routes. The routes cannot intersect each other or ants will get confused and get to the wrong colony or tree, thus spurring a war between colonies.Bill would like to connect each ant colony to a single apple tree so that all n routes are non-intersecting straight lines. In this problem such connection is always possible. Your task is to write a program that finds such connection.On this picture ant colonies are denoted by empty circles and apple trees are denoted by filled circles. One possible connection is denoted by lines.InputThe first line of the input file contains a single integer number n (1 ≤ n ≤ 100) — the number of ant colonies and apple trees. It is followed by n lines describing n ant colonies, followed by n lines describing n apple trees. Each ant colony and apple tree is described by a pair of integer coordinates x and y (−10 000 ≤ x, y ≤ 10 000) on a Cartesian plane. All ant colonies and apple trees occupy distinct points on a plane. No three points are on the same line.OutputWrite to the output file n lines with one integer number on each line. The number written on i-th line denotes the number (from 1 to n) of the apple tree that is connected to the i-th ant colony.Sample Input5 -42 58 44 86 7 28 99 34 -13 -59 -47 -44 86 74 68 -75 -68 60 99 -60Sample Output4 2 1 5 3SourceNortheastern Europe 2007链接https://vjudge.net/problem/UVA-1411题意给出n个白点和n个黑点的坐标，要求用n条不相交的线段把它们连接起来，其中每条线段恰好连接一个白点和一个黑点，每个点恰好连接到一条线段。题解因为结点有黑白两色，我们不难想到构造一个二分图，其中每个白点对应一个X结点，每个黑点对应一个Y结点，每个黑点和每个白点相连，权值等于二者的欧几里得距离的相反数，跑一遍二分图最大权值匹配就能得到答案。假设在匹配中有$a_1-b_1$和$a_2-b_2$相交，那么$dist(a_1,…

UVA10537 The Toll! Revisited（最短路）
type: item
date: 2018-08-24T14:55:00+08:00
description: The Toll! RevisitedInputThe input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.The first line of the roadmap contains an integer n, which is the number of roads in the map(0 ≤ n). Each of the next n lines contains exactly two letters representing the two endpoints of a road.A capital letter represents a town; a lower case letter represents a village. Roads can be traveled in either direction.Following the roadmap is a single line for the delivery details. This line consists of three things: an integer p (0 < p < 1000000000) for the number of items that must be delivered, a letter for the starting place, and a letter for the place of delivery. The roadmap is always such that the items can be delivered.The last test case is followed by a line containing the number ‘-1’.OutputThe output consists of three lines for each test case. First line displays the case number, second lineshows the number of items required at the beginning of the journey and third line shows the pathaccording to the problem statement above. Actually, the path contains all the city/village names thatSindbad sees along his journey. Two consecutive city/village names in the path are separated by ahyphen.Sample Input1 a Z 19 a Z 5 A D D X A b b c c X 39 A X -1Sample OutputCase 1: 20 a-Z Case 2: 44 A-b-c-X链接https://cn.vjudge.net/problem/UVA-10537题意运送货物需要缴纳过路费。进入一个村庄需要缴纳一单位的货物，而进入一个城镇时，每20个单位的货物中就要上缴一个单位(70 = 20 + 20 + 20 + 10 = 1 + 1 + 1 + 1 = 4)。现给定一个起点和终点，输出一条缴纳过路费最少的路线，有多条路线时输出字典序最小的。题解尽管和普通的最短路不尽相同，本题仍然可以用Dijkstra算法的思路解决，所不同的是需进行逆推而非顺推。令d[i]表示进入节点i之后，至少要有d[i]单位的货物，到达目的地时货物数量才足够，则每次选择一个d[i]最小的未标号结点，更新它的所有前驱结点的d值即可算出所有的d值，然后在输出路径时根据d值可以直接构造字典序最小解。需要注意的是，d[i]可能会超过无符号32位证书的范围，需要用long long。——小白书P332本题的坑点除了long long外，还需注意到达城镇u时，下一个点v至少需要多少货物。假设我们到达u时至少需要100，那么按照100计算的话，在点u处需要缴纳5的过路费，即d[u] = 100，d[v] = 105，实际上从v到u时，需要缴纳105(1+1+1+1+1+1=6)的过路费，因为那个过路费5也需要缴纳1过路费。所以实际计算的时候不能用20来算，我们看有多少个19，就缴纳多少的过路费。即$d[v] = d[u] + \frac{d[u]+18}{19}$。如果是村庄…

UVALive8456 The Maximum Unreachable Node Set（floyd传递闭包+二分图最大匹配）
type: item
date: 2018-08-24T10:27:00+08:00
description: The Maximum Unreachable Node SetIn this problem, we would like to talk about unreachable sets of a directed acyclic graph G = (V,E). In mathematics a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is a graph such that there is no way to start at any node and follow a consistently-directed sequence of edges in E that eventually loops back to the beginning again.A node set denoted by $V_{U}R⊂V$ containing several nodes is known as an unreachable node set of G if, for each two different nodes u and v in $V_{UR}$, there is no way to start at u and follow a consistently-directed sequence of edges in E that finally archives the node v. You are asked in this problem to calculate the size of the maximum unreachable node set of a given graph G.InputThe input contains several test cases and the first line contains an integer T(1≤T≤500) which is the number of test cases.For each case, the first line contains two integers nn(1≤n≤100) and m(0≤m≤n(n−1)/2) indicating the number of nodes and the number of edges in the graph G. Each of the following mm lines describes a directed edge with two integers u and v (1≤u,v≤n and u≠v) indicating an edge from the u-th node to the v-th node. All edges provided in this case are distinct.We guarantee that all directed graphs given in input are DAGs and the sum of m in input is smaller than 500000.OutputFor each test case, output an integer in a line which is the size of the maximum unreachable node set of GG.样例输入3 4 4 1 2 1 3 2 4 3 4 4 3 1 2 2 3 3 4 6 5 1 2 4 2 6 2 2 3 2 5样例输出2 1 3链接https://cn.vjudge.net/problem/UVALive-8456【玄学WA】https://nanti.jisuanke.com/t/19979【可交题】题意给定一个有向无环图，求最大不可到达的点集（对于集合中任意两点u、v，不能从点u出发到达点v）。题解使用Floyd求传递闭包得到可达矩阵，然后跑一遍二分图最大匹配，答案就是顶点数减去二分图最大匹配。其实就是顶点数减去最小路径覆盖，有点最大独立集的感觉。二分图：任意一张图，若能将所有顶点分为两个互斥的集合，每个集合内的点两两互不相连，则可看做二分图（二部图）根据题意，计算图的可达性矩阵，用此矩阵作为二分图，就可用匈牙利算法算出二分图的最大匹配数res，注意res是匹配成功的有向边的数目，所以最多有res个点可以被到达（或者说有res个点可以出去）不能被到达的点，就可以抠出来，作为符合本题的那个点集合。另一种理解，匹配完边之后，有n-res个点没有被到达，也就是可以有从这n-res个点起始的n-…

UVA1416 Warfare And Logistics（最短路/树）
type: item
date: 2018-08-23T16:23:00+08:00
description: Warfare And LogisticsThe army of United Nations launched a new wave of air strikes on terroristforces. The objective of the mission is to reduce enemy's logistical mobility. Each airstrike will destroy a path and therefore increase the shipping cost of the shortest pathbetween two enemy locations. The maximal damage is always desirable.Let's assume that there are n enemy locations connected by m bidirectional paths,each with specific shipping cost. Enemy's total shipping cost is given as $\sum_{i=1}^{n}\sum_{j=1}^{n}path(i, j)$. Here path(i, j) is the shortest path between locations i and j. In case i and j are not connected, path(i, j) = L. Each air strike can only destroy one path. The total shipping cost after the strike is noted as c'. In order to maximizedthe damage to the enemy, UN's air force try to find the maximal c' - c.InputThe first line ofeach input case consists ofthree integers: n, m, and L. $1 < n <= 100,1 <= m <= 1000, 1 <= L <= 10^8$. Each ofthe following m lines contains three integers: a,b, s, indicating length of the path between a and b.OutputFor each case, output the total shipping cost before the air strike and the maximaltotal shipping cost after the strike. Output them in one line separated by a space.Sample Input4 6 1000 1 3 2 1 4 4 2 1 3 2 3 3 3 4 1 4 2 2Sample Output28 38链接https://cn.vjudge.net/problem/UVA-1416题意给出一个n个点m条边的带权无向图，令c等于每对结点之间的最短路径之和。要求删除一条边后使得新的c值c'最大。不连通两点的最长路视为L。题解如果用floyd算法计算c，每尝试着删除一条边都要重新计算一次，时间复杂度为$O(n^3m)$，很难承受。如果用n次Dijkstra计算单源最短路，时间复杂度为$O(nm^2logn)$。虽然看上去比$O(n^3m)$略好，但由于floyd算法的常数很小，实际运行时间差不多。这时候，最短路树派上用场了。因为在源点确定的情况下，只要最短路树不被破坏，起点到所有点的距离都不会发生改变。换句话说，只有删除最短路树上的n-1条边，最短路树才需要重新计算。这样，对于每个源点，最多只需要求n次而不是m次单源最短路，时间复杂度降为$O(n^2mlogn)$，可以承受。注意：如果有重边，删除一条边时，应该用第二短的边代替。最短路树。用Dijkstra算法可以求出单源最短路树，方法是在发现$d[i]+w(ij)<d[j]$时除了更新d[j]之外还要设置p[i]=j。这样，把p看成是父指针，则所有点形成了一棵树。这样，要从起点出发沿最短路走到任意其他点，只需要顺着树上的边走即可。前面的Dijkstra算法的代码已经求出了p数组。——小白书P330还是使用堆优化的dijkstra跑最短路，但是每条边加一个状态记录边的编号，在跑最短路的时候把最短路上的边都记录下来，然后删除这些边重新计算。有一位老哥关于本题的代码写的很好：传送门。代码Stat…

UVA11374 Airport Express（最短路）
type: item
date: 2018-08-20T13:50:00+08:00
description: Airport ExpressIn a small city called Iokh, a train service, Airport-Express, takes residents to the airport more quickly than other transports.There are two types of trains in Airport-Express, the Economy-Xpress and the Commercial-Xpress. They travel at different speeds, take different routes and have different costs.Jason is going to the airport to meet his friend. He wants to take the Commercial-Xpress which is supposed to be faster, but he doesn’t have enough money. Luckily he has a ticket for the Commercial-Xpress which can take him one station forward. If he used the ticket wisely, he might end up saving a lot of time. However, choosing the best time to use the ticket is not easy for him.Jason now seeks your help. The routes of the two types of trains are given. Please write a program to find the best route to the destination. The program should also tell when the ticket should be used.InputThe input consists of several test cases. Consecutive cases are separated by a blank line. The first line of each case contains 3 integers, namely N, S and E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ N), which represent the number of stations, the starting point and where the airport is located respectively.There is an integer M (1 ≤ M ≤ 1000) representing the number of connections between the stations of the Economy-Xpress. The next M lines give the information of the routes of the Economy-Xpress. Each consists of three integers X, Y and Z (X, Y ≤ N, 1 ≤ Z ≤ 100). This means X and Y are connected and it takes Z minutes to travel between these two stations.The next line is another integer K (1 ≤ K ≤ 1000) representing the number of connections between the stations of the Commercial-Xpress. The next K lines contain the information of the CommercialXpress in the same format as that of the Economy-Xpress.All connections are bi-directional. You may assume that there is exactly one optimal route to the airport. There might be cases where you MUST use your ticket in order to reach the airport.Out…

UVA11367 Full Tank? （最短路+dp）
type: item
date: 2018-08-18T20:31:00+08:00
description: Full Tank?DescriptionAfter going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.InputThe first line of input gives 1<=n<=1000 and 0<=m<=10000, the number of cities and roads. Then follows a line with n integers 1<=pi<=100, where pi is the fuel price in the ith city. Then follow m lines with three integers 0<=u, v < n and 1<=d<=100, telling that there is a road between u and v with length d. Then comes a line with the number 1<=q<=100, giving the number of queries, and q lines with three integers 1<=c<=100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.OutputFor each query, output the price of the cheapest trip from s to e using a car with the given capacity, or “impossible” if there is no way of getting from s to e with the given car.Sample Input5 5 10 10 20 12 13 0 1 9 0 2 8 1 2 1 1 3 11 2 3 7 2 10 0 3 20 1 4Sample Output170 impossibleSource2007 Nordic Collegiate Programming Contest链接https://cn.vjudge.net/problem/UVA-11367题意n个城市有m条道路。每个城市的油价不一样，给出起点s和终点t，以及汽车的油箱的容量，求从城市s到城市t 的最便宜路径。（一开始油箱是空的，你每次可以选择加多少升。假设每单位的距离消耗1L汽油）题解dijkstra的变形。用优先队列来维护当前花费的最小值。设dp[i][j]为到达城市i的消耗剩余汽油为j升的最小花费。那么，经过每一站时候，如果到下一站加油可能最优，那么就加。参考了题解：传送门。每次只加一单位的汽油，如果能够到达下一个节点就进行更新，如果不能到达就继续加油，使用优先队列维护，满足当前的消费为最低消费。其实就相当把一个点拆成一百个点（因为容量最多为100），把拆出来的点理解为一个状态，理解为求解不同状态之间的最短路。代码StatusAcceptedTime130msLength2470#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1010; const i…

UVA10054 The Necklace（欧拉回路）
type: item
date: 2018-07-26T16:11:00+08:00
description: The NecklaceMy little sister had a beautiful necklace made of colorful beads. Two successive beads in the necklace shared a common color at their meeting point. The figure below shows a segment of the necklace: But, alas! One day, the necklace was torn and the beads were all scattered over the floor. My sister did her best to recollect all the beads from the floor, but she is not sure whether she was able to collect all of them. Now, she has come to me for help. She wants to know whether it is possible to make a necklace using all the beads she has in the same way her original necklace was made and if so in which order the bids must be put. Please help me write a program to solve the problem.InputThe input contains T test cases. The first line of the input contains the integer T. The first line of each test case contains an integer N (5 ≤ N ≤ 1000) giving the number of beads my sister was able to collect. Each of the next N lines contains two integers describing the colors of a bead. Colors are represented by integers ranging from 1 to 50.OutputFor each test case in the input first output the test case number as shown in the sample output. Then if you apprehend that some beads may be lost just print the sentence “some beads may be lost” on a line by itself. Otherwise, print N lines with a single bead description on each line. Each bead description consists of two integers giving the colors of its two ends. For 1 ≤ i ≤ N1, the second integer on line i must be the same as the first integer on line i + 1. Additionally, the second integer on line N must be equal to the first integer on line 1. Since there are many solutions, any one of them is acceptable. Print a blank line between two successive test cases.Sample Input2 5 1 2 2 3 3 4 4 5 5 6 5 2 1 2 2 3 4 3 1 2 4Sample OutputCase #1 some beads may be lost Case #2 2 1 1 3 3 4 4 2链接https://cn.vjudge.net/problem/UVA-10054题意无向图求欧拉回路。题解首先判断一下每个点的度数是否都是偶数，如果出现奇数那就不会形成环。然后直接使用dfs或者Fleury算法求欧拉回路。注意：如果本题判断整个图是否连通的话，会有问题，因为可能一个单…