首页 > 代码库 > ZOJ 3261 Connections in Galaxy War
ZOJ 3261 Connections in Galaxy War
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3261
题意:
一. 给定N个星球(0,...,N-1)及其对应的power(p0,...pn-1)
二. 给定M条星球a与b间(a!=b)的通路
三. 给出Q个指令,"destroy a b"代表此时星球a b间的通路(必定已连接)被破坏了,"query a"要求输出当时应对星球a进行救援的星球的编号
规则为: ①与星球a有直接或间接通路的星球中power最大的
②该星球的power大于pa
③符合①②的星球中取编号最小的
④如无符合的星球,则输出"-1"
ps: 含多个case,case之间需输出空行
思路:
离线处理+并查集
逆向处理,一次性读入并保存所有指令,用map标记被破坏的边,将未被破坏的边用并查集连接,生成最终的状态
再从后往前处理指令,是destroy就并查集连接该边,是query就判断自身是否为根来决定答案
将答案依次保存进数组中,最后逆向输出
代码: 190ms 2264KB
#include <cstdio>#include <map>using namespace std;#define N 10001#define NN 50001#define swap(x,y) x=x^y;y=x^y;x=x^y;struct Node { int a, b; bool m; //两种指令} edge[N << 1], que[NN]; //边,指令int fa[N], pw[N], ans[NN]; //父节点,power值,答案map<int, bool> mp; //标记被破坏的边void init(int n) { mp.clear(); for (int i = 0; i < n; i++) { fa[i] = i; }}int findfa(int n) { return n == fa[n] ? n : fa[n] = findfa(fa[n]);}void unite(int a, int b) { a = findfa(a); b = findfa(b); if (a != b) { if (pw[a] > pw[b] || pw[a] == pw[b] && a < b) { //power大及编号小的为父节点 fa[b] = a; } else { fa[a] = b; } }}int main() { int n, m, q; char c[8]; bool f = 1; while (~scanf("%d", &n)) { if (!f) { printf("\n"); } f = 0; init(n); for (int i = 0; i < n; i++) { scanf("%d", &pw[i]); } scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%d%d" , &edge[i].a , &edge[i].b); if (edge[i].a > edge[i].b) { swap(edge[i].a , edge[i].b); //小号在前 } } scanf("%d", &q); for (int i = 0; i < q; i++) { scanf("%s", c); if (c[0] == ‘d‘) { scanf("%d%d", &que[i].a, &que[i].b); if (que[i].a > que[i].b) { swap(que[i].a , que[i].b); //小号在前 } que[i].m = 1; mp[que[i].a * N + que[i].b] = 1; //被毁标记 } else { scanf("%d", &que[i].a); que[i].m = 0; } } for (int i = 0; i < m; i++) { if (!mp[edge[i].a * N + edge[i].b]) { //未被毁则合并 unite(edge[i].a, edge[i].b); } } int ansn = 0; for (int i = q - 1; i >= 0; i--) { if (que[i].m) { unite(que[i].a, que[i].b); //被毁的连回去 } else { int t = findfa(que[i].a); if (pw[t] <= pw[que[i].a]) { //根的power不比自己大 ans[ansn++] = -1; } else { ans[ansn++] = t; } } } for (int i = ansn - 1; i >= 0; i--) { printf("%d\n", ans[i]); } } return 0;}
ZOJ 3261 Connections in Galaxy War
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。