Участник:Muradyan Armen/TAXI

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/TAXI/

<code_cpp>

  1. include <stdio.h>
  2. include <algorithm>
  3. include <queue>

using namespace std;

  1. define MAX 701
  2. define NIL 0
  3. define INF (1<<28)

vector< int > G[MAX]; int n, m, match[MAX], dist[MAX]; int per[410][2], car[210][2];

bool bfs() {

   int i, u, v, len;
   queue< int > Q;
   for(i=1; i<=n; i++) {
       if(match[i]==NIL) {
           dist[i] = 0;
           Q.push(i);
       }
       else dist[i] = INF;
   }
   dist[NIL] = INF;
   while(!Q.empty()) {
       u = Q.front(); 
       Q.pop();
       if(u!=NIL) {
           len = G[u].size();
           for(i=0; i<len; i++) {
               v = G[u][i];
               if(dist[match[v]]==INF) {	
                   dist[match[v]] = dist[u] + 1;
                   Q.push(match[v]);
               }
           }
       }
   }
   return (dist[NIL]!=INF);

}

bool dfs(int u) {

   int i, v, len;
   if(u!=NIL) {
       len = G[u].size();
       for(i=0; i<len; i++) {
           v = G[u][i];
           if(dist[match[v]]==dist[u]+1) {
               if(dfs(match[v])) {
                   match[v] = u;
                   match[u] = v;
                   return true;
               }
           }
       }
       dist[u] = INF;
       return false;
   }
   return true;

}

int hopcroft_karp() {

   int matching = 0, i;
   for(int j=0; j<MAX;j++)
   	match[j]=NIL;
   
   while(bfs())
       for(i=1; i<=n; i++)
           if(match[i]==NIL && dfs(i))
               matching++;
   return matching;

}

int s, c;

bool dist1(int cno, int pno) {

   int d = abs(car[cno][0]-per[pno][0])+abs(car[cno][1]-per[pno][1]);
   d = d*200;
   if(d>=0 and d<=s*c)
       return true;
   return false;

}

int main() { int A, B, P, T, k, i, j;

scanf("%d", &T); while(T--) {

       scanf("%d %d %d %d", &n, &m, &s, &c);

for(i=0; i<MAX;i++) G[i].clear();

       for(i=0; i<n; i++)
           scanf("%d %d", &per[i][0], &per[i][1]);
       for(i=0; i<m; i++)
       {
           scanf("%d %d", &car[i][0], &car[i][1]);
           for(j=0; j<n; j++)
           {
               if(dist1(i, j))
               {
                   G[j+1].push_back(n+i+1);
                   G[n+i+1].push_back(j+1);
               }
           }
       }

printf("%d\n", hopcroft_karp()); } return 0; } </code_cpp>