@topcoder - 2017TCOAlgorithmRound2A - D1L2@ DistanceZeroAndOne

@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。

{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@

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

巴特西

@topcoder - 2017TCOAlgorithmRound2A - D1L2@ DistanceZeroAndOne

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章