题目链接：uva 718 - Skyscraper Floors

题目大意：一栋大楼，有F层楼，E个电梯，现在要从A层到B层，问是否可行，每个电梯给出Xi和Yi,代表这个电梯可以到达的层数Yi+k?Xi(k≥0)

解题思路：建图，以A，B以及电梯为节点建图，将可以到达A，B这两层的电梯与这两点建边，在将两两电梯可以达到同一层的建边，判断方法为:Yi+aXi=Yj+bXj,移项得：aXi+bXj=Yj?Yi,即是一个线性方程，用拓展欧几里得算法求出通解的形式，判断是否存在通解在0~F之间即可。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; const int maxn = 105; const int INF = 0x3f3f3f3f; int F, E, A, B, X[maxn], Y[maxn]; vector
         
           g[maxn]; void gcd (int a, int b, int& d, int& x, int& y) { if (b == 0) { d = a; x = 1; y = 0; } else { gcd(b, a%b, d, y, x); y -= (a/b)*x; } } void addPoint (int k, int u, int v) { if (k < Y[v]) return ; if ((k-Y[v]) % X[v] == 0) { g[v].push_back(u); g[u].push_back(v); } } void addEdge (int u, int v) { int a = X[u], b = -X[v], c = Y[v] - Y[u]; int d, xi, yi; gcd(a, b, d, xi, yi); if (c % d) return ; int lower = -INF, up = INF; double T = (F - Y[u]) * 1.0 / X[u]; if (b / d > 0) { up = min (up, (int)floor((T*d - xi*c) / b)); lower = max(lower, (int)ceil(-xi*c*1.0/b)); } else { up = min(up, (int)floor(-xi*c*1.0/b)); lower = max(lower, (int)ceil((T*d - xi*c) / b)); } T = (F - Y[v]) * 1.0 / X[v]; if (a / d > 0) { up = min(up, (int)floor((yi*c*1.0)/a)); lower = max(lower, (int)ceil((T*d*-yi*c) / a)); } else { up = min(up, (int)floor((T*d*-yi*c) / a)); lower = max(lower, (int)ceil((yi*c*1.0)/a)); } if (up < lower) return; g[u].push_back(v); g[v].push_back(u); } void init () { scanf("%d%d%d%d", &F, &E, &A, &B); for (int i = 0; i <= E+1; i++) g[i].clear(); for (int i = 1; i <= E; i++) { scanf("%d%d", &X[i], &Y[i]); addPoint(A, 0, i); addPoint(B, E+1, i); } for (int i = 1; i <= E; i++) { for (int j = 1; j <= E; j++) addEdge(i, j); } } bool bfs (int s, int e) { int vis[maxn]; memset(vis, 0, sizeof(vis)); queue
          
            que; que.push(s); vis[s] = 1; while (!que.empty()) { int u = que.front(); que.pop(); if (u == e) return true; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (vis[v]) continue; que.push(v); vis[v] = 1; } } return false; } int main () { int cas; scanf("%d", &cas); while (cas--) { init (); if (bfs(0, E+1)) printf("It is possible to move the furniture.\n"); else printf("The furniture cannot be moved.\n"); } return 0; }