ZOJ 3811 Untrusted Patrol 并查集

题目链接:点击打开链接

题意:

给定n个点m条边的无向图,k个触发器。

下面k个数表示触发器安装在哪几个点。

下面m行给出边

最后有l个信号,

给出信号发出的触发器的顺序。

每个触发器只会发出一次信号,且一个点只有一个触发器。

有一个人在遍历图。

每经过一个点,那个点的触发器就会发出信号,问是否存在一种走法使得这个人遍历了所有点且触发器发出的信号顺序和给出的一样。

思路:

先把无触发器的点放到图里。

然后根据触发器的信号顺序把点依次加入图中,加入时只添加(与无触发器点相连的边)

然后判断这个点能否与之前的图连通。bfs+并查集判断。

==其实并查集就够了,写的时候有脑洞,bfs就冒出来了

#include #include #include #include #include #include using namespace std; #define ll int typedef pair pii; #define M 400010 #define N 200010 int f[N]; int find(int x){return x==f[x]?x:f[x] = find(f[x]);} void Union(int x,int y){ int fx = find(x), fy = find(y); if(fx==fy)return ; if(fx>fy)swap(fx,fy); f[fx] = fy; } struct Edge{ int from, to, nex; }edge[MG, E[N]; void ADD(int x){ for(int i = 0; i q; q.push(x); vis[x] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].to; Union(v, x); if(vis[v])continue; vis[v] = 1; q.push(v); } } } bool solve(){ scanf("%d %d %d",&n,&m, &k); init(); int i, j, u, v; for(i = 1; i =0){ find(G[i]); find(G[i-1]); if(f[G[i]] != f[G[i-1]]) return false; } } for(i = 1; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:jpa的双向一对多和双向一对一关联关系
下一篇:ZOJ 3816 Generalized Palindromic Number dfs+暴力枚举
相关文章

ZOJ1543 Stripies

ZOJ2425

ZOJ 1205 Martian Addition

ZOJ2722Head-to-Head Match

ZOJ2723 Semi_Primer

ZOJ 3508 The War 贪心

ZOJ 3622 Magic Number 月赛水题

ZOJ 3627 Treasure Hunt II

ZOJ 3631 Watashi's BG

ZOJ 2587 最小割的唯一性

图文推荐

ZOJ 3811 Untrusted Patrol 并查集
ZOJ 3640 Help Me
ZOJ 3811 Untrusted Patrol 并查集
CF 518C(Anya and
ZOJ 3811 Untrusted Patrol 并查集
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-12 人气:8
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.028 (s). 10 q(s)