@topcoder - 2017TCOAlgorithmRound2A - D1L2@ DistanceZeroAndOne

╰半夏微凉° 2023-06-01 14:56 9阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

一个 n 个点的无向简单的连通图，编号从 0 到 n-1。

现给出每个点到点 0 的距离 dist0\[\]、每个点到点 1 的距离 dist1\[\]，还原整张图，或判断无解。

**Constraints**  
n 在 2 到 50 之间。  
dist0 与 dist1 中的元素都在 0 到 n-1 之间。

**Examples**  
0)  
\{0,2,1\}  
\{2,0,1\}  
Returns: \{  
"NNY",  
"NNY",  
"YYN" \}  
整张图为 0 - 2 - 1。

1)  
\{0,2,1\}  
\{1,0,2\}  
Returns: \{ \}  
dist0\[1\] ≠ dist1\[0\]。

## @solution@ ##

根据三角形不等式，假如 u 与 v 之间有边，则 |dist0\[u\] - dist0\[v\]| ≤ 1 且 |dist1\[u\] - dist1\[v\]| ≤ 1。

如果 u, v 之间可以连边（即满足三角形不等式），则连 (u, v)。  
显然边连的越多，点之间的距离越精确。  
所以要是有解，则上面的连边方案一定可以得到一个合法解。

我们连完边过后再跑两边 bfs 检验一下这个图是否满足 dist0 与 dist1 的限制。

## @accepted code@ ##

#include<queue> #include<cstdio> #include<vector> #include<iostream> #include<algorithm> using namespace std; class DistanceZeroAndOne{ #define MAXN 50 private: int a[MAXN][MAXN], n; int abs(int x) {return x >= 0 ? x : -x;} int d[MAXN]; public: void bfs(int x) { for(int i=0;i<n;i++) d[i] = n; d[x] = 0; queue<int>que; que.push(x); while( !que.empty() ) { int f = que.front(); que.pop(); for(int i=0;i<n;i++) if( a[f][i] && d[f] + 1 < d[i] ) { d[i] = d[f] + 1, que.push(i); } } } vector<string>ans; vector<string>construct(vector<int>d0, vector<int>d1) { ans.clear(), n = d0.size(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) if( i != j && abs(d0[i] - d0[j]) <= 1 && abs(d1[i] - d1[j]) <= 1 ) a[i][j] = 1; bool flag = true; bfs(0); for(int i=0;i<n;i++) if( d[i] != d0[i] ) flag = false; if( !flag ) return ans; bfs(1); for(int i=0;i<n;i++) if( d[i] != d1[i] ) flag = false; if( !flag ) return ans; for(int i=0;i<n;i++) { string s = ""; for(int j=0;j<n;j++) if( a[i][j] ) s = s + 'Y'; else s = s + 'N'; ans.push_back(s); } return ans; } };

## @details@ ##

好像。。。也没什么细节。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11568373.html