链接: link.

C - Crowd Control

题意：

给定$n$个点$m$条边的无向图，每条边都有一个容量，从起点$0$到终点$n-1$的容量，取决于路径上的最小容量，为了使从起点到终点容量最大化，需要删除一些边，以便于从$0$走到$n-1$的最小容量是最大的，并把删除的边的编号由小到大输出

思路：

先套 $spfa$最大化最小边，并记录下路径，把从$0$到$n-1$的路径存下来后，再通过两重循环，或者$dfs$把不是对应路径上的边，都记下来，然后排序去重输出即可，由于是链式前向星存的是无向边，找答案就按有一条边来算就行，所以就是$i+=2$，边的编号就是链式前向星中的编号$/2$
也可以通过二分$+BFS$来实现最大化最小边，然后再找到路径，再删除非路径的边，或者最大生成树
链接: link.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
const int inf = 0x7fffffff;
int ue[N], h[N], e[N], ne[N], w[N], idx;
int dis[N], vis[N], pre[N];
int n, m;
int st, ed;
vector<int> path;
vector<int> res;
void add_edge(int a, int b, int c) {ue[idx] = a;e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void spfa() {memset(dis, 0, sizeof(dis));queue<int> q;q.push(st);dis[st] = inf;vis[st] = 1;while (!q.empty()) {int t = q.front();q.pop();vis[t] = 0;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (dis[j] < min(dis[t], w[i])) {dis[j] = min(dis[t], w[i]);pre[j] = t;if (!vis[j]) {vis[j] = 1;q.push(j);}}}}
}
void dfs1(int u) {path.push_back(u);vis[u] = 1;if (u == 0) return;dfs1(pre[u]);
}void dfs2(int n) {int now = path[n];if (n == 0) {for (int i = 0; i < idx; i += 2) {if (ue[i] == now && e[i] != path[n + 1] ||e[i] == now && ue[i] != path[n + 1]) {res.push_back(i / 2);}}return;} else {for (int i = 0; i < idx; i += 2) {if (ue[i] == now && e[i] != path[n + 1] && e[i] != path[n - 1] ||e[i] == now && ue[i] != path[n + 1] && ue[i] != path[n - 1]) {res.push_back(i / 2);}}dfs2(n - 1);}
}
int main() {memset(h, -1, sizeof(h));scanf("%d%d", &n, &m);for (int i = 0, a, b, c; i < m; i++) {scanf("%d%d%d", &a, &b, &c);add_edge(a, b, c);add_edge(b, a, c);}st = 0, ed = n - 1;spfa();memset(vis, 0, sizeof(vis));dfs1(ed);dfs2(path.size() - 1);sort(res.begin(), res.end());res.erase(unique(res.begin(), res.end()), res.end());if (res.size() == 0) {puts("none");} else {for (int i = 0; i < res.size(); i++) {printf("%d ", res[i]);}}
}

A - Abandoned Animal

题意：

给定$n$个超市的位置编号，和他们所卖的商品，现在给定一份$m$行的购买商品的清单，问按照清单列举的顺序买东西，所走的路径是唯一的，不确定的，还是不存在的

思路：

开二维$vector$,来存超市与商品的关系，然后先按照在清单顺序的情况下，多个商店符合条件的话，优先去位置最近的商店，再按照在清单顺序的情况下，多个商品符合条件，游仙区位置最远的商店，然后看两种遍历方法的路径是否一样，如果无法遍历成功，就是不存在，如果路径相同就是唯一，不相同就是不确定

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> shop[N];
map<string, int> mp;
int a[N];
char s[20];
int n, k, m;
int id;
int idx = 1;
vector<int> pre;
vector<int> suf;
int main() {cin >> n >> k;for (int i = 0; i < k; i++) {scanf("%d%s", &id, s);if (mp[s]) {shop[id].push_back(mp[s]);} else {mp[s] = idx;shop[id].push_back(idx++);}}cin >> m;for (int i = 0; i < m; i++) {scanf("%s", s);a[i] = mp[s];}int cur = 0;int flag = 0;for (int i = 0; i < n && cur < m; i++) {int len = shop[i].size();for (int j = 0; j < len; j++) {if (shop[i][j] == a[cur]) {pre.push_back(i);cur++;i--;break;}}}if (pre.size() == m) {flag++;}cur = m - 1;for (int i = n - 1; i >= 0 && cur >= 0; i--) {int len = shop[i].size();for (int j = len - 1; j >= 0; j--) {if (shop[i][j] == a[cur]) {suf.push_back(i);cur--;i++;break;}}}if (suf.size() == m) {flag++;}if (flag == 0) {puts("impossible");} else if (flag == 1) {puts("unique");} else {bool f = 0;reverse(suf.begin(), suf.end());for (int i = 0; i < m; i++) {if (pre[i] != suf[i]) {f = 1;break;}}if (f)puts("ambiguous");elseputs("unique");}return 0;
}

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！