Hi,
I am trying to solve the following problem: http://www.spoj.com/problems/TAXI/
I have implemented a DFS based maximum flow algorithm. I have tested my code on 30+ test cases and it works correctly in those but I am still getting a WA. The following is my code:
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<bitset>
#include<cstring>
#define MAXP 410
#define MAXC 410
using namespace std;
int pMatch[MAXP]; //stores the cab matched to person[i]
bool seen[MAXP]; //marks if we have already allocated a person or not
int dist(pair<int,int>& a, pair<int,int>& b) {
return (abs(a.first-b.first)+abs(a.second-b.second)); // I have tried both multiplying by 200 here and dividing the speed * time by 200
}
bool findMatch(int cab,int nP, bool adjMat[MAXC][MAXP]) { //dfs based algorithm
for(int j=0;j<nP;j++) {
if(adjMat[cab][j] && !seen[j]) {
seen[j]=true;
if(pMatch[j]<0 || findMatch(pMatch[j],nP,adjMat)) {
pMatch[j]=cab;
return true;
}
}
}
return false;
}
int main() {
int nTest,nP,nC,speed,cTime;
int x,y;
vector<pair<int,int> > pList(MAXP);
vector<pair<int,int> > cList(MAXC);
bool adjMat[MAXC][MAXP];
scanf("%d",&nTest);
for (int t=1;t<=nTest;t++) {
memset(seen,0,sizeof(seen));
memset(pMatch,-1,sizeof(pMatch));
memset(adjMat,0,sizeof(adjMat));
scanf("%d %d %d %d", &nP,&nC,&speed,&cTime);
for(int p=0;p<nP;p++) {
scanf("%d %d",&x,&y);
pList[p]=make_pair(x,y);
}
for(int c=0;c<nC;c++) {
scanf("%d %d",&x,&y);
cList[c]=make_pair(x,y);
for(int j=0;j<nP;j++) {
int ds=dist(cList[c],pList[j]);
if(ds<=(cTime*speed)/200)
adjMat[c][j]=1;
}
}
// for(int i=0;i<nC;i++) {
// for (int j=0;j<nP;j++) {
// printf("%d ",adjMat[i][j]);
// }
// printf("\n");
// }
int result=0;
for(int i=0;i<nC;i++) {
result+=findMatch(i,nP,adjMat);
}
printf("%d\n",result);
}
return 0;
}
Please let me know what I am doing wrong here. The following are some sample test cases that I tried:
7
7 4 10 40
2 5
0 1
100 3
23 1
42 2
3 4
5 2
1 52
3 2
3 4
5 2
7 4 10 40
2 5
0 1
7 3
23 1
42 2
3 4
5 2
1 52
3 2
3 4
5 2
7 4 10 40
2 5
0 1
7 3
2 1
4 2
3 4
5 2
1 9
3 2
3 4
5 2
7 4 1 2
2 5
0 1
7 3
2 1
4 2
3 4
5 2
1 9
3 2
3 4
5 2
7 4 2000 100
2 555
0 101
70 3325
2 11152
4 2125
3 4000
5 21254
1 94564
3 2468
3 411
5 225
7 4 2000 1000000
2 555
0 101
70 3325
2 11152
4 2125
3 4000
5 21254
1 94564
3 2468
3 411
5 225
2 3 10 40
2 5
5 2
2 3
4 1
4 4