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 <stdio.h>
#include <string.h>
#include <vector>
#include <math.h>
using namespace std;const int INF = 0x3f3f3f3f;
int t, f, e, a, b, x[105], y[105], vis[105];
vector<int> 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;
}