A - TT 的魔法猫

题意：

众所周知，TT 有一只魔法猫。

这一天，TT 正在专心致志地玩《猫和老鼠》游戏，然而比赛还没开始，聪明的魔法猫便告诉了 TT 比赛的最终结果。TT 非常诧异，不仅诧异于他的小猫咪居然会说话，更诧异于这可爱的小不点为何有如此魔力？

魔法猫告诉 TT，它其实拥有一张游戏胜负表，上面有 N 个人以及 M 个胜负关系，每个胜负关系为 A B，表示 A 能胜过 B，且胜负关系具有传递性。即 A 胜过 B，B 胜过 C，则 A 也能胜过 C。

TT 不相信他的小猫咪什么比赛都能预测，因此他想知道有多少对选手的胜负无法预先得知，你能帮帮他吗？

Input

第一行给出数据组数。

每组数据第一行给出 N 和 M（N , M <= 500）。

接下来 M 行，每行给出 A B，表示 A 可以胜过 B。

Output

对于每一组数据，判断有多少场比赛的胜负不能预先得知。注意 (a, b) 与 (b, a) 等价，即每一个二元组只被计算一次。

Sample Input

33 31 21 32 33 21 22 34 21 23 4

Sample Output

004

思路做法：

这是经过变化后的多源最短路算法问题，将原问题转化为图的问题，即为若A胜过B，则A到B有一条边，由于点数不多，可以用邻接矩阵存储。根据规则，把多源最短路算法中的更新改变为TT[i][j] = TT[i][j] | TT[i][k]&TT[k][j]并且为了降低复杂度，需要剪枝避免不必要的计算，即先判断TT[i][k]是否为true，若否则一定不能更新，直接跳过。最后便历矩阵，若TT[i][j]和TT[j][i]都为false则胜负未知否则若其中一个为true则胜负已分，不可能出现2个都是true的情况，同时将矩阵清零以进行下一轮。

总结:

正常情况下不可能直接给出原始问题来求解，大多是多源最短路算法的变体。

代码:

#include <stdio.h>const int N = 500+5;bool TT[N][N];int main(){int t; scanf("%d", &t);while(t--){int n, m, ans = 0; scanf("%d %d", &n, &m);for(int i = 0; i < m; ++i){int a, b; scanf("%d %d", &a, &b);TT[a][b] = 1;}for(int k = 1; k <= n; ++k){for(int i = 1; i <= n; ++i){if(TT[i][k]){for(int j = 1; j <= n; ++j){TT[i][j] = TT[i][j] | TT[i][k]&TT[k][j];}}}}for(int i = 1; i <= n; ++i){for(int j = i+1; j <= n; ++j){if(!TT[i][j]&&!TT[j][i]) ans++; TT[i][j] = 0; TT[j][i] = 0;}}printf("%d\n", ans);}return 0;}

B - TT 的旅行日记

题意：

众所周知，TT 有一只魔法猫。

今天他在 B 站上开启了一次旅行直播，记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发，准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种，它们的速度与价钱都不同。当然啦，商业线要比经济线贵，TT 平常只能坐经济线，但是今天 TT 的魔法猫变出了一张商业线车票，可以坐一站商业线。假设 TT 换乘的时间忽略不计，请你帮 TT 找到一条去喵星机场最快的线路，不然就要误机了！

Input

输入包含多组数据。每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即猫猫快线中的车站总数，起点和终点（即喵星机场所在站）编号。

下一行包含一个整数 M (1 ≤ M ≤ 1000)，即经济线的路段条数。

接下来有 M 行，每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返，其中单程需要 Z 分钟。

下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。

接下来 K 行是商业线路段的描述，格式同经济线。

所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。

Output

对于每组数据，输出3行。第一行按访问顺序给出 TT 经过的各个车站（包括起点和终点），第二行是 TT 换乘商业线的车站编号（如果没有使用商业线车票，输出"Ticket Not Used"，不含引号），第三行是 TT 前往喵星机场花费的总时间。

