563 - Crimewave
Moderator: Board moderators
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
563 - Runtime Error
Hi. I'm receiving Runtime Error (Inavlid Memory Reference) for about 2 days and can't find where this invalid memory reference can be happening.
Thanks for your help =)
Here's my code (I tried an algorithm that looks like max bipartite matching)
[/code]
Thanks for your help =)
Here's my code (I tried an algorithm that looks like max bipartite matching)
Code: Select all
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
int vis[55][55];
int antx[55][55];
int anty[55][55];
int bank[55][55];
int nvis;
int dirx[] = {1,0,-1,0};
int diry[] = {0,1,0,-1};
int nx, ny;
#define f(i,j,k) for(int i = j; i < k; i++)
#define sz size
#define pb push_back
int dfs(int x, int y){
vis[x][y] = nvis;
int xx, yy;
if(x == 0 || y == 0 || x > nx || y > ny) return 1;
f(i,0,4){
xx = x + dirx[i];
yy = y + diry[i];
if(bank[xx][yy]) continue;
if(vis[xx][yy] >= nvis) continue;
if(antx[xx][yy] == x && anty[xx][yy] == y) continue;
if(anty[xx][yy] == -1 && antx[xx][yy] == -1){
if(dfs(xx,yy)){
antx[xx][yy] = x;
anty[xx][yy] = y;
return 1;
}
else continue;
}
if(dfs(antx[xx][yy],anty[xx][yy])){
antx[xx][yy] = x;
anty[xx][yy] = y;
return 1;
}
}
return 0;
}
vector<int> bx, by;
int main(void){
int n;
scanf("%d",&n);
while(n--){
int b;
scanf("%d %d %d",&nx,&ny,&b);
f(i,0,55) f(j,0,55) bank[i][j]=0;
bx.clear(); by.clear();
int is = 1;
f(i,0,b){
int a,c;
scanf("%d %d",&a,&c);
bx.pb(a); by.pb(c);
if(bank[a][c]){
is = 0;
goto end;
}
bank[a][c]=1;
}
f(i,0,55) f(j,0,55) { vis[i][j] = 0; anty[i][j]=antx[i][j]=-1; }
nvis = 0;
f(i,0,b){
nvis++;
if(!dfs(bx[i],by[i])){
is=0;
break;
}
}
end:;
if(is) printf("possible\n");
else printf("not possible\n");
}
return 0;
}
MaxFlow Algorithm and Problem 563-CrimeWave
The problem 563-CrimeWave is a maximum
flow problem. The funny thing is i've AC
for this problem although i think my solution
is wrong in the way it implements ford-fulkerson
algorithm!!!
Since vertices also have capacities in this
problem, i had the usual idea of splitting
the vertices into two and have the newly
created edge the vertex capacity. But i just
couldn't find a way to split the vertices.
I know it sounds funny, but given the grid like
graph structure it seem very complicated to
split the vertices, and to add pain, this is
an undirected graph.
Finding no other way and since the capacity of
all the vertices is exactly 1, i thought of
using a 'visited' array just to mark an already
visited vertex and never to use it while finding
a new augmenting path. However the way ford-fulkerson
algorithm works i thougth it was incorrect to
do this. BUT it was AC!!
now i've two questions.
(1) is my approach correct or incorrect? why?
(2) how can i split the vertices of an undirected
graph like the one below to accomodate vertex capacities?
Thanks.
flow problem. The funny thing is i've AC
for this problem although i think my solution
is wrong in the way it implements ford-fulkerson
algorithm!!!
Since vertices also have capacities in this
problem, i had the usual idea of splitting
the vertices into two and have the newly
created edge the vertex capacity. But i just
couldn't find a way to split the vertices.
I know it sounds funny, but given the grid like
graph structure it seem very complicated to
split the vertices, and to add pain, this is
an undirected graph.
Finding no other way and since the capacity of
all the vertices is exactly 1, i thought of
using a 'visited' array just to mark an already
visited vertex and never to use it while finding
a new augmenting path. However the way ford-fulkerson
algorithm works i thougth it was incorrect to
do this. BUT it was AC!!
now i've two questions.
(1) is my approach correct or incorrect? why?
(2) how can i split the vertices of an undirected
graph like the one below to accomodate vertex capacities?
Code: Select all
0---0---0
| | |
0---0---0
| | |
0---0---0
i'll be back
-
- New poster
- Posts: 5
- Joined: Sat Dec 30, 2006 2:16 pm
- Location: Hyderabad
- Contact:
Hi,
I don't understand the fact that a bank can be robbed more than once ... I did exactly same as ImLazy has written above but I always get WA![:cry:](./images/smilies/icon_cry.gif)
. My programs output matches with the above output on all the 50 cases [ I suppose the output shown above is correct ]. Can somebody help me out about it. Here is the code for you to have a look =>
Thanks a lot in advance.
I don't understand the fact that a bank can be robbed more than once ... I did exactly same as ImLazy has written above but I always get WA
![:cry:](./images/smilies/icon_cry.gif)
Code: Select all
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<stack>
#include<algorithm>
#include<queue>
#include<list>
#include<map>
#include<cassert>
using namespace std;
/* maximum Flow using Ford Fulkerson method */
#define INF 10000000
int n,source,destination;
list<pair<int,int> > graph[5002];
int calCapacity(int a,int b){
for(list<pair<int,int> >::iterator i=graph[a].begin();i!=graph[a].end();i++){
if((*i).first == b){
return (*i).second;
}
}
return 0;
}
void updateCapacity(int a,int b,int c){
bool state = false;
for(list<pair<int,int> >::iterator i=graph[a].begin();i!=graph[a].end();i++){
if((*i).first == b){
(*i).second += c;
if((*i).second == 0){
graph[a].erase(i);
return;
}
state = true;
break;
}
}
if(!state){
graph[a].push_front(pair<int,int> (b,c));
}
return;
}
int bfsCapacity(){
queue<int> q;
bool visited[n],done=false;
int from[n],cur,where,pathCapacity,prev;
memset(visited,false,sizeof(visited));
from[destination] = from[source] = -1;
q.push(source);
visited[source] = true;
while(!q.empty() && !done){
cur = q.front();q.pop();
for(list<pair<int,int> >::iterator i=graph[cur].begin();i!=graph[cur].end();i++){
if(!visited[(*i).first] && (*i).second > 0){
visited[(*i).first] = true;
q.push((*i).first);
from[(*i).first] = cur;
if((*i).first == destination){
done = true;
}
}
}
}
if(!visited[destination]){
return 0;
}
where = destination;
pathCapacity = INF;
while(from[where] > -1){
pathCapacity = min(pathCapacity,calCapacity(from[where],where));
where = from[where];
}
where = destination;
while(from[where] > -1){
prev = from[where];
updateCapacity(from[where],where,-pathCapacity);
updateCapacity(where,from[where],pathCapacity);
where = from[where];
}
assert(pathCapacity == 1);
return pathCapacity;
}
int maxFlow(){
int answer = 0,p;
while(1){
p = bfsCapacity();
if(!p){
break;
}
answer += p;
}
return answer;
}
int main(){
int N,row,column,c,x,y;
scanf("%d",&N);
while(N--){
scanf("%d%d%d",&column,&row,&c);
source = 0;
destination = 2 * row * column + 1;
n = 2 * row * column + 2;
for(int i=0;i<n;i++){
graph[i].clear();
}
for(int i=0;i<c;i++){
scanf("%d%d",&y,&x);
x = row - x;
graph[source].push_front(pair<int,int> ((x*column + y)*2-1,1));
}
for(int i=0;i<row;i++){
for(int j=1;j<=column;j++){
graph[(i*row+j)*2-1].push_front(pair<int,int> ((i*column+j)*2,1));
if ( i > 0){
graph[(i*column+j)*2].push_front(pair<int,int> (((i-1)*column+(j))*2-1,1));
}
if ( i < row-1 ){
graph[(i*column+j)*2].push_front(pair<int,int> (((i+1)*column+(j))*2-1,1));
}
if ( j > 1){
graph[(i*column+j)*2].push_front(pair<int,int> (((i)*column+(j-1))*2-1,1));
}
if ( j < column ){
graph[(i*column+j)*2].push_front(pair<int,int> (((i)*column+(j+1))*2-1,1));
}
if(i == 0 || i == row - 1 || j == 1 || j == column){
graph[(i*column+j)*2].push_front(pair<int,int> (destination,1));
}
}
}
if(maxFlow() == c){
puts("possible");
}
else {
puts("not possible");
}
}
return 0;
}
People die young because god loves them so much, I am still on earth because there is a godess here who loves me even more.
I am a bit confused with the problem statement . Can a bank be robbed more than once ?? If a bank is being robbed for the second time , doest it men that the second robbers are crossing the first robbers' path ??
I am getting WA . I used backtracking to match the paths . I got correct answer for the 50 inputs given in this thread. Can anyone hep me with some more tricky input ??
I am getting WA . I used backtracking to match the paths . I got correct answer for the 50 inputs given in this thread. Can anyone hep me with some more tricky input ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh
CSE,BUET
Bangladesh
Is there anyone who can explain the algorithm for this problem ?? I think , I have to calculate repeatedly changing source and sink and then pick the smallest flow. but I am a bit confused how to construct the graph and how to select the source and the sink . Can anyone help me ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh
CSE,BUET
Bangladesh
Use two artificial nodes, source and sink. capacity of source to banks are all 1, and capacity of the corner points to sink are 1. Then run flow from source to sink. Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Thanks mf.
Now I am providing my max-flow values of ImLazy's inputs, Please verify these.
(I am not very good at maximum flow, If you want i can paste my code here)
Now I am providing my max-flow values of ImLazy's inputs, Please verify these.
Code: Select all
(flow: 12) not possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 12) not possible
(flow: 4) not possible
(flow: 11) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 9) not possible
(flow: 11) not possible
(flow: 15) not possible
(flow: 9) not possible
(flow: 13) not possible
(flow: 8) not possible
(flow: 6) possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 7) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 14) not possible
(flow: 11) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 9) not possible
(flow: 6) possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 14) not possible
(flow: 15) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 9) not possible
(flow: 3) not possible
(flow: 7) not possible
(flow: 13) not possible
(flow: 12) not possible
(flow: 3) possible
For this case my program found a flow of value 10, while your program says 9.
Code: Select all
1
5 5 13
4 5
1 5
3 3
1 3
4 2
3 1
4 2
4 4
1 4
2 3
1 3
4 5
2 4
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Thanks again mf,
After fixing some bug, i got these output for same input.
But I am still getting Wrong Answer. Are above outputs are correct?
After fixing some bug, i got these output for same input.
Code: Select all
(flow: 12) not possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 12) not possible
(flow: 4) not possible
(flow: 11) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 9) not possible
(flow: 11) not possible
(flow: 15) not possible
(flow: 9) not possible
(flow: 13) not possible
(flow: 8) not possible
(flow: 6) possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 7) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 14) not possible
(flow: 11) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 9) not possible
(flow: 6) possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 14) not possible
(flow: 15) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 10) not possible
(flow: 3) not possible
(flow: 7) not possible
(flow: 13) not possible
(flow: 12) not possible
(flow: 3) possible