图论 | SPFA | 20190623考试：解题报告
Problem.#1：虫洞(wormhole.cpp/c/pas)
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1..N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），也就是说，John可以从任何一块地开始，但是最终要通过虫洞回到这块地，且时间要处在开始之前，请你告诉John他能办到吗。
John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
Input
Line 1: 一个整数 F, 表示农场个数。
Line 1 of each farm: 三个整数 N, M, W。
Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。
Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。
Output
- Lines 1..F: 如果John能在这个农场实现他的目标，输出”YES”,否则输出”NO”。
Sample Input
1 | 2 |
Sample Output
1 | NO |
分析
图论基础题，理解一下题目大意，就是：给你一张含有 M 条无向边的和 W 条有向边的混合图，问你图中是否存在负环（因为通过虫洞回到原点时时间在开始之前，那么路上权值之和一定为负值）
判断负环用的是 SPFA 算法
Codes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
const ll INF=1e15;
int n,m,s,addcnt[maxn];
ll dist[maxn];
bool vis[maxn];
struct node{
vector<pr> linkto;
}e[maxn];
inline void init()
{
int x,y,z;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
if(x==y) continue;
e[x].linkto.push_back(make_pair(y,z));
e[y].linkto.push_back(make_pair(x,z));
}
for(int i=1;i<=s;i++){
scanf("%d%d%d",&x,&y,&z);
e[x].linkto.push_back(make_pair(y,-z));
}
}
bool spfa(int st,int mode)
{
vector<pr>::iterator iterid;
int head,next,val;
queue<int> wait;
memset(vis,false,sizeof(vis));
if(mode==1){ // 判断负环
for(int i=1;i<=n;i++){
dist[i]=0;
vis[i]=true;
wait.push(i);
}
}
else{
for(int i=1;i<=n;i++) dist[i]=INF;
dist[st]=0;
vis[st]=true;
wait.push(st);
}
while(!wait.empty()){
head=wait.front();
wait.pop();
vis[head]=false;
iterid=e[head].linkto.begin();
while(iterid!=e[head].linkto.end()){
next=iterid->first;
val=iterid->second;
if(dist[next]>dist[head]+val){
dist[next]=dist[head]+val;
if(!vis[next]){
vis[next]=true;
wait.push(next);
addcnt[next]++;
if(mode==1) if(addcnt[next]>=n-1) return true;
}
}
iterid++;
}
}
return false;
}
int main()
{
freopen("wormhole.in","r",stdin);
freopen("wormhole.out","w",stdout);
int T; scanf("%d",&T);
while(T--){
init();
if(spfa(0,1)) printf("YES\n");
else printf("NO\n");
for(int i=1;i<=n;i++) e[i].linkto.clear();
memset(addcnt,0,sizeof(addcnt));
}
return 0;
}
1 |
|
Problem.#2：数列问题
给定一个数列，从中找到3个无交集的连续子数列使其和最大。
Input
第一行一个数n，表示数列长度。
接下来有n行，每行一个数，第i行为第i个数。
Output
仅有一个数，表示最大和。
Sample Input
1 | 10 |
Sample Output
1 | 1 |
分析
考试时想到的是所有的正数和 + 如果正数不够 3 个就加上最大的负数，愉快的 WA 了大样例（因为两个区间的正数和他们之间的负数的整体和很有可能大于原来的任何一个正数区间和）
于是自然而然地想到了 DP，设 $f[i][j][k]$ 表示当前考虑到第 $i$ 个数，要形成 $j$ 组（$j\leq 3$）并且选不选这个数（$k=0$ 表示不选，反之则选），下面来讨论：
如果选这个数，那么要形成 $j$ 组，可以根第 $i-1$ 个数凑到一起，需要 $f[i-1][j][1]$ ，或者也可以另起一组那么第 $i-1$ 个数就无所谓了，需要 $f[i-1][j-1][0]$ 或 $f[i-1][j-1][1]$ 皆可
如果不选这个数，那么要形成 $j$ 组，显然第 $i-1$ 个数必须已经形成 $j$ 组才行，所以就是 $f[i-1][j][0]$ 和 $f[i-1][j][1]$
Codes
1 |
|
Problem.#3：Dueling GPS (gps.cpp)
Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the “Submit” button twice when selecting extra features for the car, and as a result the car ended up equipped with two GPS navigation systems! Even worse, the two systems often make conflicting decisions about the route that FJ should take. The map of the region in which FJ lives consists of N intersections (2 <= N <= 10,000) and M directional roads (1 <= M <= 50,000). Road i connects intersections A_i (1 <= A_i <= N) and B_i (1 <= B_i <= N). Multiple roads could connect the same pair of intersections, and a bi-directional road (one permitting two-way travel) is represented by two separate directional roads in opposite orientations. FJ’s house is located at intersection 1, and his farm is located at intersection N. It is possible to reach the farm from his house by traveling along a series of directional roads. Both GPS units are using the same underlying map as described above; however, they have different notions for the travel time along each road. Road i takes P_i units of time to traverse according to the first GPS unit, and Q_i units of time to traverse according to the second unit (each travel time is an integer in the range 1..100,000). FJ wants to travel from his house to the farm. However, each GPS unit complains loudly any time FJ follows a road (say, from intersection X to intersection Y) that the GPS unit believes not to be part of a shortest route from X to the farm (it is even possible that both GPS units can complain, if FJ takes a road that neither unit likes). Please help FJ determine the minimum possible number of total complaints he can receive if he chooses his route appropriately. If both GPS units complain when FJ follows a road, this counts as +2 towards the total.
John最近新买了辆车，但是他在为车订购GPS时，脑子进水点了两下”Submit”，导致新车装了两套GPS系统，更糟的是，两套GPS系统存储的路径信息不同，当John没有按照GPS的预定最短路径走的时候，GPS就会报警一次，如果John同时不在两套GPS的预定路径上行驶，他们甚至会同时报警，John现在把这个难题交给了你，他给了你一张有向图有 N 个结点和 M 条边，两套GPS存储的从 i 到 j 的路径长度分别用 A_i 和 B_i 表示，John希望你帮他设计一条从 1 到 N的路线，使得他能听到最少的GPS报警次数
Input
- Line 1: The integers N and M. Line i describes road i with four integers: A_i B_i P_i Q_i.
Output
- Line 1: The minimum total number of complaints FJ can receive if he routes himself from his house to the farm optimally.
Sample Input
1 | 5 7 |
Sample Output
1 | 1 |
分析
建三个图，分别存储 GPS1 的路径信息，GPS2的路径信息，以及报警次数
先对 1，2 图进行 SPFA ，记录下最短路经过的边，一开始把 3 图的边权全部改成 2，代表两个 GPS 都为报警，然后对于每个 GPS 认为的最短路径的边，在 3 图中边权减去 1 即可
需要注意的是，GPS 对于路径的选择是实时更新的，每次 GPS 都会选择当前点 k 到点 N 的最短路径而不是当前点 k 到点 1 的最短路径，因此 1，2 图要存逆图再 SPFA
最后在图3上 SPFA 求最短路就可以了
Codes
1 |
|