本题不忽略多余的空格和制表符，且每一组答案间要输出一个换行

Sample Input

4 1 441 2 21 3 32 4 43 4 512 4 3

Sample Output

1 2 425

思路做法：

单源最短路算法的变体问题，不能直接使用原算法。除带有动态规划的思想算法求解外，较容易理解的是针对每条商业线（i，j）便历，分别计算（s，i）+（i，j）+（j，e）的值并最小化，最后与不走商业线的方案取最小值（不一定用到商业线的就是最小的）。因此具体做法为从s开始运行一遍最短路算法，再从e开始运行一遍最短路算法，然后便历每一条商业线，为求最小值不断更新记录的相关参数，最后与dis1[e]（不走商业线的结果）比较，并递归输出路径上的结点。

总结:

运用逐个便历商业线的思想写起代码还是不难的，还有值得注意的一点是题目中要求的输出格式，最后不能有多与的空格，这里用变量t记录次数实现。

代码:

#include <stdio.h>#include <vector>#include <queue>using namespace std;const int N = 500+5;const int M = 1000+5;const int K = 1000+5;const int INF = 0x3f3f3f3f;struct Edge{int v, w;Edge(){}Edge(int _v, int _w):v(_v), w(_w){}};vector<Edge> E[N];struct Point{int p, d;Point(){}Point(int _p, int _d):p(_p), d(_d){}bool operator<(const Point& P) const {return d < P.d;}};int pre1[N], pre2[N], vis[N], dis1[N], dis2[N];priority_queue<Point> q;void addEdge(int u, int v, int w){E[u].push_back(Edge(v, w));E[v].push_back(Edge(u, w));}void dijkstra(int s, int e, int n, int *dis, int *pre){while(!q.empty()) q.pop();for(int i = 1; i <= n; ++i){pre[i] = 0; vis[i] = 0;dis[i] = INF;}dis[s] = 0; q.push(Point(s, 0));while(!q.empty()){int u = q.top().p; q.pop();if(vis[u]){if(u == e) return;continue;}vis[u] = 1;for(int i = 0, len = E[u].size(); i < len; ++i){int v = E[u][i].v, w = E[u][i].w;if(vis[v]) continue;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w; pre[v] = u;q.push(Point(v, -dis[v]));}}}}void output1(int s, int e, int *pre){if(e == s) return;output1(s, pre[e], pre);printf(" %d", e);}void output2(int s, int e, int *pre){if(e == s) return;printf(" %d", pre[s]);output2(pre[s], e, pre);}int main(){int n, s, e, t = 0;while(~scanf("%d%d%d", &n, &s, &e)){for(int i = 1; i <= n; ++i)while(!E[i].empty()) E[i].pop_back();int x, y, z;int m; scanf("%d", &m); //经济线 for(int i = 0; i < m; ++i){scanf("%d%d%d", &x, &y, &z);addEdge(x, y, z);}dijkstra(s, e, n, dis1, pre1); dijkstra(e, s, n, dis2, pre2);int cost = dis1[e], temp = cost, u = 0, v = 0;int k; scanf("%d", &k); //商业线for(int i = 0; i < k; ++i){scanf("%d%d%d", &x, &y, &z);int cost1 = dis1[x] + dis2[y] + z;int cost2 = dis1[y] + dis2[x] + z;if(cost1 < cost2 && cost1 < cost){cost = cost1; u = x; v = y;}else if(cost2 < cost1 && cost2 < cost){cost = cost2; u = y; v = x;}}if(t) printf("\n");if(temp > cost){printf("%d", s); output1(s, u, pre1);printf(" %d", v); output2(v, e, pre2);printf("\n%d\n%d\n", u, cost);}else{printf("%d", s); output1(s, e, pre1);printf("\nTicket Not Used\n%d\n", dis1[e]);}t++;}return 0;}

C - TT 的美梦

题意：

这一晚，TT 做了个美梦！

在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。

喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。

具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。

