POJ2449 Remmarguts' Date（k短路/A*+Dijkstra）
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短路模板题，dijkstra加A*算法解决。对于每个点，都有一个有g(n)和h(n)确定的f(n)，并以f(n)的参考权值确定搜索的方向，f(n) = g(n) + h(n)在这里，h(n)表示送起点S出发到n走过的路径长度，g(n)表示从n到终点T的最短路径的长度，在这个问题中g(n)是完美估价，搜索的方向一定是对的。第k短路可以理解为第k次找到终点，相当于终点被找到k次，即出队k次。——转载自：传送门关于A*算法的详细介绍可以参考：关于寻路算法的一些思考，模板可以使用：传送门。代码#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; const int maxn = 1010; const int inf = 0x3f3f3f3f; int n, m, s, t, k; bool vis[maxn]; int dist[maxn]; struct Node { int v, c; Node (int _v = 0, int _c = 0): v(_v), c(_c) {} bool operator < (const Node &rhs) const { return c + dist[v] > rhs.c + dist[rhs.v]; // 估价函数 fx = gx + hx 路径短先出队 } }; struct Edge { int to, cost; Edge (int _to = 0, int _cost = 0): to(_to), cost(_cost) {} }; vector <Edge> E[maxn], revE[maxn]; void addedge(int u, int v, int w) { E[v].push_back(Edge(u, w)); // 反向加边 revE[u].push_back(Edge(v, w)); // 正向加边 } void dijkstra(int s, int n) // 最短路 { for (int i = 0; i <= n; ++i) { vis[i] = false; dist[i] = inf; } 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 < E[u].size(); ++i) { int v = E[u][i].to, cost = E[u][i].cost; if (!vis[v] && dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; Q.push(Node(v, dist[v])); } } } } int astar(int s) { priority_queue <Node> Q; Q.push(Node(s, 0)); k--; while (!Q.empty()) { Node tmp = Q.top(); Q.pop(); int u = tmp.v; if (u == t) { if (k) --k; else // 第k次到达目标节点t return tmp.c; } for (int i = 0; i < revE[u].size(); ++i) { int v = revE[u][i].to, cost = revE[u][i].cost; Q.push(Node(v, tmp.c + cost)); } } return -1; } int main() { int u, v, w; while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i <= n; ++i) { E[i].clear(); revE[i].clear(); } for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } scanf("%d%d%d", &s, &t, &k); dijkstra(t, n); // t点到所有点的最短路 if (dist[s] == inf) printf("-1\n"); else { if (s == t) // 起点等于终点特判 ++k; printf("%d\n", astar(s)); } } return 0; }The end.2018-09-09 星期日
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 apart. The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.链接https://cn.vjudge.net/problem/POJ-3169【为什么是vjudge的链接呢，因为POJ挂了】题意n头奶牛，标号为1到n，排成一列，先给定其中一些奶牛的关系：ml，奶牛A和奶牛B的距离小于等于Dmd，奶牛A和奶牛B的距离大于等于D问符合关系下奶牛1和奶牛n的最大距离，无解输出-1，距离无限大输出-2。题解转化为差分约束使用最短路解，具体参考：传送门。代码未提交POJ、暂挂#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1010; struct Edge { int from, to; int dist; Edge(int _from, int _to, int _dist): from(_from), to(_to), dist(_dist) {} }; struct BellmanFord // 最短路 { int n, m; vector <Edge> edges; vector <int> G[maxn]; bool inq[maxn]; int d[maxn]; int p[maxn]; int cnt[maxn]; void init(int n) { this->n = n; for (int i = 0; i < n; ++i) G[i].clear(); edges.clear(); } void addedge(int from, int to, int dist) { edges.push_back(Edge(from, to, dist)); m = edges.size(); G[from].push_back(m - 1); } bool negativeCycle() { queue <int> Q; memset(inq, 0, sizeof(inq)); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) d[i] = inf; d[0] = 0; inq[0] = true; Q.push(0); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int i = 0; i < G[u].size(); ++i) { Edge & e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if (++cnt[e.to] > n) return true; } } } } return false; } }; int main() { // freopen("/Users/taifu/Codes/NOW/data.in", "r", stdin); // freopen("/Users/taifu/Codes/NOW/data.out","w",stdout); int n, ml, md, u, v, w; BellmanFord bm; while (scanf("%d%d%d", &n, &ml, &md) != EOF) { bm.init(n); for (int i = 0; i < ml; ++i) { scanf("%d%d%d", &u, &v, &w); u--, v--; bm.addedge(u, v, w); // u v w } for (int i = 0; i < md; ++i) { scanf("%d%d%d", &u, &v, &w); u--, v--; bm.addedge(v, u, -w); // v u -w } bool flag = bm.negativeCycle(); if (!flag) { if (bm.d[n-1] == inf) // 距离无限长 printf("-2\n"); else printf("%d\n", bm.d[n-1]); // 答案 } else // 存在负权回路 printf("-1\n"); } return 0; }贝尔曼福德算法的板子是刘老师小蓝书P332上的，有点小错误（d数组初始化以及s点入队），已修正，本题是在本地测试的官方数据，没有发现错误。详解（转载自传送门）1、因为我们要求1号牛和n号牛的最大距离，那么我们希望得到这样一个不等式(假设n==5)：①-⑤<=x，那么这个x就是1号牛和n号牛的最大距离。2、那么我们引入一个差分约束系统的相关概念：差分约束系统问题，能够将问题转化为最短路问题。以下给出转化过程：假设有这样的三个条件：$x_1 - x_2 <= k_1 $$x_2 - x_3 <= k_2$$x_1 - x_3 <= k_3$那么我们可以将不等式1和不等式2相加得到：$x_1 - x_3 <= k_1 + k_2$$x_1 - x_3 <= k_3$那么如果想要得到k1和k3的最大差值，那么其实就是取$min(k1+k2, k3)$，其实问题我们可以将问题转化成图论，将k1, k2, k3看成三个点k1, k2, k3，对应三条边的建立就根据三个不等式来建立，那么边权值如何取呢？显然我们想要最大差值，我们就需要取最大值。那么图可以建立成这样：那么我们上述过程将不等式1和不等式2相加，然后和不等式3比较值的过程，其实就是最短路计算过程中的判断能否松弛的过程。那么我们就可以根据不等式建立有向图，然后再通过有向图计算1号点到n号点的最短路，其值就是x1与xn的最大差值。3、然后我们再回归到这个问题上来。对应ml条信息：①牛A和牛B的距离不想超过D，那么建立不等式：posA-posB<=D;加入到图中直接add（A，B，D）即可、对应md条信息：②牛A和牛B的距离至少要为D，那么建立不等式：posA-posB>=D，那么我们左右两边同乘-1有：posB-posA<=-D，那么加入到图中add（B，A，-D）即可。4、图建立好之后直接跑最短路即可。对应输出：①如果dis【n】==inf，输出-2；②否则输出dis【n】；③如果在跑贝尔曼福德过程中发现了负环，说明问题无解，那么输出-1.The end.2018-09-05 星期三
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] > dist1[n]，那么保存值并更新，得到次短路，具体可参考：传送门。求次短路，可以通过求最短路得到次短路长度1到n的次短路长度必然产生于：从1走到x的最短路 + edge[x][y] + y到n的最短路首先预处理好1到每一个节点的最短路，和n到每一个节点的最短路然后枚举每一条边作为中间边（x，y）或者（y，x），如果加起来长度等于最短路长度则跳过，否则更新。从1走到x的最短路 + edgex + y到n的最短路 给dist[n] 比较 找大于dist[n] 且是最小的那一个代码Accepted 3612K 219MS 1749B#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; const int maxn = 5010; const int maxm = 100010; const int inf = 0x3f3f3f3f; int dist[maxn], dist2[maxn]; int n, m; struct Node { int v, dis; Node(int _v, int _dis): v(_v), dis(_dis) {} bool operator < (const Node & r) const { return dis > r.dis; } }; struct Edge { int to, cost; Edge(int _to, int _cost): to(_to), cost(_cost) {} }; vector <Edge> edge[maxn]; void addedge(int u, int v, int w) { edge[u].push_back(Edge(v, w)); } void dijkstra(int s) { for (int i = 0; i <= n; ++i) dist[i] = dist2[i] = inf; dist[s] = 0, dist2[s] = inf; priority_queue <Node> Q; Q.push(Node(s, dist[s])); while (!Q.empty()) { Node tmp = Q.top(); Q.pop(); int u = tmp.v, dis = tmp.dis; if (dis > dist2[u]) // 距离大于次短路 continue; for (int i = 0; i < edge[u].size(); ++i) { int v = edge[u][i].to, cost = edge[u][i].cost; int w = cost + dis; // 边权加上当前的一个最短/次短距离 if (dist[v] > w) // 更新最短路 { swap(dist[v], w); // 更新dist[v]/w Q.push(Node(v, dist[v])); } if (dist2[v] > w && dist[v] < w) // 更新次短路 { dist2[v] = w; Q.push(Node(v, dist2[v])); } } } } int main() { int u, v, w; while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } dijkstra(1); printf("%d\n", dist2[n]); } return 0; }或者使用两次dijkstra，然后一遍循环。int ans = inf, tmp; for (int i = 1; i <= n; ++i) { for (int j = 0; j < edge[i].size(); ++j) { int v = edge[i][j].to, w = edge[i][j].cost; tmp = dist1[i] + dist2[v] + w; if (tmp > dist1[n] && tmp < ans) ans = tmp; } }The end.2018-08-30 星期四
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 = 1; j <= n; ++j) { if (G[i][j] || G[j][i]) // i和j的关系确定 cnt++; } if (cnt == n - 1) // 该点和别的n-1个点的关系都确定 ++ans; } printf("%d\n", ans); } return 0; }一道大水题，了解一下floyd传递闭包。还有一道题，HDU1704 RANK ，为啥上面的代码蜜汁超时了呢！和下面的也差不了多少。#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int maxn = 510; int G[maxn][maxn]; int n, m; void floyd() // 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]) // i->k->j G[i][j] = 1; } } } } } 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 = 0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { if (!(G[i][j] || G[j][i])) // i和j的关系不确定 ans++; } } printf("%d\n", ans); } return 0; }The end.2018-08-23 星期四
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 with at most two digits after the decimal point, 10-2<=rate<=102, 0<=commission<=102. Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 104.OutputIf Nick can increase his wealth, output YES, in other case output NO to the output file.Sample Input3 2 1 20.0 1 2 1.00 1.00 1.00 1.00 2 3 1.10 1.00 1.10 1.00Sample OutputYESSourceNortheastern Europe 2001, Northern Subregion链接http://poj.org/problem?id=1860题意城市中有n种货币m个货币兑换点，货币兑换点的规则是：A兑换B，汇率为RAB，费用为CAB，B兑换A，汇率为RBA，费用为CBA。比如将100美元兑换成俄元，汇率是29.75，费用为0.39，那么可以兑换到(100-0.39)*29.75俄元。现在某人有第一些第S种货币，问能否在若干次交换后增加他的现金，这些现金最终仍是第S种货币。题解从第S类货币开始兑换其他货币，最后还是要换回第S种货币，所以至少存在一个环使得最后能回到S，但是要使得钱数增加，所以必须是正环。问题转化为判断图中是否存在正环，使用bellman_ford算法即可判断，SPFA同样适用。建图方式：n种货币看成n个结点，将每个兑换点转化为两条有向边。代码StatusAcceptedTime32msMemory688kBLength1664#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 110; double dist[maxn]; int n, m, s; double sval; struct Edge { int u, v; double val, cost; Edge () {} Edge (int _u = 0, int _v = 0, double _val = 0, double _cost = 0):u(_u), v(_v), val(_val), cost(_cost) {} }; vector <Edge> E; bool bellman_ford(int start) { // 与判断负权回路相反 for (int i = 1; i <= n; ++i) // 初始化为0 dist[i] = 0.0; dist[start] = sval; // 起点 for (int i = 1; i < n; ++i) { bool flag = false; for (int j = 0; j < E.size(); ++j) { int u = E[j].u, v = E[j].v; double val = E[j].val, cost = E[j].cost; if (dist[v] < (dist[u] - cost) * val) // 更新 { dist[v] = (dist[u] - cost) * val; flag = true; } } if (!flag) break; } for (int i = 0; i < E.size(); ++i) { int u = E[i].u, v = E[i].v; double val = E[i].val, cost = E[i].cost; if ((dist[u] - cost) * val > dist[v]) // 存在正权回路 return true; } return false; } int main() { int a, b; double va, ca, vb, cb; while (scanf("%d%d%d%lf", &n, &m, &s, &sval) != EOF) { E.clear(); for (int i = 0; i < m; ++i) { scanf("%d%d%f%f%f%f", &a, &b, &va, &ca, &vb, &cb); E.push_back(Edge(a, b, va, ca)); E.push_back(Edge(b, a, vb, cb)); } bool flag = bellman_ford(s); if (flag) printf("YES\n"); else printf("NO\n"); } return 0; }不知道为什么，在Vjudge交URAL的时候过不了，一直WA，但是在POJ上就能过，网上找的代码交URAL同样是WA。The end.2018-08-14 星期二
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 maxn = 110; const int inf = 0x3f3f3f3f; int match[maxn], cx[maxn], cy[maxn], slack[maxn]; int G[maxn][maxn]; // 边权 bool visx[maxn], visy[maxn]; int nx, ny, ans; char map[maxn][maxn]; struct Node { int x, y; }nodem[maxn], nodeh[maxn]; bool find(int x) { int tmp; visx[x] = 1; for (int y = 0; y < ny; ++y) { if (visy[y]) // 如果这个点已经访问过 continue; tmp = cx[x] + cy[y] - G[x][y]; if (tmp == 0) // (x, y)在相等子图中 { visy[y] = true; if (match[y] == -1 || find(match[y])) // 如果这个点未匹配或者能修改 { match[y] = x; return true; } } else if (slack[y] > tmp) // (x, y)不在相等子图中 slack[y] = tmp; } return false; } void KM() { for (int x = 0; x < nx; ++x) // 分别对左端点进行匹配 { for (int i = 0; i < ny; ++i) // 初始化 slack[i] = inf; while (true) { memset(visx, 0, sizeof(visx)); // 初始化，每次find()更新 memset(visy, 0, sizeof(visy)); if (find(x)) // 成功匹配后换下一个 break; int delat = inf; for (int i = 0; i < ny; ++i) // 计算delta值 { if (!visy[i] && delat > slack[i]) delat = slack[i]; } for (int i = 0; i < nx; ++i) { if (visx[i]) cx[i] -= delat; } for (int j = 0; j < ny; ++j) { if (visy[j]) cy[j] += delat; else slack[j] -= delat; } // 修改顶标后，要把所有的slack值都减去delta // 这是因为lx[i] 减小了delta // slack[j] = min(lx[i] + ly[j] -w[i][j]) } } } int main() { int r, c; while (scanf("%d%d", &r, &c) != EOF) { if (r == 0 && c == 0) return 0; ans = 0; int cntm = 0, cnth = 0; for (int i = 0; i < r; ++i) { scanf("%s", map[i]); for (int j = 0; j < c; ++j) { if (map[i][j] == 'm') // 记录小人 nodem[cntm].x = i, nodem[cntm++].y = j; else if (map[i][j] == 'H') // 记录房子 nodeh[cnth].x = i, nodeh[cnth++].y = j; } } nx = cntm, ny = cnth; for (int i = 0; i < nx; ++i) { for (int j = 0; j < ny; ++j) // 边权取负数 G[i][j] = -(abs(nodem[i].x - nodeh[j].x) + abs(nodem[i].y - nodeh[j].y)); } for (int i = 0; i < nx; ++i) { cx[i] = -inf; for (int j = 0; j < ny; ++j) { if (cx[i] < G[i][j]) cx[i] = G[i][j]; } } memset(match, -1, sizeof(match)); memset(cy, 0, sizeof(cy)); KM(); for (int i = 0; i < ny; ++i) { if (match[i] != -1) ans += G[match[i]][i]; } printf("%d\n", -ans); // 答案为相反数 } return 0; }之前是使用最小费用最大流来做的。The end.2018-08-01 星期三
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; // 点数 const int maxm = 100010; // 边数 const int inf = 0x3f3f3f3f; char map[maxn][maxn]; struct Node { int x, y; }nodem[maxn], nodeh[maxn]; struct Edge { int to, next, cap, flow, cost; }edge[maxm]; int head[maxn], pre[maxn], dis[maxn]; int n, m, tot; bool vis[maxn]; void init() { memset(head, -1, sizeof(head)); tot = 0; } void addedge(int u, int v, int cap, int cost) // 链式前向星存图 { edge[tot].to = v; edge[tot].cap = cap; edge[tot].cost = cost; edge[tot].flow = 0; edge[tot].next = head[u]; head[u] = tot++; } bool spfa(int s, int t) // spfa寻找最小费用增广路 { queue <int> Q; for (int i = 0; i <= n; ++i) { dis[i] = inf; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if (!vis[v]) { vis[v] = true; Q.push(v); } } } } if (pre[t] == -1) return false; return true; } int minCostMaxflow(int s, int t, int &mincost) // 计算费用 { int maxflow = 0; mincost = 0; while (spfa(s, t)) { int Min = inf; for (int i = pre[t]; i != -1; i = pre[edge[i^1].to]) // 每次增加的流量 Min = min(Min, edge[i].cap - edge[i].flow); for (int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; mincost += edge[i].cost * Min; } maxflow += Min; } return maxflow; } int main() { int r, c, cost, cap = 1, s, t; while (scanf("%d%d", &r, &c) == 2 && r && c) { init(); int cntm = 0, cnth = 0; for (int i = 1; i <= r; ++i) { scanf("%s", map[i] + 1); for (int j = 1; j <= c; ++j) { if (map[i][j] == 'm') // 记录小人 nodem[++cntm].x = i, nodem[cntm].y = j; else if (map[i][j] == 'H') // 记录房子 nodeh[++cnth].x = i, nodeh[cnth].y = j; } } // cout << cntm << " " << cnth << endl; // 这个一开始多了1 for (int i = 1; i <= cntm; ++i) // 小人与房子之间建立一条容量为1费用为最短移动距离的边 { for (int j = 1; j <= cnth; ++j) { cost = abs(nodem[i].x - nodeh[j].x) + abs(nodem[i].y - nodeh[j].y); addedge(i, cntm + j, cap, cost); addedge(cntm + j, i, 0, -cost); } } s = 0, n = cntm + cnth + 1, t = cnth + cntm + 1; for (int i = 1; i <= cntm; ++i) // 源点与小人之间建边，容量为1，费用为0 { addedge(s, i, cap, 0); addedge(i, s, 0, 0); } for (int i = 1; i <= cnth; ++i) // 房子与汇点之间建边，容量为1，费用为0 { addedge(cntm + i, t, cap, 0); addedge(t, cntm + i, 0, 0); } int mincost = 0; minCostMaxflow(s, t, mincost); // 求解最小费用最大流 cout << mincost << endl; } return 0; }好像还可以使用二分图匹配来做。The end.2018-07-31 星期二
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。现在，给定多组字符大小顺序的关系式，问能否通过这些关系式确定一个有序序列。如果能确定有序序列，输出最早能够确定顺序的关系式的数量以及该序列如果出现冲突，输出最早能够确定冲突的关系式的数量如果不能确定也不存在冲突，输出无法得到题解每来一个小于关系就进行一次拓扑排序 ，直到出现冲突（也就是出现了环）或者已经能确定顺序，当结果已经确定时，后面的小于关系也就没有必要处理了 因此可以用一个flag标记结果是否已经确定。注意判拓扑序列不唯一时应放在输入完毕后，以及不能确定的条件。具体实现看代码。参考了ddwust的题解。代码StatusAcceptedTime1msMemory128kBLength1779#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn = 30; int indegree[maxn], _indegree[maxn]; int n, m; vector <int> E[maxn]; char ans[maxn]; queue <int> Q; void init() { for (int i = 0; i < n; ++i) { E[i].clear(); indegree[i] = 0; } } int Topsort() { int size = 0, ret = 1; memcpy(_indegree, indegree, sizeof(_indegree)); for (int i = 0; i < n; ++i) { if (_indegree[i] == 0) Q.push(i); } while (!Q.empty()) { if (Q.size() > 1) // 当前状态下有多个入度为0的节点，选择的顺序不能确定 ret = 0; int u = Q.front(); Q.pop(); ans[size++] = char(u + 'A'); for (int i = 0; i < E[u].size(); ++i) { int v = E[u][i]; if ((--_indegree[v]) == 0) Q.push(v); } } if (size < n) // 出现环 return -1; // for (int i = 0; i < n; ++i) // 判断环，同上 // if (_indegree[i] != 0) // return -1; ans[size] = '\0'; // 不加会报错 return ret; } int main() { char s[10]; int u, v; while (scanf("%d%d", &n, &m) != EOF && n && m) { init(); int flag = 0; for (int i = 0; i < m; ++i) { scanf("%s", s); if (flag) // 如果已经判断完成只需继续输入即可 continue; u = s[0] - 'A', v = s[2] - 'A'; E[u].push_back(v); indegree[v]++; flag = Topsort(); if (flag == 1) printf("Sorted sequence determined after %d relations: %s.\n", i + 1, ans); else if (flag == -1) printf("Inconsistency found after %d relations.\n", i + 1); } if (!flag) printf("Sorted sequence cannot be determined.\n"); } return 0; }注意C语言的字符数组，直接输出的话得加结束标记\0。The end.2018-07-20 星期五模板#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; const int maxn = 1010; int vis[maxn]; vector <int> E[maxn]; vector <int> V; int n, m; bool dfs(int u) { vis[u] = -1; // 当前 for (int i = 0; i < E[u].size(); ++i) { int v = E[u][i]; if (vis[v] == -1) // 出现环 return false; else if (!vis[v]) dfs(v); } V.push_back(u); vis[u] = 1; return true; } bool TopSort() { for (int i = 1; i <= n; ++i) if (!vis[i]) { if (!dfs(i)) return false; } return true; } int main() { scanf("%d%d", &n, &m); int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); E[u].push_back(v); } if (TopSort()) { for (int i = V.size() - 1; i >= 0; --i) printf("%d ", V[i]); } else printf("No\n"); } /* /Users/taifu/Codes/CPP/cmake-build-debug/CPP 13 15 1 2 1 6 1 7 3 1 3 4 4 6 6 5 7 4 7 10 8 7 9 8 10 11 10 12 10 13 12 13 9 8 3 1 7 10 12 13 11 4 6 5 2 Process finished with exit code 0 */
POJ3177 Redundant Paths（Tarjan求有重边双连通分量缩点）
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 fields is, in fact, connected by two routes. It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.SourceUSACO 2006 January Gold链接http://poj.org/problem?id=3177题意与POJ3352 Road Construction（Tarjan 求双连通分量缩点）一样，n 个节点 m 条边的无向图，问至少需要添加多少条边使这个图变成边双连通的。但是本题的数据有重边！！！所以需要特别处理一下。题解使用 Tarjan 求双连通分量，然后将同一个双连通分量缩点构成成一棵树，统计树上度为 1 的节点的数量 cnt，需要添加边的数量就是 (cnt+1)/2。两个点之间如果存在有重边，也算是双连通的。需要一个标记flag， 假如这个点到父亲的路有两条，那么第一条可以不走，但是第二条必须要走，因为是重边，这样儿子节点也就可以更新 low 了。代码StatusAcceptedMemory312kBLength4287#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <stack> using namespace std; const int maxn = 5010; int n, m, tot, cnt, cccnt; int dfn[maxn], low[maxn], head[maxn], ccno[maxn], ccnum[maxn], degree[maxn]; bool vis[maxn]; struct Edge { int to, next; }edge[20010]; stack <int> S; void addedge(int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void init() { for (int i = 0; i <= n; ++i) { dfn[i] = low[i] = ccno[i] = ccnum[i] = degree[i] = 0; head[i] = -1; vis[i] = false; } memset(edge, 0, sizeof(edge)); tot = cccnt = 0; cnt = 1; } void tarjan(int u, int father) // 求双连通分量 { low[u] = dfn[u] = ++tot; S.push(u); vis[u] = true; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == father && flag) // 重边处理，与求桥类似 { flag = false; continue; } if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) // 栈中保存的是同一个连通分量 { cccnt++; while (1) { int v = S.top(); S.pop(); // printf("%d %d\n", cccnt, v); vis[v] = false; ccno[v] = cccnt; ccnum[cccnt]++; if (v == u) break; } } } int main() { scanf("%d%d", &n, &m); init(); int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } tarjan(1, 0); for (int i = 1; i <= n; ++i) // 缩点成树求节点的度 { for (int j = head[i]; j != -1; j = edge[j].next) { int v = edge[j].to; if (ccno[i] != ccno[v]) degree[ccno[i]]++; } } int ans = 0; for (int i = 1; i <= cccnt; ++i) { if (degree[i] == 1) // 找到度为1的节点 ans++; } printf("%d\n", (ans+1) / 2); // 至少需要添加的边数 return 0; }推荐pku 3177 (3352) Redundant PathsPOJ 3177 Redundant Paths（重边标记法，有重边的边双连通分支）poj 3177 Redundant Paths(边双连通分量+缩点)数据来源于：传送门。Input for test 1 7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7 Output for test 1 2 Input for test 2 7 7 1 2 2 3 3 4 2 5 4 5 3 6 5 7 Output for test 2 2 Input for test 3 6 5 3 1 3 2 3 4 3 5 3 6 Output for test 3 3 Input for test 4 10 12 1 2 2 3 3 1 3 4 4 8 4 5 5 6 6 7 7 5 8 9 9 10 10 8 Output for test 4 2 Input for test 5 10 10 1 8 6 3 7 1 3 5 5 2 2 9 9 7 8 4 4 10 10 6 Output for test 5 0 Input for test 6 10 9 1 2 7 4 9 6 10 6 8 4 3 5 3 4 3 6 1 3 Output for test 6 3 Input for test 7 16 22 1 3 7 1 5 1 12 7 6 3 4 7 8 3 10 7 14 6 11 5 9 7 15 4 2 6 13 12 8 2 2 11 6 1 4 11 1 14 3 10 13 16 13 16 Output for test 7 2 Input for test 8 27 35 1 3 10 3 22 3 15 3 11 15 5 15 12 22 18 10 23 11 7 1 2 15 25 1 14 10 24 11 8 2 19 22 4 12 16 4 13 18 9 14 21 13 6 4 17 23 20 17 17 6 3 21 20 3 9 13 17 12 20 18 2 26 26 27 27 8 2 27 26 8 Output for test 8 4 Input for test 9 75 81 1 3 58 3 37 1 36 58 15 36 9 58 10 37 8 1 44 10 33 44 61 8 54 9 4 3 20 44 53 37 26 20 67 54 71 20 5 3 70 54 45 67 14 54 74 67 41 53 52 37 63 53 31 20 55 63 60 55 40 5 75 58 62 31 68 52 72 36 49 9 66 31 43 41 22 52 35 8 21 45 30 15 11 61 7 68 57 30 12 40 27 71 25 40 46 66 42 61 24 37 29 4 59 11 16 74 47 5 69 74 64 59 56 75 19 9 48 56 23 9 13 72 2 43 32 1 73 13 28 7 6 45 18 4 38 42 50 72 17 53 39 50 51 63 34 25 65 64 67 41 58 5 5 27 75 63 7 50 20 18 38 65 Output for test 9 16 Input for test 10 200 250 1 3 106 1 134 1 157 134 23 106 60 134 44 60 117 1 126 1 11 134 139 44 178 3 97 60 101 157 118 44 30 23 128 30 174 3 108 23 110 128 132 157 92 106 173 132 79 106 82 178 7 44 52 79 74 30 4 23 49 7 164 139 127 30 156 4 65 7 120 101 46 97 112 178 8 46 59 60 198 174 100 134 90 92 192 60 125 100 26 178 19 192 63 125 155 126 70 100 35 63 151 126 165 157 146 70 84 157 141 52 160 70 163 8 38 127 171 139 62 101 133 11 177 146 158 125 41 165 145 52 98 30 5 177 68 164 168 173 107 178 86 132 199 127 136 168 71 155 50 128 189 35 193 46 105 70 195 189 89 158 69 177 190 50 28 19 21 92 93 71 170 86 122 21 131 136 197 158 16 108 33 195 18 164 196 141 94 92 61 79 149 26 169 193 124 163 78 189 147 108 150 49 129 70 77 168 194 18 54 100 140 127 24 196 109 158 2 97 17 195 64 28 115 174 185 41 81 141 45 62 180 18 167 109 27 65 123 140 188 77 91 129 73 110 76 173 14 149 103 105 51 11 57 84 58 101 148 193 43 156 162 109 22 61 179 52 67 74 200 117 6 167 119 192 113 41 184 16 32 98 39 160 75 32 175 98 121 78 183 26 47 174 102 79 83 23 172 127 176 74 138 121 182 90 29 156 153 183 114 162 152 47 15 136 12 64 143 155 161 89 99 90 87 114 25 193 144 86 137 64 135 52 56 14 55 112 20 71 142 5 34 126 116 56 40 79 130 89 187 49 85 62 111 136 191 39 166 16 159 120 13 50 95 55 154 33 96 171 181 115 88 21 80 24 48 14 72 21 31 67 9 31 66 143 37 117 104 56 36 86 42 125 186 33 10 184 53 18 164 64 136 63 77 25 128 105 133 147 130 1 67 161 10 132 190 173 195 80 123 1 70 82 126 38 163 7 193 17 152 105 44 24 168 185 174 163 177 40 79 173 70 19 26 60 198 130 97 22 143 67 97 25 119 89 194 163 188 180 49 173 109 71 4 124 58 79 151 178 74 93 34 96 161 65 167 16 172 114 183 14 46 116 199 187 118 175 109 23 101 115 160 114 110 173 96 28 77 182 27 116 Output for test 10 32 Input for test 11 14 16 1 2 1 12 12 2 3 2 4 3 4 5 4 6 6 14 7 14 7 6 7 8 7 9 10 9 11 10 11 13 13 10 Output for test 11 2模板最后附上邝斌大大的板子。#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include using namespace std; const int MAXN = 5010;//点数 const int MAXM = 20010;//边数，因为是无向图，所以这个值要*2 struct Edge { int to,next; bool cut;//是否是桥标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block int Index,top; int block;//边双连通块数 bool Instack[MAXN]; int bridge;//桥的数目 void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !DFN[v] ) { Tarjan(v,u); if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } } else if( Instack[v] && Low[u] > DFN[v] ) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = block; } while( v!=u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } int du[MAXN];//缩点后形成树，每个点的度数 void solve(int n) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = 0; Tarjan(1,0); int ans = 0; memset(du,0,sizeof(du)); for(int i = 1;i <= n;i++) for(int j = head[i];j != -1;j = edge[j].next) if(edge[j].cut) du[Belong[i]]++; for(int i = 1;i <= block;i++) if(du[i]==1) ans++; //找叶子结点的个数ans,构造边双连通图需要加边(ans+1)/2 printf("%d\n",(ans+1)/2); } int main() { int n,m; int u,v; while(scanf("%d%d",&n,&m)==2) { init(); while(m--) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } solve(n); } return 0; }The end.2018-07-18 星期三
POJ3352 Road Construction（Tarjan求双连通分量缩点）
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. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.OutputOne line, consisting of an integer, which gives the minimum number of roads that we need to add.Sample InputSample Input 1 10 12 1 2 1 3 1 4 2 5 2 6 5 6 3 7 3 8 7 8 4 9 4 10 9 10 Sample Input 2 3 3 1 2 2 3 1 3Sample OutputOutput for Sample Input 1 2 Output for Sample Input 2 0SourceCCC 2007链接http://poj.org/problem?id=3352题意n个节点m条边的无向图，问至少需要添加多少条边使这个图变成边双连通的。题解使用Tarjan求双连通分量，然后将同一个双连通分量缩点构成成一棵树，统计树上度为1的节点的数量cnt，需要添加边的数量就是(cnt+1)/2。貌似这题的数据是没有重边的。具体可参考BYVoid大佬的题解：题目大意是，给定一个连通图，要求添加一些边，使每两个顶点之间都有至少两条不相交的路径，求最小需要添加的边数。很显然，题中要求的图就是一个边双连通图，即边连通度不小于2。我的方法是在原图中DFS求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。有人说至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以结果就是(leaf+1)/2。这个结论我不能证明，但是可以想象出是对的。简单说明一下，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。这道题跟pku3352一模一样，拿这个程序交两个题一个字不用改都能AC！但实际上两个题也稍有不同，这个题有一点很不容易被注意到，就是可能存在重边，两个点之间如果存在有重边，也算是双连通的。我的处理方法是在DFS时标记每条边及其反向边是否被访问过，而不是判断顶点。代码StatusAcceptedTime47msMemory376kBLength4295#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <stack> using namespace std; const int maxn = 5010; int n, m, tot, cnt, cccnt; int dfn[maxn], low[maxn], head[maxn], ccno[maxn], ccnum[maxn], degree[maxn]; bool vis[maxn]; struct Edge { int to, next; }edge[20010]; stack <int> S; void addedge(int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void init() { for (int i = 0; i <= n; ++i) { dfn[i] = low[i] = ccno[i] = ccnum[i] = degree[i] = 0; head[i] = -1; vis[i] = false; } memset(edge, 0, sizeof(edge)); tot = cccnt = 0; cnt = 1; } void tarjan(int u, int father) // 求双连通分量 { low[u] = dfn[u] = ++tot; S.push(u); vis[u] = true; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == father && flag) // 重边处理 { flag = false; continue; } if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) // 栈中保存的是同一个连通分量 { cccnt++; while (1) { int v = S.top(); S.pop(); // printf("%d %d\n", cccnt, v); vis[v] = false; ccno[v] = cccnt; ccnum[cccnt]++; if (v == u) break; } } } int main() { scanf("%d%d", &n, &m); init(); int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } tarjan(1, 0); for (int i = 1; i <= n; ++i) // 缩点成树求节点的度 { for (int j = head[i]; j != -1; j = edge[j].next) { int v = edge[j].to; if (ccno[i] != ccno[v]) degree[ccno[i]]++; } } int ans = 0; for (int i = 1; i <= cccnt; ++i) { if (degree[i] == 1) // 找到度为1的节点 ans++; } printf("%d\n", (ans+1) / 2); // 至少需要添加的边数 return 0; }推荐阅读lin375691011 | POJ 3352 Road Construction用Tarjan算法求双连通分量的时候，并不是low数组中值不同的就不再同一个双联通分量。很多大牛的博客都只借助low数组中的值来判断是否是同一个双联通分量。的确low数组中值相同的一定是双连通，但通过Tarjan处理过的low不同也有可能是双连通。我们开始学习Tarjan算法时有一个手写栈，每一次弹栈的时候弹出来的点是一个双联通分量才对。小優YoU | POJ3352-Road Construction若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2The end.2018-07-18 星期三