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题意给定一些客人的出行计划（开始时间，起点位置，终点位置），派最少的出租车去接这些客人。出租车接人的条件是：要么这位客人是着凉出租车接送的第一个人，要么在接送完上一个客人后，至少提前一分钟时间到达新客人的位置。题解建图，转化为DAG的最小路径覆盖。最小路径覆盖，就是在图中找尽量少的路径，使得每个结点恰好在一条路径上（即不同的路径不能有公共点），单独的结点也可以作为一条路径。本题中，“时间”是一个天然的序，因此可以构图如下：每个客人作为一个结点，如果同一个出租车在接完客人u后来得及接客人v，那么连边$u \rightarrow v$，不难发现，这个图是一个DAG，并且它的最小路径覆盖就是答案。最小路径覆盖等于总点数减去最大匹配，详情查看：传送门。注意，在建图的时候，条件应该是出租车接完客人u的时间加上u的终点到达v的时间小于v的开始时间。代码StatusAcceptedTime343msMemory2160kBLength2002#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 510; const int maxm = 250010; using namespace std; struct Edge { int to, next; }edge[maxm<<1]; int head[maxn], tot; int linker[maxn]; bool used[maxn]; struct Node { int hh, mm; int x1, y1, x2, y2; }node[maxn]; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } bool dfs(int u) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!used[v]) { used[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false; } int hungary(int n) // 最大匹配 { int res = 0; memset(linker, -1, sizeof(linker)); for (int u = 0; u < n; ++u) { memset(used, 0, sizeof(used)); if (dfs(u)) ++res; } return res; } int time_hours(Node a) { return a.hh * 60 + a.mm; } int time(Node a, Node b) { return abs(a.x1 - a.x2) + abs(a.y1 - a.y2) + abs(a.x2 - b.x1) + abs(a.y2 - b.y1); } int main() { // freopen("/Users/taifu/Codes/NOW/data.in", "r", stdin); // freopen("/Users/taifu/Codes/NOW/data.out","w",stdout); int T, m; scanf("%d", &T); while (T--) { init(); scanf("%d", &m); for (int i = 0; i < m; ++i) scanf("%d:%d %d%d%d%d", &node[i].hh, &node[i].mm, &node[i].x1, &node[i].y1, &node[i].x2, &node[i].y2); for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { if (time_hours(node[i]) + time(node[i], node[j]) < time_hours(node[j])) // 符合条件，连边 addedge(i, j); } } int ans = m - hungary(m); // 点数-最大匹配数 printf("%d\n", ans); } return 0; }因为边集数组开小了导致连边错误，找了一上午BUG。The end.2018-08-30 星期四
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就有可能私奔，这样就导致了婚姻的不稳定，稳定婚姻就是找到一种解决方案让婚姻稳定。算法：稳定婚姻的解决方法比较简单，通俗易懂，而且还容易实现，具体有没有固定的模板我不知道，没有去找，自己模拟的，在求解的过程中，我们先把所有的男生都加到队列里，队列里的就表示当前还单身的男生，每次从队列里拿出一个男生，然后从她最喜欢的女生开始匹配，如果当前的女生尝试追求过，那么就不用追求了，如果当前的女生没有伴侣，那么可以直接匹配上，如果有伴侣，那么就看看当前这个男生和女生之前的伴侣在那个女生中更喜欢谁，如果更喜欢当前的这个男生，那么当前男生就和这个女生匹配，女生之前匹配过的直接变成单身，被扔回队列，否则，继续找下一个女生，知道找到一个能匹配上的为止，就这样一直到队列空的时候，就已经全部匹配完成了。正确性：对于男生来说，每次都是从最喜欢的女生开始匹配的，遇到的第一个没人能抢走的并且稳定的就是自己最终伴侣，也就是说如果之前追求过的女生被别人抢走了，那么他将永远抢不会来，因为对于女生来说，第一次被男士按照自己的意愿选择之后，每次变更匹配对象都是在自己心目中更加喜欢的，所以一旦他放弃了某个男生，那么那个男生就没希望在和他匹配，这样男生是从最优的选的，保证男生不会出轨，女生每次都是在选择她的男生中选择最优的，这样也保证了女生最后没有怨言，这样的话，最后的到的婚姻就是稳定的，至于稳定婚姻，肯定会有稳定方案，这个我暂时证明不了，是看别人说的。——转载自：传送门，总结的不错。代码因为本题是求解的女生心中最满意的男生，而板子写的是男生心中最满意的女生，所以刚好反过来，“男生变女生，女生变男生”，得到的就是答案，小蓝书上的板子。StatusAcceptedTime190msLength1782#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int maxn = 1010; int pref[maxn][maxn], order[maxn][maxn], Next[maxn]; int future_husband[maxn], future_wife[maxn]; int n; queue <int> Q; // 未订婚男士队列 void engage(int man, int woman) // 订婚 { int m = future_husband[woman]; // 女士现任未婚夫m if (m) // 找到一个更爱她的，放弃原来的 { future_wife[m] = 0; // m加入未订婚男士队列 Q.push(m); } future_wife[man] = woman; future_husband[woman] = man; } void solve() { while (!Q.empty()) { int man = Q.front(); Q.pop(); int woman = pref[man][Next[man]++]; // 下一个求婚对象，从1开始 if (!future_husband[woman]) // 女士没有未婚夫，直接订婚 engage(man, woman); else if (order[woman][man] < order[woman][future_husband[woman]]) // 取代女士的现任未婚夫 engage(man, woman); else // 丑拒，下次再来 Q.push(man); } while (!Q.empty()) Q.pop(); } int main() { int T, x; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) scanf("%d", &pref[i][j]); // 编号为i的男士第j喜欢的人 Next[i] = 1; // 接下来应该向排名为1的女士求婚 future_wife[i] = 0; // 没有未婚妻 Q.push(i); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &x); order[i][x] = j; // 在编号为i的女士心目中，编号为x的男士的排名 } future_husband[i] = 0; // 没有未婚夫 } solve(); for (int i =1; i <= n; ++i) printf("%d\n", future_wife[i]); if (T) printf("\n"); } return 0; }The end.2018-08-28 星期二
UVA1006 Fixed Partition Memory Management（二分图最优匹配/最小权值匹配）
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 giving the sizes of the m memory regions. Following this are n lines, describing the time-space tradeoffs for each of the n programs. Each line starts with a positive integer k (k ≤ 10), followed by k pairs of positive integers s1, t1, s2, t2, . . . , sk, tk, that satisfy si < si+1 for 1 ≤ i < k. The minimum space requirement of the program is s1, i.e. it cannot run in a partition of size less than this number. If the program runs in a memory partition of size s, where si ≤ s < si+1 for some i, then its execution time will be ti . Finally, if the programs runs in a memory partition of size sk or more, then its execution time will be tk.A pair of zeroes will follow the input for the last test case.You may assume that each program will execute in exactly the time specified for the given region size, regardless of the number of other programs in the system. No program will have a memory requirement larger than that of the largest memory region.OutputFor each test case, first display the case number (starting with 1 and increasing sequentially). Then print the minimum average turnaround time for the set of programs with two digits to the right of the decimal point. Follow this by the description of an execution schedule that achieves this average turnaround time. Display one line for each program, in the order they were given in the input, that identifies the program number, the region in which it was executed (numbered in the order given in the input), the time when the program started execution, and the time when the program completed execution. Follow the format shown in the sample output, and print a blank line after each test case. If there are multiple program orderings or assignments to memory regions that yield the same minimum average turnaround time, give one of the schedules with the minimum average turnaround time.Sample Input2 4 40 60 1 35 4 1 20 3 1 40 10 1 60 7 3 5 10 20 30 2 10 50 12 30 2 10 100 20 25 1 25 19 1 19 41 2 10 18 30 42 0 0Sample OutputCase 1 Average turnaround time = 7.75 Program 1 runs in region 1 from 0 to 4 Program 2 runs in region 2 from 0 to 3 Program 3 runs in region 1 from 4 to 14 Program 4 runs in region 2 from 3 to 10 Case 2 Average turnaround time = 35.40 Program 1 runs in region 2 from 25 to 55 Program 2 runs in region 2 from 0 to 25 Program 3 runs in region 3 from 0 to 19 Program 4 runs in region 3 from 19 to 60 Program 5 runs in region 1 from 0 to 18链接https://cn.vjudge.net/problem/UVALive-2238题意编程计算最优的内存分配策略，即给定m个区域的大小和n个程序在各种内存环境下的运行时间，找出一个调度方案，使得平均回转时间（即平均结束时刻）尽量小，具体来说，你需要给每个程序分配一个内存区域，使得没有两个程序在同一时间运行在同一个内存区域中，而所有程序分配的区域大小都不小于该程序的最低内存需求。程序对内存的需求不会超过最大内存块的大小。题解先来看一个内存区域的情况，假设在这个内存区域按顺序执行的k个程序的运行时间分别为$t_1, t_2, t_3, ..., t_k$，那么第i个程序的回转时间为$r_1 = t_1+t_2+...+t_i$，所有程序的回转时间之和等于$r = kt_1+(k-1)t_2 + (k-2)t_3 + ... + 2t_{k-1} + t_k$。换句话说，如果程序i是内存区域j的倒数第p个执行的程序，则它对于总回转时间的“贡献值”为$pT_{i, j}$，其中$T_{i,j}$为程序i在内存区域j中的运行时间。这样一来，算法就比较明显了，构造二分图G，X结点为n个程序，Y结点为n*m个“位置”，其中位置(j, p)表示第j个内存区域的倒数第p个执行的程序。每个X结点i和Y结点(j, p)连一条权为$pT_{i, j}$的边，然后求最小权匹配即可。注意，并不是每个匹配都对应一个合法方案，但是最佳匹配一定对应一个合法方案，把倒数第1个程序放到倒数第2个程序处，显然运行时间将减少，因此最佳方案不可能只有倒数第1个程序，而没有倒数第2个程序。——刘汝佳小白书P352因为匹配的信息保存在Y结点（n*m个位置）中，所以我们可以遍历m个内存块，找到这些位置保存的n个程序的信息（只有n个程序，所以只有n个位置成功匹配），然后记录每个程序所在的内存编号以及开始时间，注意，内存中存的程序信息是倒序的，详情参看代码output部分。更详细的题解和说明可以看网上的博客：传送门1，传送门2。首先，我们可以证明最佳完美匹配一定是满足题意的一个解。因为我们采用了倒数第p个这样的设定。那么对应边权pT(i,j)中，T(i,j)一定是一个定值。那么自然是p越小越好。所以是先有了倒数第一才会有倒数第二。而不会只有倒数第一，没有倒数第二，又有倒数第三的不符合现实的情况。这在其他完美匹配就有可能出现，但最佳匹配避免开了这种情况。 采用倒数还有一个好处是如果是设位置为(i,j,k)。表示在内存i中总共有j个程序要执行，该程序是第k个，那么对应边权为（j-k+1)*T(i,k),似乎也行。但是这种设定每个程序也可以和(i,j+1,k+1)匹配。反正在同一个内存中运行时间是固定的。匹配数巨大，也有可能出现不合常理的情况。给写代码带来困扰。代码两种写法的最主要的区别就是在于输出方案判断右边内存区域匹配的程序。法一是通过添加虚拟边判断if (Left >= n) // 匹配到虚拟结点，说明本region已经没有更多程序了实现的，法二直接判断if (linker[Right] == -1) // 未匹配到跳过。实测法二43ms左右，法一253ms左右。写法一：n*m（左，n个程序+虚拟结点）——n*m（右，m块内存每块n个区域）StatusAcceptedTime253msLength4680#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> using namespace std; const int maxn = 1010; const int maxp = 50 + 5; const int maxr = 10 + 5; const int inf = 0x3f3f3f3f; int nx, ny, n, m; int G[maxn][maxn], runtime[maxp][maxr]; int linker[maxn], lx[maxn], ly[maxn], slack[maxn]; bool visx[maxn], visy[maxn]; bool dfs(int x) { visx[x] = true; for (int y = 0; y < ny; ++y) { if (visy[y] || !G[x][y]) // 注意这里需要判断x和y之间是否有边或者每条边初始化为-inf continue; int tmp = lx[x] + ly[y] - G[x][y]; if (tmp == 0) { visy[y] = true; if (linker[y] == -1 || dfs(linker[y])) { linker[y] = x; // 匹配 return true; } } else if (slack[y] > tmp) slack[y] = tmp; } return false; } void KM() // 二分图最大权值匹配 { memset(linker, -1, sizeof(linker)); memset(ly, 0, sizeof(ly)); for (int i = 0; i < nx; ++i) { lx[i] = -inf; for (int j = 0; j < ny; ++j) { if (G[i][j] > lx[i]) lx[i] = G[i][j]; } } for (int x = 0; x < nx; ++x) { for (int i = 0; i < ny; ++i) slack[i] = inf; while (true) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if (dfs(x)) break; int d = inf; for (int i = 0; i < ny; ++i) { if (!visy[i] && d > slack[i]) d = slack[i]; } for (int i = 0; i < nx; ++i) { if (visx[i]) lx[i] -= d; } for (int i = 0; i < ny; ++i) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } } void output() // 具体方案 { int start[maxp], region_number[maxp], total = 0; // 程序p开始时间，所在内存编号，总时间 for (int region = 0; region < m; region++) // 起始时刻、分配到得区域编号、总回转时间 { vector <int> programs; // 本region执行的所有程序，按照逆序排列（因为是指“倒数”第pos个程序） for (int pos = 0; pos < n; pos++) { int Right = region * n + pos; int Left = linker[Right]; if (Left >= n) // 匹配到虚拟结点，说明本region已经没有更多程序了 break; programs.push_back(Left); // 保存程序 region_number[Left] = region; // 记录编号 total -= G[Left][Right]; // 计算时间 } reverse(programs.begin(), programs.end()); int time = 0; for (int i = 0; i < programs.size(); ++i) // 每个程序开始时间 { start[programs[i]] = time; time += runtime[programs[i]][region]; } } printf("Average turnaround time = %.2f\n", (double)total / n); for (int p = 0; p < n; ++p) printf("Program %d runs in region %d from %d to %d\n", p + 1, region_number[p] + 1, start[p], start[p] + runtime[p][region_number[p]]); printf("\n"); } int main() { int kase = 0; while (scanf("%d%d", &m, &n) != EOF && n && m) { memset(G, 0, sizeof(G)); memset(runtime, 0, sizeof(runtime)); nx = n * m, ny = n * m; int size[maxr]; for (int region = 0; region < m; ++region) scanf("%d", &size[region]); for (int program = 0; program < n; ++program) // 计算程序P在区域R的运行时间 { int s[10], t[10], k; scanf("%d", &k); for (int i = 0; i < k; ++i) scanf("%d%d", &s[i], &t[i]); for (int region = 0; region < m; region++) { int & time = runtime[program][region]; time = inf; if (size[region] < s[0]) // 内存不足s[0]时无法运行 continue; for (int i = 0; i < k; ++i) { if (i == k - 1 || size[region] < s[i + 1]) // 内存满足s[i] <= s < s[i+1]时运行时间为ti，内存至少为s[k]，运行时间为tk { time = t[i]; break; } } // 连边X(program) -> Y(region,pos) 程序p在内存r的倒数第p个位置的运行时间 for (int pos = 0; pos < n; ++pos) G[program][region * n + pos] = -(pos + 1) * time; // 最小权值匹配，取相反数 } } for (int i = n; i < n * m; ++i) // 虚拟结点补全二分图 for (int j = 0; j < n * m; ++j) G[i][j] = 1; KM(); printf("Case %d\n", ++kase); output(); } return 0; }写法二：n（左，n个程序）——n*m（右，m块内存每块n个区域）StatusAcceptedTime43msLength4720#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> using namespace std; const int maxn = 1010; const int maxp = 50 + 5; const int maxr = 10 + 5; const int inf = 0x3f3f3f3f; int nx, ny, n, m; int G[maxn][maxn], runtime[maxp][maxr]; int linker[maxn], lx[maxn], ly[maxn], slack[maxn]; bool visx[maxn], visy[maxn]; bool dfs(int x) { visx[x] = true; for (int y = 0; y < ny; ++y) { if (visy[y]) // 注意这里需要判断x和y之间是否连边 continue; int tmp = lx[x] + ly[y] - G[x][y]; if (tmp == 0) { visy[y] = true; if (linker[y] == -1 || dfs(linker[y])) { linker[y] = x; // 匹配 return true; } } else if (slack[y] > tmp) slack[y] = tmp; } return false; } void KM() // 二分图最大权值匹配 { memset(linker, -1, sizeof(linker)); memset(ly, 0, sizeof(ly)); for (int i = 0; i < nx; ++i) { lx[i] = -inf; for (int j = 0; j < ny; ++j) { if (G[i][j] > lx[i]) lx[i] = G[i][j]; } } for (int x = 0; x < nx; ++x) { for (int i = 0; i < ny; ++i) slack[i] = inf; while (true) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if (dfs(x)) break; int d = inf; for (int i = 0; i < ny; ++i) { if (!visy[i] && d > slack[i]) d = slack[i]; } for (int i = 0; i < nx; ++i) { if (visx[i]) lx[i] -= d; } for (int i = 0; i < ny; ++i) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } } void output() // 具体方案 { int start[maxp], region_number[maxp], total = 0; // 程序p开始时间，所在内存编号，总时间 // for (int i = 0; i < nx; ++i) // total -= lx[i]; // for (int j = 0; j < ny; ++j) // total -= ly[j]; for (int i = 0; i < ny; ++i) if (linker[i] != -1) total -= G[linker[i]][i]; for (int region = 0; region < m; region++) // 起始时刻、分配到得区域编号、总回转时间 { vector <int> programs; // 本region执行的所有程序，按照逆序排列（因为是指“倒数”第pos个程序） for (int pos = 0; pos < n; pos++) { int Right = region * n + pos; int Left = linker[Right]; if (linker[Right] == -1) // 未匹配到跳过 continue; programs.push_back(Left); // 保存程序 region_number[Left] = region; // 记录编号 } reverse(programs.begin(), programs.end()); int time = 0; for (int i = 0; i < programs.size(); ++i) // 每个程序开始时间 { start[programs[i]] = time; time += runtime[programs[i]][region]; } } printf("Average turnaround time = %.2f\n", (double)total / n); for (int p = 0; p < n; ++p) printf("Program %d runs in region %d from %d to %d\n", p + 1, region_number[p] + 1, start[p], start[p] + runtime[p][region_number[p]]); printf("\n"); } int main() { int kase = 0; while (scanf("%d%d", &m, &n) != EOF && n && m) { for (int i = 0; i < n*m; ++i) for (int j = 0; j < n*m; ++j) G[i][j] = -inf; memset(runtime, 0, sizeof(runtime)); nx = n, ny = n * m; int size[maxr]; for (int region = 0; region < m; ++region) scanf("%d", &size[region]); for (int program = 0; program < n; ++program) // 计算程序P在区域R的运行时间 { int s[10], t[10], k; scanf("%d", &k); for (int i = 0; i < k; ++i) scanf("%d%d", &s[i], &t[i]); for (int region = 0; region < m; region++) { int & time = runtime[program][region]; time = inf; if (size[region] < s[0]) // 内存不足s[0]时无法运行 continue; for (int i = 0; i < k; ++i) { if (i == k - 1 || size[region] < s[i + 1]) // 内存满足s[i] <= s < s[i+1]时运行时间为ti，内存至少为s[k]，运行时间为tk { time = t[i]; break; } } // 连边X(program) -> Y(region,pos) 程序p在内存r的倒数第p个位置的运行时间 for (int pos = 0; pos < n; ++pos) G[program][region * n + pos] = -(pos + 1) * time; // 最小权值匹配，取相反数 } } KM(); printf("Case %d\n", ++kase); output(); } return 0; }一开始按照刘汝佳老师的代码写的，KM算法是用的kuangbin的板子，但是连样例都过不了，我拿两份代码测试样例，发现加的边以及权值都是一样的，就是有问题，弄得我还以为bin聚的板子有问题。实际上并不一样，因为刘老师的写法除了一个邻接矩阵W来保存边权信息外，还有一个vector邻接表，实际上在跑最大权值匹配的时候是用邻接表来遍历边的，而我只用了一个邻接矩阵来保存边权信息，然后这里就出现问题了，实际上有些点之间并没有连边，比如有些程序的最低内存需求大于某个内存块的内存，这时候这两点之间就没有边，再加上我初始化二维数组是清为0，所以导致匹配出错，无法得到正确结果，后面终于发现了这个错误，太不容易了。这道题的关键还是在于建图转化为二分图匹配，还有一点就是输出分配方案。The end.2018-08-26 星期日
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, b_1)+dist(a_2,b_2)$一定大于$dist(a_1, b_2)+dist(a_2,b_1)$，因此如果把这两条线段改成$a_1-b_2$和$a_2-b_1$后总长度会变小，与“最大权值”矛盾，所以我们实际上求的是是二分图最小权值匹配，匹配中不会出现线段相交的情况。代码StatusAcceptedTime30msLength2697#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> using namespace std; const int maxn = 110; const double inf = 0x3f3f3f3f * 1.0; int nx, ny, n; double G[maxn][maxn], lx[maxn], ly[maxn], slack[maxn]; int linker[maxn]; bool visx[maxn], visy[maxn]; bool eq(double a, double b) { return fabs(a - b) < 1e-9; } bool dfs(int x) { visx[x] = true; for (int y = 0; y < ny; ++y) { if (visy[y]) continue; double tmp = lx[x] + ly[y] - G[x][y]; if (eq(lx[x] + ly[y], G[x][y])) { visy[y] = true; if (linker[y] == -1 || dfs(linker[y])) { linker[y] = x; // 匹配 return true; } } else if (slack[y] > tmp) slack[y] = tmp; } return false; } void KM() // 二分图最大权值匹配 { memset(linker, -1, sizeof(linker)); for (int i = 0; i < nx; ++i) { lx[i] = -inf; for (int j = 0; j < ny; ++j) { ly[j] = 0; if (G[i][j] > lx[i]) lx[i] = G[i][j]; } } for (int x = 0; x < nx; ++x) { for (int i = 0; i < ny; ++i) slack[i] = inf; while (true) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if (dfs(x)) break; double d = inf; for (int i = 0; i < ny; ++i) { if (!visy[i] && d > slack[i]) d = slack[i]; } for (int i = 0; i < nx; ++i) { if (visx[i]) lx[i] -= d; } for (int i = 0; i < ny; ++i) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } } double distance(int x1, int y1, int x2, int y2) { return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2)); } struct Node { int x, y; }nodea[maxn], nodeb[maxn]; int main() { int cnt = 0; while (scanf("%d", &n) != EOF) { if (cnt++ > 0) printf("\n"); nx = ny = n; for (int i = 0; i < n; ++i) scanf("%d%d", &nodea[i].x, &nodea[i].y); for (int i = 0; i < n; ++i) scanf("%d%d", &nodeb[i].x, &nodeb[i].y); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) G[j][i] = -distance(nodea[i].x, nodea[i].y, nodeb[j].x, nodeb[j].y); KM(); // 权值取相反数，问的是i的匹配，所以用的是G[j][i]，也可以单独记录 for (int i = 0; i < n; ++i) printf("%d\n", linker[i] + 1); } return 0; }注意，必须得用两点间的欧几里得距离来求，因为是实际长度并非相对长度，我之前写的是return 1ll * (x1 - x2) * (x1 - x2) + 1ll * (y1 - y2) * (y1 - y2);WA到死。在这里分享一组数据。In.txt20 63 85 56 -51 79 98 -2 -47 76 -6 -96 -94 94 33 89 44 -40 -26 38 -28 -53 -83 91 -79 4 1 4 0 49 -31 -90 19 36 -97 23 60 18 13 -98 52 1 77 -54 45 99 -53 -88 -1 80 -15 -71 26 -59 -41 -45 -21 71 75 90 -47 100 14 -43 100 55 15 -5 -14 50 -53 19 -22 -37 56 -61 -33 -85 -52 -89 3out.txt12 15 9 8 5 19 11 13 4 16 7 3 2 14 10 20 18 1 17 6再分享一个刘汝佳老师的标程。// LA4043 Ants // Rujia Liu #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 100 + 10; const double INF = 1e30; int n; double W[maxn][maxn]; double Lx[maxn], Ly[maxn]; // 顶标 int left[maxn]; // left[i]为右边第i个点的匹配点编号 bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记 bool eq(double a, double b) { return fabs(a-b) < 1e-9; } bool match(int i){ S[i] = true; for(int j = 1; j <= n; j++) if (eq(Lx[i]+Ly[j], W[i][j]) && !T[j]){ T[j] = true; if (!left[j] || match(left[j])){ left[j] = i; return true; } } return false; } void update(){ double a = INF; for(int i = 1; i <= n; i++) if(S[i]) for(int j = 1; j <= n; j++) if(!T[j]) a = min(a, Lx[i]+Ly[j] - W[i][j]); for(int i = 1; i <= n; i++) { if(S[i]) Lx[i] -= a; if(T[i]) Ly[i] += a; } } void KM() { for(int i = 1; i <= n; i++) { left[i] = Lx[i] = Ly[i] = 0; for(int j = 1; j <= n; j++) Lx[i] = max(Lx[i], W[i][j]); } for(int i = 1; i <= n; i++) { for(;;) { for(int j = 1; j <= n; j++) S[j] = T[j] = 0; if(match(i)) break; else update(); } } } int main(){ int kase = 0; while(scanf("%d", &n) == 1) { if(++kase > 1) printf("\n"); int x1[maxn], y1[maxn], x2[maxn], y2[maxn]; for(int i = 1; i <= n; i++) scanf("%d%d", &x1[i], &y1[i]); for(int i = 1; i <= n; i++) scanf("%d%d", &x2[i], &y2[i]); for(int i = 1; i <= n; i++) // ant colony for(int j = 1; j <= n; j++) // apple tree W[j][i] = -sqrt((double)(x1[i]-x2[j])*(x1[i]-x2[j]) + (double)(y1[i]-y2[j])*(y1[i]-y2[j])); KM(); // 最大权匹配 for(int i = 1; i <= n; i++) printf("%d\n", left[i]); } return 0; }The end.2018-08-24 星期五
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}$。如果是村庄的话那么$d[v] = d[u] + 1$就行了。需要详细的说明可以参考博客：传送门。代码StatusAcceptedLength2538#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; typedef long long ll; const long long inf = (1ll << 62); const int maxn = 110; const int maxm = 1010; ll dist[maxn], D; bool vis[maxn]; int n, pre[maxn]; struct Node { int v; ll dis; Node(int _v, ll _dis): v(_v), dis(_dis) {} bool operator < (const Node & r) const { return dis > r.dis; } }; struct Edge { int to, cost; Edge(int _to): to(_to) {} Edge(int _to, int _cost): to(_to), cost(_cost) {} }; vector <Edge> edge[maxn]; void addedge(int u, int v) { edge[u].push_back(Edge(v)); } int char2int(char ch) // 字母转数字 { return ch - 'A'; } char int2char(int x) // 数字转字母 { return char(x + 65); } ll Cost(int u) // 到达点u时下一个点v的花费 { if (u < 26) // 大写字母-城镇 return dist[u] + (dist[u] + 18) / 19; return dist[u] + 1; // 村庄 } void dijkstra(int s) { for (int i = 0; i < maxn; ++i) // 点数，不为n { dist[i] = inf; vis[i] = false; pre[i] = -1; } dist[s] = D; priority_queue <Node> Q; Q.push(Node(s, dist[s])); while (!Q.empty()) { Node tmp = Q.top(); Q.pop(); int u = tmp.v; if (vis[u]) continue; vis[u] = true; for (int i = 0; i < edge[u].size(); ++i) { int v = edge[u][i].to; if (vis[v]) continue; ll cost = Cost(u); if (dist[v] > cost) // 更新到达v点所需要的最少货物 { pre[v] = u; // 记录前驱节点 dist[v] = cost; Q.push(Node(v, dist[v])); } else if (dist[v] == cost && u < pre[v]) // 相等时取字典序最小的 pre[v] = u; } } } int main() { int s, t, kase = 0; char s1[2], s2[2]; while (scanf("%d", &n)) { if (n == -1) break; for (int i = 0; i < maxn; ++i) // 注意点的范围 edge[i].clear(); for (int i = 1; i <= n; ++i) { scanf("%s%s", s1, s2); addedge(char2int(s1[0]), char2int(s2[0])); addedge(char2int(s2[0]), char2int(s1[0])); } scanf("%lld%s%s", &D, s1, s2); s = char2int(s1[0]), t = char2int(s2[0]); dijkstra(t); // 从终点开始逆序求最短路 printf("Case %d:\n", ++kase); printf("%lld\n", dist[s]); while (pre[s] != -1) // 逆序输出 { printf("%c-", int2char(s)); s = pre[s]; } printf("%c\n", int2char(t)); } return 0; }之前不知道long long inf = 1<<30会爆精度，实际上要用long long inf = 1ll<<30，然后由于数组初始化又错了一次，数组的范围并不是n。The end.2018-08-24 星期五
UVALive8456 The Maximum Unreachable Node Set（floyd传递闭包+二分图最大匹配）
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-res条路（平行的），从这n-res条路上各取一点，必定互不相连，故答案为n-res。——传送门代码#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 110; int G[maxn][maxn]; int n, m; int linker[maxn]; bool used[maxn]; void floyd() { for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { if (G[i][k]) { for (int j = 1; j <= n; ++j) if (G[k][j]) G[i][j] = 1; } } } } //void floyd() //{ // for (int k = 1; k <= n; ++k) // for (int i = 1; i <= n; ++i) // for (int j = 1; j <= n; ++j) // G[i][j] |= G[i][k] & G[k][j]; //} bool dfs(int u) { for (int i = 1; i <= n; ++i) { if (G[u][i] && !used[i]) { used[i] = true; if (linker[i] == -1 || dfs(linker[i])) { linker[i] = u; return true; } } } return false; } int solve() { int res = 0; memset(linker, -1, sizeof(linker)); for (int i = 1; i <= n; ++i) { memset(used, 0, sizeof(used)); if (dfs(i)) ++res; } return res; } int main() { int T, u, v; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); memset(G, 0, sizeof(G)); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); G[u][v] = 1; } floyd(); int ans = n - solve(); printf("%d\n", ans); } return 0; }Vjudge上交UVALive一直WA，找网上的代码也是WA，后面看了一下提交记录，貌似没有过的，玄学，可以去计蒜客或者中国石油大学OJ上交。The end.2018-08-24 星期五
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跑最短路，但是每条边加一个状态记录边的编号，在跑最短路的时候把最短路上的边都记录下来，然后删除这些边重新计算。有一位老哥关于本题的代码写的很好：传送门。代码StatusAcceptedTime200msLength2557#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 110; const int maxm = 1010; ll dist[maxn], ans[maxm]; bool vis[maxn]; int pre1[maxn], pre2[maxn]; int n, m, L; struct Node { int v; ll dis; Node(int _v, ll _dis): v(_v), dis(_dis) {} bool operator < (const Node & r) const { return dis > r.dis; } }; struct Edge { int to, id, cost; Edge(int _to, int _cost, int _id): to(_to), cost(_cost), id(_id) {} }; vector <Edge> edge[maxn]; void addedge(int u, int v, int w, int id) { edge[u].push_back(Edge(v, w, id)); } ll dijkstra(int s, int e) { for (int i = 0; i <= n; ++i) { dist[i] = inf; pre1[i] = 0; vis[i] = false; } dist[s] = 0; priority_queue <Node> Q; Q.push(Node(s, dist[s])); while (!Q.empty()) { Node tmp = Q.top(); Q.pop(); int u = tmp.v; if (vis[u]) continue; vis[u] = true; for (int i = 0; i < edge[u].size(); ++i) { int id = edge[u][i].id, v = edge[u][i].to; if (id == e) continue; if (!vis[v] && dist[v] > dist[u] + edge[u][i].cost) { dist[v] = dist[u] + edge[u][i].cost; pre1[v] = id; // 记录边的编号 Q.push(Node(v, dist[v])); } } } ll sum = 0; for (int i = 1; i <= n; ++i) // 从s出发的所有最短路 { if (dist[i] == inf) sum += L; else sum += dist[i]; } return sum; } void solve() { for (int i = 1; i <= n; ++i) { ll cost = dijkstra(i, 0); for (int j = 0; j <= m; ++j) // 不删边时的最短路和 ans[j] += cost; memcpy(pre2, pre1, sizeof(pre1)); // 将记录的最短路编号复制给pre2数组 for (int j = 1; j <= n; ++j) { if (pre2[j]) // 删除边pre2[j]后的最短路之和 ans[pre2[j]] += ((dijkstra(i, pre2[j])) - cost); } } } int main() { int u, v, w; while (scanf("%d%d%d", &n, &m, &L) != EOF) { for (int i = 0; i <= n; ++i) edge[i].clear(); for (int i = 0; i <= m; ++i) ans[i] = 0; for (int i = 1; i <= m; ++i) // 边的编号从1开始 { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w, i); addedge(v, u, w, i); } solve(); ll tmp = 0; for (int i = 1; i <= m; ++i) // 得到一个最大值 tmp = max(tmp, ans[i]); printf("%lld %lld\n", ans[0], tmp); // ans[0]表示不删边时任意两点的最短路之和 } return 0; }The end.2018-08-23 星期四
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.OutputFor each case, you should first list the number of stations which Jason would visit in order. On the next line, output ‘Ticket Not Used’ if you decided NOT to use the ticket; otherwise, state the station where Jason should get on the train of Commercial-Xpress. Finally, print the total time for the journey on the last line. Consecutive sets of output must be separated by a blank line.链接https://cn.vjudge.net/problem/UVA-11374题意n个车站，m条经济线，k条商业线，线路是双向的，每条线路花费时间不同，现在你有一张商业线机票，可以坐一站商业线，而其他时候只能乘坐经济线，假设换乘时间不计，任务是找一条去机场最快的路线（从s到t）。注意有可能必须乘坐商业线才能到达目的地，保证最优解唯一。输出线路、乘坐商业线的站点号和最短时间。题解因为商业线只能坐一站，所以可以枚举坐的是哪一站，比较所有可能性下的最优解。如果可以在$O(1)$时间内解决计算出每种方案对应的最优方案，整个问题就可以在$O(K)$时间内解决，假设我们用商业线车票从车站a坐到车站b，则从起点到a、从a到终点这两部分线路对于“经济线网络”来说都应该是最短路。换句话说，我们只要从起点开始、到终点结束做两次单源最短路，记录下从起点到每个点x的最短时间f(x)和从每个点x到终点的最短时间g(x)，则总时间为f(a)+T(a, b)+f(b)，其中T(a,b)为从a坐一站商业线到b的时间。算上预处理时间$O(mlogn)$，本算法的时间复杂度$O(mlongn + k)$。——小白书P329特别注意一下处理输出的路径，以及两个输出之间有一个空行。因为点数只有500，所以我用的是邻接矩阵版的dijkstra。代码StatusAcceptedLength3132#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 510; int n, m; int dist1[maxn], dist2[maxn], pre1[maxn], pre2[maxn]; bool vis[maxn]; int G[maxn][maxn]; vector <int> V1, V2; void dijkstra(int s, int dist[], int pre[]) // 最短路 { for (int i = 1; i <= n; ++i) { dist[i] = inf; vis[i] = false; pre[i] = -1; } dist[s] = 0; pre[s] = -1; for (int i = 1; i <= n; ++i) { int k = -1; int Min = inf; for (int j = 1; j <= n; ++j) { if (!vis[j] && dist[j] < Min) { Min = dist[j]; k = j; } } if (k == -1) break; vis[k] = true; for (int j = 1; j <= n; ++j) { if (!vis[j] && dist[k] + G[k][j] < dist[j]) { dist[j] = dist[k] + G[k][j]; pre[j] = k; } } } } int main() { // freopen("/Users/taifu/Codes/NOW/data.in", "r", stdin); // freopen("/Users/taifu/Codes/NOW/data.out","w",stdout); int s, t, k, u, v, w, a, b, kase = 0; while (scanf("%d%d%d", &n, &s, &t) != EOF) { ++kase; scanf("%d", &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) G[i][j] = (i == j ? 0 : inf); for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); G[u][v] = G[v][u] = w; } dijkstra(s, dist1, pre1); // 正向最短路 dijkstra(t, dist2, pre2); // 反向最短路 scanf("%d", &k); int pos = -1, dis = dist1[t], tmp; for (int i = 0; i < k; ++i) { scanf("%d%d%d", &u, &v, &w); tmp = dist1[u] + w + dist2[v]; if (tmp < dis) // 坐商业线更快 u->v { dis = dist1[u] + w + dist2[v]; pos = u; a = u, b = v; } tmp = dist1[v] + w + dist2[u]; if (tmp < dis) // 坐商业线更快 v->u { dis = dist1[v] + w + dist2[u]; pos = v; a = v, b = u; } } V1.clear(), V2.clear(); if (kase > 1) // 两个输出之间有一个空行 printf("\n"); if (pos == -1) // 不需要乘坐商业线 { for (int i = t; i != -1; i = pre1[i]) V1.push_back(i); printf("%d", V1[V1.size() - 1]); for (int i = V1.size() - 2; i >= 0; --i) // 直接输出正向路径 printf(" %d", V1[i]); printf("\n"); printf("Ticket Not Used\n"); } else // 乘坐商业线 { for (int i = a; i != -1; i = pre1[i]) V1.push_back(i); for (int i = b; i != -1; i = pre2[i]) V2.push_back(i); printf("%d", V1[V1.size() - 1]); for (int i = V1.size() - 2; i >= 0; --i) // 路径1->a->b->路径2 printf(" %d", V1[i]); for (int i = 0; i < V2.size(); ++i) printf(" %d", V2[i]); printf("\n"); printf("%d\n", pos); } printf("%d\n", dis); } }The end.2018-08-20 星期一
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 int maxm = 10010; int n, m, c; int head[maxn], tot; int dist[maxn][maxn]; // 到达第i点剩余油量为j的最小花费 int a[maxn]; struct Edge { int to, cost, next; }edge[maxm<<2]; struct Node { int idx, cost, cap; Node(){} Node(int _idx, int _cost, int _cap): idx(_idx), cost(_cost), cap(_cap){} bool operator < (const Node & r) const { return cost > r.cost; } }; void init() { memset(head, -1, sizeof(head)); tot = 0; } void addedge(int u, int v, int w) { edge[tot].to = v; edge[tot].cost = w; edge[tot].next = head[u]; head[u] = tot++; } int dijkstra(int s, int t) { priority_queue <Node> Q; for (int i = 0; i <= n; ++i) for (int j = 0; j < 110; ++j) // 最多为100 dist[i][j] = inf; while (!Q.empty()) Q.pop(); Q.push(Node(s, 0, 0)); // 从s开始，花费为0，剩余油量为0 while (!Q.empty()) { Node u = Q.top(); Q.pop(); int idx = u.idx, cost = u.cost, cap = u.cap; if (idx == t) // 到达t点，返回最小花费 return u.cost; // 在容量范围之内且比之前状态的花费大，更新 if (cap < c && dist[idx][cap + 1] > cost + a[idx]) // 加油，每次加1L { dist[idx][cap + 1] = cost + a[idx]; Q.push(Node(idx, dist[idx][cap + 1], cap + 1)); } for (int i = head[idx]; i != -1; i = edge[i].next) { int v = edge[i].to; if (cap < edge[i].cost) // 当前油量不够到达下一点 continue; if (dist[v][cap-edge[i].cost] > cost) // 到下一点的花费少于可以比记录的更少就更新 { dist[v][cap-edge[i].cost] = cost; Q.push(Node(v, cost, cap-edge[i].cost)); } } } return -1; } int main() { int s, t, u, v, w, q; while (scanf("%d%d", &n, &m) != EOF) { init(); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &u, &v, &w); u++, v++; // 下标 addedge(u, v, w); addedge(v, u, w); } scanf("%d", &q); while (q--) { scanf("%d%d%d", &c, &s, &t); s++, t++; // 下标 int ans = dijkstra(s, t); if (ans == -1) printf("impossible\n"); else printf("%d\n", ans); } } return 0; }打组队赛的时候在小白书上找到了原题，但是没有题解而且之前没有做过，实在是太难受了，更可惜的是，即使知道是最短路的题也不会写，完全不会图上的dp。The end.2018-08-18 星期六
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算法求欧拉回路。注意：如果本题判断整个图是否连通的话，会有问题，因为可能一个单独的连通分量构成一个欧拉回路，比如下面这组数据，来自uDebug。Input 1 4 1 2 2 1 3 4 4 3 Output Case #1 1 2 2 1代码直接BFSStatusAcceptedTime130msLength1322#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn = 60; int G[maxn][maxn]; int degree[maxn]; int n, m; void init() { memset(G, 0, sizeof(G)); memset(degree, 0, sizeof(degree)); } void Euler(int u) { for (int i = 1; i <= n; ++i) { if (G[u][i] > 0) { G[u][i]--; G[i][u]--; Euler(i); // 先dfs完，最后再进行逆序输出，不然可能会出现(1, 2)、(1, 3) printf("%d %d\n", i, u); } } } int main() { int u, v, T, s, kase = 0; scanf("%d", &T); while (T--) { bool flag = true; scanf("%d", &m); init(); n = 0; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); G[u][v]++; // 无向图可能存在重边 G[v][u]++; degree[u]++; degree[v]++; n = max(n, max(u, v)); s = u; } for (int i = 1; i <= n; ++i) { if ((degree[i] & 1)) // 欧拉回路要求所有点的度数均为偶数，出现度数为奇数 flag = false; } printf("Case #%d\n", ++kase); if (!flag) printf("some beads may be lost\n"); else Euler(s); if (T > 0) printf("\n"); } return 0; }使用Fleury算法StatusAcceptedTime126msLength2126#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn = 60; vector <int> V; int G[maxn][maxn]; int degree[maxn]; int ans[maxn*maxn]; // ans栈数组开小了玄学TLE int n, m, top; void init() { memset(G, 0, sizeof(G)); memset(degree, 0, sizeof(degree)); memset(ans, 0, sizeof(ans)); V.clear(); // V忘记初始化OLE玄学 } void dfs(int u) // 寻找一条路径 { ans[++top] = u; for (int i = 1; i <= n; ++i) { if (G[u][i] > 0) // “删边” { G[u][i]--; G[i][u]--; dfs(i); break; // 一条边 } } } void fleury(int u) { top = 1; ans[top] = u; while (top > 0) { int k = 0; for (int i = 1; i <= n; ++i) // 判断是否可扩展 { if (G[ans[top]][i] > 0) // 若存在一条从ans[top]出发的边 那么就可以扩展一条“回路” { k = 1; break; } } if (k == 0) // 没有其他的边了，不可扩展，保存结果 V.push_back(ans[top--]); else if (k == 1) // 对可扩展的路径进行dfs dfs(ans[top--]); } } int main() { //freopen("/Users/taifu/Codes/CPP/data.in", "r", stdin); //freopen("/Users/taifu/Codes/CPP/data.out","w",stdout); int u, v, T, s, kase = 0; scanf("%d", &T); while (T--) { bool flag = true; scanf("%d", &m); init(); n = 0; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); G[u][v]++; // 无向图可能存在重边 G[v][u]++; degree[u]++; degree[v]++; n = max(n, max(u, v)); } s = u; for (int i = 1; i <= n; ++i) { if ((degree[i] & 1)) flag = false; } if (!flag) printf("Case #%d\nsome beads may be lost\n", ++kase); else { fleury(s); printf("Case #%d\n", ++kase); printf("%d %d\n", V[0], V[1]); for (int i = 2; i < V.size(); ++i) printf("%d %d\n", V[i-1], V[i]); } if (T > 0) printf("\n"); } return 0; }附上判连通图的代码（WA）#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn = 60; vector <int> V; int G[maxn][maxn]; int degree[maxn]; int ans[maxn*maxn]; bool vis[maxn]; int n, m, top, cnt1, cnt2; void init() { cnt1 = cnt2 = 0; memset(vis, 0, sizeof(vis)); memset(G, 0, sizeof(G)); memset(degree, 0, sizeof(degree)); memset(ans, 0, sizeof(ans)); V.clear(); } void con_dfs(int u) { vis[u] = true; cnt2++; for (int i = 1; i <= n; ++i) { if (G[u][i] > 0 && !vis[i]) con_dfs(i); } } void dfs(int u) // 寻找一条路径 { ans[++top] = u; for (int i = 1; i <= n; ++i) { if (G[u][i] > 0) // “删边” { G[u][i]--; G[i][u]--; dfs(i); break; // 一条边 } } } void fleury(int u) { top = 1; ans[top] = u; while (top > 0) { int k = 0; for (int i = 1; i <= n; ++i) // 判断是否可扩展 { if (G[ans[top]][i] > 0) // 若存在一条从ans[top]出发的边 那么就可以扩展一条“回路” { k = 1; break; } } if (k == 0) // 没有其他的边了，不可扩展，保存结果 V.push_back(ans[top--]); else if (k == 1) // 对可扩展的路径进行dfs dfs(ans[top--]); } } int main() { //freopen("/Users/taifu/Codes/CPP/data.in", "r", stdin); //freopen("/Users/taifu/Codes/CPP/data.out","w",stdout); int u, v, T, s, kase = 0; scanf("%d", &T); while (T--) { bool flag = true; scanf("%d", &m); init(); n = 0; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); G[u][v]++; // 无向图可能存在重边 G[v][u]++; degree[u]++; degree[v]++; n = max(n, max(u, v)); if (!vis[u]) { cnt1++; vis[u] = true; } if (!vis[v]) { cnt1++; vis[v] = true; } } s = u; memset(vis, 0, sizeof(vis)); con_dfs(s); if (cnt1 != cnt2) // 判断是否连通 flag = false; for (int i = 1; i <= n; ++i) { if ((degree[i] & 1)) flag = false; } if (!flag) printf("Case #%d\nsome beads may be lost\n", ++kase); else { fleury(s); printf("Case #%d\n", ++kase); printf("%d %d\n", V[0], V[1]); for (int i = 2; i < V.size(); ++i) printf("%d %d\n", V[i-1], V[i]); } if (T > 0) printf("\n"); } return 0; }栈数组开小了导致TLE，玄学？保存结果的vector忘记初始化，OLE错误，判连通图WA。关于直接dfs和使用Fleury算法求欧拉路...关于逆序输出建议阅读这篇博客。The end.2018-07-26 星期四