TT 打算测试一下这项政策是否合理，因此他想知道从首都出发，走到其他城市至少要交多少的税，如果总金额小于 3 或者无法到达请悄咪咪地打出 ‘?’。

Input

第一行输入 T，表明共有 T 组数据。（1 <= T <= 50）

对于每一组数据，第一行输入 N，表示点的个数。（1 <= N <= 200）

第二行输入 N 个整数，表示 1 ～ N 点的权值 a[i]。（0 <= a[i] <= 20）

第三行输入 M，表示有向道路的条数。（0 <= M <= 100000）

接下来 M 行，每行有两个整数 A B，表示存在一条 A 到 B 的有向道路。

接下来给出一个整数 Q，表示询问个数。（0 <= Q <= 100000）

每一次询问给出一个 P，表示求 1 号点到 P 号点的最少税费。

Output

每个询问输出一行，如果不可达或税费小于 3 则输出 ‘?’。

Sample Input

256 7 8 9 1061 22 33 41 55 44 5245101 2 4 4 5 6 7 8 9 10101 22 33 11 44 55 66 77 88 99 1023 10

Sample Output

Case 1:34Case 2:??

思路做法：

因为税费可能为负数，且图中可能出现负环，因此用SPFA更容易检测出来，图创建好后，从结点1开始运行SPFA，若遇到负环，需要把负环上的点能到达的点也全部标记，表示税费为负，另外，用初始化的dis（初始为一个很大的值）来判断某点是否可达，最后根据税费为负的标记、是否可达和税费是否超过3输出答案。

总结:

SPFA不限制边必须为正，可以用于判断负环。

代码:

#include <stdio.h>#include <queue>#include <vector>#include <cmath>using namespace std;#define INF 0x3f3f3f3fconst int N = 200+5;struct Edge{int u, v, w;Edge(){}Edge(int _u, int _v, int _w):u(_u), v(_v), w(_w){}};vector<Edge> E[N];int a[N], dis[N], cnt[N], pre[N];bool inq[N], isNeg[N];queue<int> q, neg;void addEdge(int u, int v, int w){E[u].push_back(Edge(u, v, w)); //有向 }void negRing(int s){if(isNeg[s]) return;isNeg[s] = 1; neg.push(s);while(!neg.empty()){int u = neg.front(); neg.pop();for(int i = 0, len = E[u].size(); i < len; ++i){Edge e = E[u][i]; int v = e.v;if(isNeg[v]) continue;isNeg[v] = 1; neg.push(v);}}}void SPFA(int s, int n){for(int i = 1; i <= n; ++i){dis[i] = INF; inq[i] = 0; pre[i] = 0;cnt[i] = 0; isNeg[i] = 0;}dis[s] = 0; inq[s] = 1; q.push(s);while(!q.empty()){int u = q.front(); q.pop(); inq[u] = 0;for(int i = 0, len = E[u].size(); i < len; ++i){Edge e = E[u][i]; int v = e.v;if(dis[v] > dis[u] + e.w){cnt[v] = cnt[u] + 1;if(cnt[v] >= n){negRing(v); continue; //打上标记}dis[v] = dis[u] + e.w;pre[v] = u;if(!inq[v]){q.push(v); inq[v] = 1;}}}}}int main(){int t; scanf("%d", &t);for(int k = 1; k <= t; ++k){for(int i = 0; i < N; ++i)while(!E[i].empty()) E[i].pop_back();int n; scanf("%d", &n);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);int m; scanf("%d", &m);for(int i = 0; i < m; ++i){int A, B; scanf("%d %d", &A, &B);addEdge(A, B, pow(a[B]-a[A], 3));}SPFA(1, n);int q; scanf("%d", &q);printf("Case %d:\n", k);for(int i = 1; i <= q; ++i){int p; scanf("%d", &p);if(isNeg[p] || !isNeg[p]&&dis[p]<3 || !pre[p]) printf("?\n");else printf("%d\n", dis[p]);}}return 0;}