|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 798236606 于 2020-2-22 15:53 编辑
传送门:https://pintia.cn/problem-sets/9 ... /994805523835109376
解:
最短路径
1.迪杰斯特拉
- #include <cstdio>
- #include <climits>
- #include <algorithm>
- using namespace std;
- const int maxn = 510;
- int n, m, c1, c2;
- int G[maxn][maxn];
- int men[maxn];//存放点权,即救援队数
- int num[maxn];//存放到每个点的最短路径数
- int w[maxn];//存放可聚集的队伍数
- int v[maxn];//存放最短路径长度
- bool vis[maxn];//是否访问过
- void DJS(int s)
- {
- fill(v, v + n, INT_MAX);
- fill(num, num + n, 0);
- fill(w , w + n, 0);
- v[s] = 0;
- w[s] = men[s];
- num[s] = 1;
- for (int i = 0; i < n; i++)
- {
- int u = -1, min = INT_MAX;
- for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
- if (!vis[i] && v[i] < min) min = v[u = i];
- if (u == -1) return;//如果剩下的顶点与源点不通,返回
- vis[u] = true;
- for (int j = 0; j < n; j++)
- {
- if (vis[j] || G[u][j] == INT_MAX) continue;
- int t = v[u] + G[u][j];
- if (t < v[j])
- {
- v[j] = t;
- num[j] = num[u];
- w[j] = w[u] + men[j];
- }
- else if (t == v[j])
- {
- num[j] += num[u];
- if (w[u] + men[j] > w[j]) w[j] = w[u] + men[j];
- }
- }
- }
- }
- int main(void)
- {
- scanf("%d %d %d %d", &n, &m, &c1, &c2);
- fill(G[0], G[0] + maxn * maxn, INT_MAX);
- for (int i = 0; i < n; i++)
- scanf("%d", men + i);
- while (m--)
- {
- int a, b, l;
- scanf("%d %d %d", &a, &b, &l);
- G[a][b] = G[b][a] = l;
- }
- DJS(c1);
- printf("%d %d", num[c2], w[c2]);
- return 0;
- }
复制代码
2.迪杰斯特拉 + DFS (模板)
- #include <cstdio>
- #include <climits>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int maxn = 510;
- int n, m, c1, c2;
- int G[maxn][maxn];
- int weight[maxn];//存放点权,即救援队数
- int d[maxn];//存放最短路径长度
- bool vis[maxn];//是否访问过
- vector<int> pre[maxn];//存放顶点在最短路径中的前驱
- void DJS(int s)
- {
- fill(d, d + n, INT_MAX);
- d[s] = 0;
- for (int i = 0; i < n; i++)
- {
- int u = -1, min = INT_MAX;
- for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
- if (!vis[i] && d[i] < min) min = d[u = i];
- if (u == -1) return;//如果剩下的顶点与源点不通,返回
- vis[u] = true;
- for (int v = 0; v < n; v++)
- {
- if (vis[v] || G[u][v] == INT_MAX) continue;
- int t = d[u] + G[u][v];
- if (t < d[v])
- {
- d[v] = t;
- pre[v].clear();
- pre[v].push_back(u);
- }
- else if (t == d[v])
- pre[v].push_back(u);
- }
- }
- }
- int num = 0;//存放最短路径条数
- int opt_w = 0;//存放最大点权和
- vector<int> path;
- void DFS(int v)
- {
- if (v == c1)//递归边界,如果遍历到起点
- {
- path.push_back(v);
- num++;
- int val = 0;
- for (int i = path.size() - 1; i >= 0; i--)
- val += weight[path[i]];
- if (val > opt_w) opt_w = val;
- path.pop_back();
- return;
- }
- path.push_back(v);
- for (int i = 0; i < pre[v].size(); i++)
- DFS(pre[v][i]);
- path.pop_back();
- }
- int main(void)
- {
- scanf("%d %d %d %d", &n, &m, &c1, &c2);
-
- fill(G[0], G[0] + maxn * maxn, INT_MAX);
- for (int i = 0; i < n; i++)
- scanf("%d", weight + i);
-
- while (m--)
- {
- int a, b, l;
- scanf("%d %d %d", &a, &b, &l);
- G[a][b] = G[b][a] = l;
- }
- DJS(c1);
- DFS(c2);
- printf("%d %d", num, opt_w);
- return 0;
- }
复制代码
3.BF算法
- #include <cstdio>
- #include <climits>
- #include <cstring>
- #include <vector>
- #include <set>
- #include <algorithm>
- using namespace std;
- const int maxn = 510;
- typedef struct node{
- int id, dis;
- node (int _id, int _dis) : id(_id), dis(_dis) {};
- }Node;
- int n, m, c1, c2;
- int weight[maxn];//存放点权,即救援队数
- int num[maxn];//存放到每个点的最短路径数
- int w[maxn];//存放可聚集的队伍数
- int d[maxn];//存放最短路径长度
- vector<Node> adj[maxn];//邻接表
- set<int> pre[maxn];//存放顶点在最短路径中的前驱
- void BF(int s)
- {
- fill(d, d + n, INT_MAX);
- memset(w, 0, sizeof(w));
- memset(num, 0, sizeof(num));
- w[s] = weight[s];
- d[s] = 0;
- num[s] = 1;
- for (int i = 0; i < n - 1; i++)
- {
- for (int u = 0; u < n; u++)
- {
- if (d[u] == INT_MAX) continue;
- for (int v = 0; v < adj[u].size(); v++)
- {
- int id = adj[u][v].id, dis = adj[u][v].dis;
- if (dis + d[u] < d[id])
- {
- d[id] = dis + d[u];
- num[id] = num[u];
- w[id] = weight[id] + w[u];
- pre[id].clear();
- pre[id].insert(u);
- }
- else if (dis + d[u] == d[id])
- {
- if (weight[id] + w[u] > w[id])
- w[id] = weight[id] + w[u];
- num[id] = 0;
-
- pre[id].insert(u);
- for (set<int>::iterator it = pre[id].begin(); it != pre[id].end(); ++it)
- num[id] += num[*it];
- }
- }
- }
- }
- }
- int main(void)
- {
- // freopen("input.txt", "r", stdin);
- scanf("%d %d %d %d", &n, &m, &c1, &c2);
- for (int i = 0; i < n; i++)
- scanf("%d", weight + i);
-
- while (m--)
- {
- int a, b, l;
- scanf("%d %d %d", &a, &b, &l);
- adj[a].push_back(node(b, l));
- adj[b].push_back(node(a, l));
- }
- BF(c1);
- printf("%d %d", num[c2], w[c2]);
- return 0;
- }
复制代码 |
|