TT 的魔法猫
现有数据大小是N的数据，然后他们之间进行M场比赛，如果A胜过B，B胜过C，那么A胜过C，也就是说有传递性，在本题中，这种性质可以预测，先从这些数据中预测有多少对两个人之间的比赛结果不能预测。
输入
第一行给出数据组数。
每组数据第一行给出 N 和 M（N , M <= 500）。
接下来 M 行，每行给出 A B，表示 A 可以胜过 B。
3
3 3
1 2
1 3
2 3
3 2
1 2
2 3
4 2
1 2
3 4
输出
对于每一组数据，判断有多少场比赛的胜负不能预先得知。注意 (a, b) 与 (b, a) 等价，即每一个二元组只被计算一次。
0
0
4
思路
比赛考察每两个人之间比赛的传递，所以这道题要求每两对人之间的比赛都要进行比较来知道他们之间的传递性，枚举这么多的数据，也就是需要三重循环，内层的两重循环是代表一场比赛，最外层的循环，是在枚举这场比赛能不能由别的比赛枚举出来。
总结
思路中说的三重循环，其实本质就是佛洛依德算法
代码
#include<iostream>
using namespace std;
bool dis[510][510];
int a, b;//一个是用来初始化点的个数，一个是边
void init() {
for (int i = 1; i <= a; i++)
for (int j = 1; j <= a; j++)
dis[i][j] = false;
}
void floyd() {
for (int k = 1; k <= a; k++)
for (int i = 1; i <= a; i++)
{
if (dis[i][k] == false)
continue;
else
for (int j = 1; j <= a; j++)
dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
}
for (int i = 1; i <= a; i++)
for (int j = 1; j <= a; j++)
if (dis[i][j] == true)
dis[j][i] = true;
}
int main() {
int n;
cin >> n;
int c, d;
for (int i = 0; i < n; i++) {
cin >> a >> b;
init();
for (int j = 0; j < b; j++)
{
scanf_s("%d %d", &c, &d);
dis[c][d] = true;
}
floyd();
int sum = 0;
for (int j = 1; j <= a; j++)
for (int k = 1; k <= a; k++)
if (k > j&& dis[j][k] == false)
sum++;
printf("%d\n", sum);
}
}
TT 的旅行日记
现在有多组数据，N个点，M条经济线路，K条经济线路，每条线路都有自己的价值，现要求计算出从起点S到终点E的最少价值。
输入
输入包含多组数据。每组数据第一行为 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 行是商业线路段的描述，格式同经济线。
所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
输出
对于每组数据，输出3行。第一行按访问顺序给出 TT 经过的各个车站（包括起点和终点），第二行是 TT 换乘商业线的车站编号（如果没有使用商业线车票，输出"Ticket Not Used"，不含引号），第三行是 TT 前往喵星机场花费的总时间。
本题不忽略多余的空格和制表符，且每一组答案间要输出一个换行
1 2 4
2
5
思路
本想用同一个链式前向星记录全部的线路，结果发现，经济线和商业线可以连接同样的两点，所以我把他们分开，用两个链式前向星来存储，先用dijkstra算出从起点开始的最短路，再计算从终点开始的最短路，再枚举每一条商业线，用商业线两端的店到起点和终点的距离加上商业线的距离，找出经过商业线最短的路径，最后再和不经过商业线的距离相比较，最短者就是答案。由于存储的是前驱，所以在输出答案的时候，要使用一个栈来把他反转过来。
总结
这道题主要考察dijsktra算法的使用
代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<utility>
#include<stack>
#define Max 4000
#define inf 99999
#include<string.h>
using namespace std;
priority_queue<pair<int, int> > q;
struct edge {
int to, w, nex;
}e[Max], d[Max];
bool vis[Max];
int ehead[Max], dhead[Max], etot, dtot, dis[Max], dis2[Max];//dis是用来记录从起点开始，ddis2记录从终点开始
int epre[Max], dpre[Max];//pre是从起点开始的pre2是从终点开始的
void add(int u, int v, int w, bool choose) {//choose是1的时候是经济线，0是商业线
if (choose) {
e[++etot].to = v, e[etot].nex = ehead[u];
e[etot].w = w, ehead[u] = etot;
}
else {
d[++dtot].to = v, d[dtot].nex = dhead[u];
d[dtot].w = w, dhead[u] = dtot;
}
}
void dijskstra(int s, bool noww) {//从s点开始搜索
while (!q.empty()) q.pop();
memset(vis, 0, sizeof vis);
int* now;
int* pre;
if (noww) { //这是第一次
for (int i = 1; i <= 1000; i++) dis[i] = inf;
now = dis;
pre = epre;
}
else {
for (int i = 1; i <= 1000; i++) dis2[i] = inf;
now = dis2;
pre = dpre;
}
now[s] = 0;
q.push(make_pair(0, s));
while (q.size()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = ehead[x]; i; i = e[i].nex) {
int y = e[i].to, w = e[i].w;
if (now[y] > now[x] + w) {
now[y] = now[x] + w;
pre[y] = x;
q.push(make_pair(-now[y], y));
}
}
}
}
int main() {
int N, S, E;
int pu=false;
while (cin>>N)
{
if(pu)
printf("\n");
pu=true;
etot = 0;
dtot = 0;
for (int i = 0; i < 1500; i++) ehead[i] = 0;
for (int i = 0; i < 1500; i++) dhead[i] = 0;
for (int i = 0; i < 1500; i++) epre[i] = 0;
for (int i = 0; i < 1500; i++) dpre[i] = 0;
scanf("%d %d", &S, &E);
int M;
scanf("%d", &M);
for (int i = 0; i < M; i++) {
int X, Y, Z;
scanf("%d %d %d", &X, &Y, &Z);
add(X, Y, Z, 1);
add(Y, X, Z, 1);
}
int K;
scanf("%d", &K);
for (int i = 0; i < K; i++) {
int X, Y, Z;
scanf("%d %d %d", &X, &Y, &Z);
add(X, Y, Z, 0);
add(Y, X, Z, 0);
}
dijskstra(S, 1);
dijskstra(E, 0);
int x = 0, y = 0, min = 99999;//前两个参数用来记录最短路所经过的商业线
for (int i = 1; i <= N; i++) {
int now;
int th;
if (dhead[i] != 0) {
now = dhead[i];
while (now != 0) {
th = d[now].to;
if ((dis[i] + d[now].w + dis2[th]) < min) {
min = dis[i] + d[now].w + dis2[th];
x = i;
y = th;
}
now = d[now].nex;
}
}
}
if (dis[E] < min) {//这是不经过商业线还是最短路径的情况
stack<int> sim;
int u = E;
while (u != 0) {
sim.push(u);
u = epre[u];
}
printf("%d", sim.top());
sim.pop();
while (sim.size())
{
printf(" %d", sim.top());
sim.pop();
}
printf("\n");
printf("Ticket Not Used\n");
printf("%d", dis[E]);
}
else {
stack<int> sim;
int u = x;
while (u != 0) {
sim.push(u);
u = epre[u];
}
while (sim.size()) {
printf("%d ", sim.top());
sim.pop();
}
printf("%d", y);
y = dpre[y];
while (y != 0) {
printf(" %d", y);
y = dpre[y];
}
printf("\n");
printf("%d\n", x);
printf("%d", min);
}
printf("\n");
}
}
TT 的美梦
情景：
这一晚，TT 做了个美梦！
在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。
喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。
具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。
TT 打算测试一下这项政策是否合理，因此他想知道从首都出发，走到其他城市至少要交多少的税，如果总金额小于 3 或者无法到达请悄咪咪地打出 '?'。
简短题意：
现有N个城市，每两个城市之间都有价值，先要求计算从点1到题目输入的指定点P之间的最小价值。如果这条线路上有负环或者是到不了那个点，就输出？。
输入
第一行输入 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 号点的最少税费。
2
5
6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
10
1 2 4 4 5 6 7 8 9 10
10
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 8
8 9
9 10
2
3 10
输出
每个询问输出一行，如果不可达或税费小于 3 则输出 '?'。
Case 1:
3
4
Case 2:
?
?
思路
这道题的题目中已经说了这些线路之间的价值可能会有负值，那么这样的话，dijsktra是不能解决的，那就要使用belman算法，但是这个太暴力了，复杂度接近O()，那就要使用复杂度更低的SPFA，计算从起点开始到每个点的最小距离，如果到某个点是负环的话，就使用dfs，遍历这个点能到达的所有点，这些点因为负环的作用没有最短路，记录下来，最后输出？。其他的点就用SPFA正常记录就行。
总结
这道题考察SPFA，同时还要注意线路中的负环。
代码
#include<cstdio>
#include<cmath>
#include<queue>
#include<string.h>
#define inf 999999
using namespace std;
struct edge {
int w, to, nex;
}e[110000];
int tot, head[300], a[300], vis[300], cnt[300], dis[300];//a是点的权值,vi是给dfs用的
void add(int u, int v, int w) {
e[++tot].to = v, e[tot].nex = head[u];
e[tot].w = w, head[u] = tot;
}
void dfs(int s) {//从s点开始dfs并标记所有点
if (vis[s] == 2)
return;
vis[s] = 2;
s = head[s];
while (s != 0) {
dfs(e[s].to);
s = e[s].nex;
}
}
void SPFA(int s,int n) {//从指定点开始
queue<int> q;
for (int i = 1; i <= 250; i++) {
vis[i] = 0;
cnt[i] = 0;
dis[i] = inf;
}
vis[s] = 1;
dis[s] = 0;
q.push(s);
while (!q.empty()) {
int a = q.front();
q.pop();
if (vis[a] == 2)
continue;
vis[a] = 0;
int b = head[a];
while (b != 0) {
if (dis[e[b].to] > dis[a] + e[b].w) {
dis[e[b].to] = dis[a] + e[b].w;
cnt[e[b].to] += 1;
if (cnt[e[b].to] >= n)
dfs(e[b].to);
if (vis[e[b].to] == 0) {
vis[e[b].to] = 1;
q.push(e[b].to);
}
}
b = e[b].nex;
}
}
}
int main() {
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++) {
int N;
scanf("%d", &N);//用来表示每组数据点的个数
for (int j = 1; j <= N; j++)
scanf("%d", &a[j]);
int M;
scanf("%d", &M);
tot = 0;
memset(head, 0, sizeof head);
for (int j = 0; j < M; j++) {
int A, B, w;
scanf("%d %d", &A, &B);
w = pow((a[B] - a[A]), 3);
add(A, B, w);
}
SPFA(1, N);
int Q;
scanf("%d", &Q);
printf("Case %d:\n", (i + 1));
for (int j = 0; j < Q; j++) {
int P;
scanf("%d", &P);
if (vis[P] == 2 || dis[P] < 3 || dis[P] == inf)
printf("?\n");
else
printf("%d\n", dis[P]);
}
}
}
