A - Silver Cow Party（SSSP）

POJ - 3268

题目大意

有1~N一共N个结点，每个结点都有一头奶牛，

每只奶牛都打算到结点X（1<=X<=N）来参加派对，

并且在派对结束后回到原来的结点，

每只奶牛都选择最短的路程，

一共有M条单向的路，每条路通过的时间为Ti，（单向有权）

(1 ≤ N ≤ 1000)    (1 ≤ M ≤ 100,000)    (1 ≤ T_i ≤ 100)

问：来回的路程最长的奶牛经过的总路程为多少？

做法

单源最短路（SSSP）问题的变种，“回家”即为从X到各点的最短路，“前往派对”即为将所有道路取反后，从X到各个点的最短路 比较稀疏的图，用Dijkstra模板即可

AC-Code (C++)

Time: 47 ms  Memory: 1060 kb

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<string> #include<vector> #include<functional> using namespace std; const int maxn = 1005; const int maxm = 100005; const int inf = 1000000000; int N, M, X; //结点数，道路数，原点 struct Edge { int from, to, dist; Edge(int u, int v, int d) :from(u), to(v), dist(d){} }; vector<Edge> edges_1; //存储正边 vector<int> G_1[maxn]; vector<Edge> edges_2; //存储反边 vector<int> G_2[maxn]; bool done[maxn]; //是否已被访问 int d_1[maxn]; //到原点的距离 int d_2[maxn]; typedef pair<int, int> pii; int ans = -1; void AddEdge_1(int from, int to, int dist) { edges_1.push_back(Edge(from, to, dist)); int m = edges_1.size(); G_1[from].push_back(m - 1); } void AddEdge_2(int from, int to, int dist) { edges_2.push_back(Edge(from, to, dist)); int m = edges_2.size(); G_2[from].push_back(m - 1); } void dijkstra_1(void) //从原点到各点 { priority_queue<pii, vector<pii>, greater<pii> >Q; for (int i = 1; i <= N; i++) d_1[i] = inf; d_1[X] = 0; memset(done, 0, sizeof(done)); Q.push(pii(0, X)); while (!Q.empty()) { pii x = Q.top(); Q.pop(); int u = x.second; //u为当前结点的编号 if (done[u]) continue; done[u] = true; for (int i = 0; i < G_1[u].size(); i++) { Edge& e = edges_1[G_1[u][i]]; if (d_1[e.to]>d_1[u] + e.dist) { d_1[e.to] = d_1[u] + e.dist; Q.push(pii(d_1[e.to], e.to)); } } } } void dijkstra_2(void) //从各点到原点 { priority_queue<pii, vector<pii>, greater<pii> >Q; for (int i = 1; i <= N; i++) d_2[i] = inf; d_2[X] = 0; memset(done, 0, sizeof(done)); Q.push(pii(0, X)); while (!Q.empty()) { pii x = Q.top(); Q.pop(); int u = x.second; //u为当前结点的编号 if (done[u]) continue; done[u] = true; for (int i = 0; i < G_2[u].size(); i++) { Edge& e = edges_2[G_2[u][i]]; if (d_2[e.to]>d_2[u] + e.dist) { d_2[e.to] = d_2[u] + e.dist; Q.push(pii(d_2[e.to], e.to)); } } } } int main(void) { scanf("%d %d %d", &N, &M, &X); for (int i = 0; i < M; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); AddEdge_1(a, b, c); AddEdge_2(b, a, c); } dijkstra_1(); dijkstra_2(); for (int i = 1; i <= N; i++) { ans = max(ans, d_1[i] + d_2[i]); } printf("%d\n", ans); return 0; }

B - Wormholes（Bellman-Ford）

POJ - 3259

题目大意

农场主FJ有F个农场（F组数据）， 一个农场有N块地（结点），编号1~N， 地与地之间有M条双向正权边，W条单向负权边（虫洞）， FJ想从农场的某点出发，经过一些结点后回到原点时，时间早于出发的时刻， 问：FJ能否在该农场实现这个愿望？ (1 ≤ N ≤ 500)    (1 ≤ M ≤ 2500)    (1 ≤ W ≤ 200)

做法

要使结束的时间早于开始的时间，即为图中含有负圈，即检测给定图中是否有负圈。 Bellman-Ford模板题， 要注意输入正负边时的细节，以及总边数的处理，防止边数组开小了，另外注意一下重边的情况

AC-Code (C++)

Time: 125 ms  Memory: 764 kb

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<string> #include<vector> #include<functional> using namespace std; const int MAXN = 505; const int MAXM = 5500; const int INF = 1000000000; int F, N, M, W; //样例数，结点数，正边数（双向），负边数（单向） int d[MAXM]; //到起点距离 int u[MAXM]; //起点 int v[MAXM]; //终点 int w[MAXM]; //权值 bool ans = false; void bellman_ford(void) { for (int k = 0; k <= N - 1; k++) { if (k == N - 1) { ans = true; break; } bool temp = false; for (int i = 1; i <= M * 2 + W; i++) { int x = u[i], y = v[i]; if (d[x] < INF) { int dy = d[y]; d[y] = min(d[y], d[x] + w[i]); if (d[y]!=dy) temp = true; } } if (!temp) break; } return; } int main(void) { scanf("%d", &F); while (F--) { scanf("%d %d %d", &N, &M, &W); for (int i = 1; i <= M * 2 + W; i++) { w[i] = INF; } for (int i = 1; i <= N; i++) { d[i] = INF; } d[1] = 0; ans = false; for (int i = 1; i <= M; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); int j = 2 * i - 1; u[j] = a; v[j] = b; w[j] = min(w[j], c); //解决重边 j++; u[j] = b; v[j] = a; w[j] = min(w[j], c); } for (int i = M * 2 + 1; i <= 2 * M + W; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); u[i] = a; v[i] = b; w[i] = min(w[i], -1*c); } bellman_ford(); if (ans) printf("YES\n"); else printf("NO\n"); } return 0; }

C - Cow Contest

POJ - 3660

题目大意

有1~N一共N个结点，每个结点都有一头奶牛，

每只奶牛都打算到结点X（1<=X<=N）来参加派对，

并且在派对结束后回到原来的结点，

每只奶牛都选择最短的路程，

一共有M条单向的路，每条路通过的时间为Ti，（单向有权）

(1 ≤ N ≤ 1000)    (1 ≤ M ≤ 100,000)    (1 ≤ T_i ≤ 100)

问：来回的路程最长的奶牛经过的总路程为多少？

做法

单源最短路（SSSP）问题的变种，“回家”即为从X到各点的最短路，“前往派对”即为将所有道路取反后，从X到各个点的最短路 比较稀疏的图，用Dijkstra模板即可

AC-Code (C++)

Time: 47 ms  Memory: 1060 kb