I know I'm new to Bipartite matching but I've submitted a problem with a very similar code & got it AC. I really don't know what's wrong :'(
Code: Select all
# include <iostream>
# include <fstream>
# include <queue>
# include <stack>
# include <cmath>
using namespace std;
ifstream fin("10080.txt");
#define cin fin
bool discovered[300];
int parent[300];
bool isFinished;
stack<int>S;
double gophers[300][2];
double holes[300][2];
struct Edge
{
Edge()
{
f = 0;
c = cf = 0;
}
int c, f, cf;
};
struct Graph
{
int nVertices;
int nEdges;
Edge edges[300][300];
}g;
void Construct_Graph(int n, int m, double v, double s)
{
int i, j;
double x, y;
double deltax, deltay, dist, max = v * s;
for(i=0; i<n; i++)
{
cin>>x>>y;
gophers[i][0] = x;
gophers[i][1] = y;
}
for(i=0; i<m; i++)
{
cin>>x>>y;
holes[i][0] = x;
holes[i][1] = y;
}
for(i=0; i<n+m+2; i++)
{
for(j=0; j<n+m+2; j++)
{
g.edges[i][j].c = 0;
g.edges[i][j].cf = 0;
g.edges[i][j].f = 0;
}
}
for(i=0; i<n; i++)
{
g.edges[n+m][i].c = 1;
g.edges[n+m][i].cf = 1;
for(j=0; j<m; j++)
{
g.edges[j+n][n+m+1].c = 1;
g.edges[j+n][n+m+1].cf = 1;
deltax = abs(gophers[i][0] - holes[j][0]);
deltay = abs(gophers[i][1] - holes[j][1]);
deltax *= deltax;
deltay *= deltay;
dist = pow(deltax + deltay, 0.5);
if(dist <= (double)max)
{
g.edges[i][j+n].c = 1;
g.edges[i][j+n].cf = 1;
g.edges[j+n][i].c = 1;
g.edges[j+n][i].cf = 1;
}
}
}
}
void Initialize_Search()
{
int i;
for(i=0; i<g.nVertices; i++)
{
discovered[i] = 0;
parent[i] = -1;
}
}
int find_path(int start, int end, int min)
{
S.push(end);
if((start == end) || (end == -1))
return min;
else
{
if(g.edges[parent[end]][end].cf < min)
min = g.edges[parent[end]][end].cf;
return find_path(start, parent[end], min);
}
}
int Process(int start, int end)
{
while(!S.empty())
S.pop();
int v, u, min = 1000;
min = find_path(start, end, 1000);
if(!S.empty())
{
v = S.top();
S.pop();
}
while(!S.empty())
{
u = S.top();
S.pop();
g.edges[v][u].f += min;
g.edges[v][u].cf -= min;
g.edges[u][v].f -= min;
g.edges[u][v].cf += min;
v = u;
}
return min;
}
int BFS(int start, int end)
{
Initialize_Search();
queue<int>q;
int v;
int i;
int min;
q.push(start);
discovered[start] = true;
while(!q.empty())
{
v = q.front();
q.pop();
if(v == end)
{
min = Process(start, end);
return min;
}
for(i=0; i<g.nVertices; i++)
{
if(discovered[i] == false && g.edges[v][i].cf > 0)
{
q.push(i);
discovered[i] = true;
parent[i] = v;
}
}
}
return 0;
}
int main()
{
int n, m, maxflow, bfs;
double v, s;
while(cin>>n>>m>>s>>v)
{
maxflow = bfs = 0;
g.nVertices = n + m + 2;
Construct_Graph(n, m, v, s);
do
{
bfs = BFS(n+m, n+m+1);
maxflow += bfs;
}
while(bfs);
cout<<n - maxflow<<endl;
}
return 0;
}