UVA 718 - Skyscraper Floors

題目鏈接

題意：在一個f層高的樓上，有e個電梯，每個電梯有x，y表示y + k * x層都可以到，現在要問從a層能否到達b層（中間怎麼換乘電梯不限制）

思路：對於兩個電梯間能不能換乘，只要滿足y[i] + xx x[i] == y[j] + yy y[j].然後移項一下，就可以用拓展歐幾裡得求解，進而求出x,y的通解，然後利用通解范圍x' >= 0, y' >= 0, x[i] x' + y[i] <= f, x[j] y' + y[j] <= f,求出通解中t的上限和下限，就可以判斷有無解了，然後就建圖，把兩個可以換乘電梯建邊，然後在讓a, b分別和電梯判斷能不能到，能到建邊，最後dfs一遍就能判斷能否達到了。

代碼：

#include 
#include 
#include 
#include 
using namespace std;

const int INF = 0x3f3f3f3f;
int t, f, e, a, b, x[105], y[105], vis[105];
vector g[105];

int exgcd(int a, int b, int &x, int &y) {
	if (!b) {x = 1; y = 0; return a;}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

void build(int v, int u, int i) {
	if (v < y[i]) return;
	if ((v - y[i]) % x[i] == 0) {
		g[u].push_back(i);
		g[i].push_back(u);
 	}
}

void build2(int i, int j) {
	int xx, yy;
	int a = x[i], b = -x[j], c = y[j] - y[i];
	int d = exgcd(a, b, xx ,yy);
	if (c % d) return;
	int down = -INF;
	int up = INF;
	if (b / d > 0) {
 		down = max(down, (int)ceil(-xx * c * 1.0 / b));
 		up = min(up, (int)floor(((f - y[i]) * 1.0 * d / x[i] - xx * c * 1.0) / b));
	}
	else {
		down = max(down, (int)ceil(((f - y[i]) * 1.0 * d / x[i] - xx * c * 1.0) / b));
 		up = min(up, (int)floor(-xx * c * 1.0 / b));
	}
	if (a / d > 0) {
		down = max(down, (int)ceil((yy * c * 1.0 - (f - y[j]) * 1.0 * d / x[j]) / a));
 		up = min(up, (int)floor(yy * c * 1.0 / a));
	}
	else {
 		down = max(down, (int)ceil(yy * c * 1.0 / a));
 		up = min(up, (int)floor((yy * c * 1.0 - (f - y[j]) * 1.0 * d / x[j]) / a));
	}
	if (down > up) return;
	g[i].push_back(j);
	g[j].push_back(i);
}

bool dfs(int u) {
	if (u == e + 1) return true;
	vis[u] = 1;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (vis[v]) continue;
		if (dfs(v)) return true;
 	}
 	return false;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		memset(g, 0, sizeof(g));
		scanf("%d%d%d%d", &f, &e, &a, &b);
		for (int i = 1; i <= e; i++) {
			scanf("%d%d", &x[i], &y[i]);
   			build(a, 0, i);
   			build(b, e + 1, i);
		}
		for (int i = 1; i <= e; i++) {
			for (int j = i + 1; j <= e; j++) {
				build2(i, j);
   			}
  		}
  		memset(vis, 0, sizeof(vis));
  		if (dfs(0)) printf("It is possible to move the furniture.\n");
  		else printf("The furniture cannot be moved.\n");
 	}
	return 0;
}