10080 - Gopher II

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

Post by asmaamagdi » Fri Nov 23, 2007 10:30 pm

Hey all, I don't really like sending my code but I think I have to. Please any1 discovers a bug or a failing test case please tell me about it.
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;
}



---
Asmaa Magdi

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena » Sun Dec 02, 2007 12:21 pm

wa... Could somebody give me some advice ...
///////////////////////////////
#include<stdio.h>
#include<math.h>
#define eps 1e-10
#define N 220

int n,m,s,v;

struct Tnode{
double x;
double y;
};

Tnode a[N];
Tnode b[N];
int src,tar;
int c[N][N];
int r[N][N];
int f[N][N];
int e[N];
int h[N];

double dist(Tnode x, Tnode y){
double u = x.x - y.x;
double v = x.y - y.y;
return sqrt(u*u + v*v);
}
bool find(int & x ,int &y){
int i,j;
for(i=1;i<=n;i++){
for(j=n+1;j<=n+m;j++)
if(r[src] >=1 && r[j] >= 1 && r[j][tar] >= 1){
x = i;
y = j;
return true;
}
}
return false;
}
int min(int x, int y,int z){
int r = x;
if(r>y)r = y;
if(r>z)r=z;
return r;
}
void maxFlow(){
int i,j;
for(i=0;i<=n+m+1;i++)
for(j=0;j<=n+m+1;j++)
f[j] = 0;

for(i=0;i<=n+m+1;i++)
for(j=0;j<=n+m+1;j++)
r[j] = c[j];
int x,y;
while( find(x,y) ){
int rr = min(r[src][x],r[x][y],r[y][tar]);
f[src][x] += rr;
f[x][src] = -1* f[src][x];
f[x][y] += rr;
f[y][x] = -1*f[x][y];
f[y][tar] += rr;
f[tar][y] = -1*f[y][tar];

r[src][x] = c[src][x]-f[src][x];
r[x][src] = c[x][src] - f[x][src];
r[x][y] = c[x][y] -f[x][y];
r[y][x] = c[y][x] -f[y][x];
r[y][tar] = c[y][tar]-f[y][tar];
r[tar][y] = c[tar][y]-f[tar][y];
}
}

void solve(){
int i,j;

for(i=0;i<=n+m+1;i++)
for(j=0;j<=n+m+1;j++)
c[j] = r[j] = f[j] = 0;

src = 0;
tar = n+m+1;

for(i=1;i<=n;i++)
c[src] = 1;
for(i=1;i<=m;i++)
c[n+i][tar] = 1;

for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if( dist(a[i-1],b[j-1]) - v*s <=eps ){
c[n+j] = 1;
}
}

maxFlow();
int res = 0;
for(i=0;i<=n+m+1;i++)
res += f[src][i];
printf("%d\n",n-res);
}

int main(){

//freopen("10080.txt", "r+", stdin);

int i;
while( scanf("%d %d %d %d",&n,&m,&s,&v) != -1 ){
for(i=0;i<n;i++)
scanf("%lf %lf",&a[i].x,&a[i].y);

for(i=0;i<m;i++)
scanf("%lf %lf",&b[i].x,&b[i].y);

solve();

}

return 0;

}

Post Reply

Return to “Volume 100 (10000-10099)”