UVa1466/LA4849 String Phone

2024-05-29 00:44
文章标签 string phone uva1466 la4849

本文主要是介绍UVa1466/LA4849 String Phone,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

UVa1466/LA4849 String Phone

  • 题目链接
  • 题意
  • 分析
  • AC 代码

题目链接

   本题是2010年icpc亚洲区域赛大田赛区的G题

题意

   平面网格上有n(n≤3000)个单元格,各代表一个重要的建筑物。为了保证建筑物的安全,警察署给每个建筑物派了一名警察,并配发了一些有绳电话以供联络。有绳电话是指长度固定的电话,且电话两端的距离必须保持不变。在本题中,坐标(x1,y1)和(x2,y2)之间的距离为|x1-x2|+|y1-y2|。以无向加权图的形式给出哪些警察之间会使用有绳电话,以及每根绳子的长度,如下图所示,这个图保证是连通的。
有绳电话
   现在已经确定每名警察所巡逻的建筑物,请判断是否存在一种方案:每个建筑物选定一个顶点安置电话,使得所有有绳电话都能正常使用。

分析

   先说一个坑点:题目说图保证是连通的,实际上可能不连通,要对各个连通分量单独处理。
   考虑满足距离要求的顶点其实可以分成两类(0:左下/右上、1:左上/右下)并且只能选择一类,每类也只能选则一个,假定有绳电话一端的建筑物选定了0/1类顶点,则另外一端建筑物选定的顶点类别可以通过二染色确定:此有绳电话权值的奇偶性已知(因为长度已知),另外一端建筑物只有选特定类别的顶点才能维持两端点距离的奇偶性与权值要求的相符,这里暂时不需要准确到距离与权值相同,后面做2-SAT来处理这一点即可。
   有绳电话一端的建筑物选定了顶点类别后,其所在连通分量的二染色方案如果不存在,那么这种选择不可行;如果二染色方案存在,根据距离需要权值相同的限制建边,用2-SAT解决:枚举有绳电话两端具体选择的点u,v,此时实际距离如果和权值不相同,则连边 u → v ˜ u\rightarrow \~v uv˜ v → u ˜ v\rightarrow \~u vu˜

AC 代码

#include <iostream>
#include <cstring>
using namespace std;#define N 3010
int dx[][2] = {{0, 1}, {0, 1}}, dy[][2] = {{0, 1}, {1, 0}}, d[N][N], g0[N][N], g[N<<1][N<<1], c0[N], c[N<<1], f[N], x[N], y[N], color[N], s[N<<1], sn[N<<1], low[N<<1], pre[N<<1], clk, cc, p, m, n;int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);
}bool bipartite(int u) {for (int i=0; i<c0[u]; ++i) {int v = g0[u][i], b = ((abs(x[u]-x[v]) + abs(y[u]-y[v])) ^ d[u][v] ^ color[u]) & 1;if (color[v] < 0) {color[v] = b;if (!bipartite(v)) return false;} else if (color[v] != b) return false;}return true;
}void add_clause(int u, int v) {g[u][c[u]++] = v^1; g[v][c[v]++] = u^1;
}bool dfs(int u) {low[u] = pre[u] = ++clk; s[p++] = u;for (int i=0, v; i<c[u]; ++i) if (!pre[v = g[u][i]]) {if (!dfs(v)) return false;low[u] = min(low[u], low[v]);} else if (!sn[v]) low[u] = min(low[u], pre[v]);if (low[u] == pre[u]) {++cc;while (true) {if (cc == sn[s[--p]^1]) return false;sn[s[p]] = cc;if (s[p] == u) break;}}return true;
}bool check(int r, int b) {memset(color, -1, sizeof(color)); color[r] = b;if (!bipartite(r)) return false;memset(c, p = 0, sizeof(c)); memset(pre, clk = 0, sizeof(pre)); memset(sn, cc = 0, sizeof(sn));for (r=1; r<=n; ++r) if (color[r] >= 0) for (int i=0; i<c0[r]; ++i) for (int j=0, a=g0[r][i]; j<2; ++j) {int xu = x[r] + dx[color[r]][j], yu = y[r] + dy[color[r]][j], u = r<<1 | j;for (int k=0; k<2; ++k) {int xv = x[a] + dx[color[a]][k], yv = y[a] + dy[color[a]][k], v = a<<1 | k;if (abs(xu-xv)+abs(yu-yv) != d[r][a]) add_clause(u, v);}}for (int u=2, m=(n+1)<<1; u<m; ++u) if (!pre[u] && !dfs(u)) return false;return true;
}void solve() {cin >> n;for (int i=1; i<=n; ++i) cin >> x[i] >> y[i], c0[i] = 0, f[i] = i;cin >> m;while (m--) {int u, v; cin >> u >> v >> d[u][v];d[v][u] = d[u][v]; g0[u][c0[u]++] = v; g0[v][c0[v]++] = u; f[find(u)] = find(v);}bool ok  = true;for (int i=1; i<=n; ++i) if (find(i) == i && !check(i, 0) && !check(i, 1)) {ok = false; break;}cout << (ok ? "possible" : "impossible") << endl;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t; cin >> t;while (t--) solve();return 0;
}

这篇关于UVa1466/LA4849 String Phone的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012166

相关文章

cell phone teardown 手机拆卸

tweezer 镊子 screwdriver 螺丝刀 opening tool 开口工具 repair 修理 battery 电池 rear panel 后盖 front and rear cameras 前后摄像头 volume button board 音量键线路板 headphone jack 耳机孔 a cracked screen 破裂屏 otherwise non-functiona

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

hdu2072(string的应用)

单词数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25447    Accepted Submission(s): 5957 Problem Description lily的好朋友xiaoou333最近很空,他

MiniCPM-V: A GPT-4V Level MLLM on Your Phone

MiniCPM-V: A GPT-4V Level MLLM on Your Phone 研究背景和动机 现有的MLLM通常需要大量的参数和计算资源,限制了其在实际应用中的范围。大部分MLLM需要部署在高性能云服务器上,这种高成本和高能耗的特点,阻碍了其在移动设备、离线和隐私保护场景中的应用。 文章主要贡献: 提出了MiniCPM-V系列模型,能在移动端设备上部署的MLLM。 性能优越:

【UVA】10739 - String to Palindrome(动态规划)

比较水的动态规划 dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数 其中删除操作和添加操作本质上是一样的。 三个状态转移方程: dp[i][j] = min(dp[i][j] ,dp[i + 1][j]); dp[i][j] = min(dp[i][j] ,dp[i + 1][j - 1]); dp[i][j] = min(dp[i][j] ,dp[

理解String的compareTo()方法返回值

compareTo()的返回值是整型,它是先比较对应字符的大小(ASCII码顺序), 如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值。 如果第一个字符和参数的第一个字符相等,则以第二个字符和参数的第二个字符作比较, 以此类推,直至比较的字符或被比较的字符有一方全比较完,这时就比较字符的长度。 我们可以通过阅读源码加深对compareTo()的理解: comp

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

leetcode#541. Reverse String II

题目 Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of

Java中Map取值转String Null值处理

Map<String, Object> 直接取值转String String value = (String)map.get("key") 当map.get(“key”)为Null值时会报错。 使用String类的valueOf静态方法可以解决这个问题 String value = String.valueOf(map.get("key"))