UVA 10319 - Manhattan(2-SET)
2024-09-06 08:26:19
UVA 10319 - Manhattan
题意:一个城市,有南北和东西街道。每种街道都是单行道,如今给定几个起点和终点。要求起点和终点必须最多转一次弯能够到达,问能否够满足全部的起点终点
思路:2-set,对于东西。南北街道,向西(北)为false,向东(南)为true,对于每一个起点终点,肯定是走坐标相应的那4条街道,表示出来是(s1 & a2) | (s2 & a1),能够转化成(s1 | s2) & (s1 | a1) & (a2 | v2) & (a2 | a1)相应2-set4条边,注意假设横坐标或纵坐标同样,仅仅要建一条边(s, s)就可以。这样建图,进行2-set判定就可以
代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std; const int MAXNODE = 2005; struct TwoSet {
int n;
vector<int> g[MAXNODE * 2];
bool mark[MAXNODE * 2];
int S[MAXNODE * 2], sn; void init(int tot) {
n = tot * 2;
for (int i = 0; i < n; i += 2) {
g[i].clear();
g[i^1].clear();
}
memset(mark, false, sizeof(mark));
} void add_Edge(int u, int uval, int v, int vval) {
u = u * 2 + uval;
v = v * 2 + vval;
g[u^1].push_back(v);
g[v^1].push_back(u);
} bool dfs(int u) {
if (mark[u^1]) return false;
if (mark[u]) return true;
mark[u] = true;
S[sn++] = u;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!dfs(v)) return false;
}
return true;
} bool solve() {
for (int i = 0; i < n; i += 2) {
if (!mark[i] && !mark[i + 1]) {
sn = 0;
if (!dfs(i)){
for (int j = 0; j < sn; j++)
mark[S[j]] = false;
sn = 0;
if (!dfs(i + 1)) return false;
}
}
}
return true;
}
} gao; int n, S, A, m; int main() {
scanf("%d", &n);
while (n--) {
scanf("%d%d%d", &S, &A, &m);
gao.init(S + A);
int s1, a1, s2, a2;
while (m--) {
scanf("%d%d%d%d", &s1, &a1, &s2, &a2);
s1--; a1--; s2--; a2--;
if (s1 == s2 && a1 == a2) continue;
a1 += S;
a2 += S;
if (s1 == s2) gao.add_Edge(s1, (a1 < a2), s2, (a1 < a2));
else if (a1 == a2) gao.add_Edge(a1, (s1 < s2), a2, (s1 < s2));
else {
gao.add_Edge(s1, (a1 < a2), s2, (a1 < a2));
gao.add_Edge(s1, (a1 < a2), a1, (s1 < s2));
gao.add_Edge(a2, (s1 < s2), s2, (a1 < a2));
gao.add_Edge(a2, (s1 < s2), a1, (s1 < s2));
}
}
printf("%s\n", gao.solve() ? "Yes" : "No");
}
return 0;
}
最新文章
- bootstrap之移动支持
- ADV-时间分配
- entOS7安装iptables防火墙,试验未通过
- linux中脚本的一些小知识的积累
- 深度分析Java的ClassLoader机制(源码级别)
- Java 8 中的 Streams API 详解
- JavaScript语言基础知识6
- 修改TabPageIndicator下划线的颜色
- BZOJ.4145.[AMPPZ2014]The Prices(状压DP)
- [Swift]LeetCode838. 推多米诺 | Push Dominoes
- 【题解】Luogu CF343D Water Tree
- Spark2.X环境准备、编译部署及运行
- win10 17025 触摸bug
- linux 的常用命令---------第十阶段
- 使用 SendARP 获取 MAC 地址(使用SendARP API函数,很多相关文章)
- Beta阶段第1周/共2周 Scrum立会报告+燃尽图 05
- 阿里云服务器ECS上ubuntu安装nginx后默认站点页面打开错误,显示无法访问此网站
- Codeforces Round #361 (Div. 2) E. Mike and Geometry Problem 离散化 排列组合
- canvas动画--demo
- 转:json注入
热门文章
- [Python爬虫] 之十八:Selenium +phantomjs 利用 pyquery抓取电视之家网数据
- Java 字符串计算频率出现最高的字符
- centos7 minimal connect: Network is unreachable(转)
- web应用程序指识别中的指纹收集
- SHOW CREATE DATABASE Syntax
- css3的Background新属性
- curl Error : maximum redirects followed , 这种问题的一种原因 .
- 客户端与服务端Post报文构造请求及Http Post与Get请求方法
- eclipse Alt+/ 无法提示代码
- VC驿站黑客编程(关机,重新启动,注销)