563 - Crimewave

Moderator: Board moderators

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

563 (crimewave)

i think this is a network-flow problem.
but i got WA.
any tricky there?
[pascal]
const
maxn = 2 * 50 * 50 + 2;
md : array[1..4, 1..2]of shortint = ((0, -1), (0, 1), (1, 0), (-1, 0));
type
tnode = record
k : word;
f, c : integer;
end;
tway = record
p, d : integer;
end;
var
n, vs, vt : word;
way : array[1..maxn]of tway;
cases,count, ans, row, col : integer;

procedure insert(u, v, c : integer);
begin
new(x);
x^.k := v;
x^.f := 0;
x^.c := c;
x^.next := g;
g := x;
new(x^.back);
x^.back^.k := u;
x^.back^.f := 0;
x^.back^.c := 0;
x^.back^.back := x;
x^.back^.next := g[v];
g[v] := x^.back;
end;

procedure initialize;
var u, v : integer;
i, j, k : integer;
list : array[1..2500, 1..2]of integer;
begin
vs := 2 * row * col + 1;
vt := 2 * row * col + 2;
for u := 1 to 2 * row * col + 2 do g := nil;
for i := 1 to count do readln(list[i, 2], list[i, 1]);
for i := 1 to row do
for j := 1 to col do
begin
u := (i - 1) * col + j;
insert(u, u + row * col, 1);
for k := 1 to 4 do
if (i + md[k, 1] >= 1) and (i + md[k, 1] <= row) and
(j + md[k, 2] >= 1) and (j + md[k, 2] <= col) then
insert(row * col + u, u + md[k, 1] * col + md[k, 2], 1);
if (i = row) or (i = 1) or (j = col) or (j = 1) then
insert(row * col + u, vt, 1);
end;
for i := 1 to count do
insert(vs, (list[i, 1] - 1) * col + list[i, 2], 1);
n := vt;
end;

procedure flow;
var q : array[1..maxn]of word;
head, tail, i, a : integer;
begin
ans := 0;
repeat
fillchar(way, sizeof(way), 0);
way[vs].d := maxint;
way[vs].p := vs;
head := 0; tail := 1;
q[tail] := vs;
while (head < tail) and (way[vt].p = 0) do
begin
x := g;
while x <> nil do
begin
a := x^.c - x^.f;
if (way[x^.k].p = 0) and (a > 0) then
begin
inc(tail);
q[tail] := x^.k;
way[x^.k].p := i;
way[x^.k].w := x;
if way.d < a then way[x^.k].d := way.d else way[x^.k].d := a;
end;
x := x^.next;
end;
end;
if way[vt].p <> 0 then
begin
i := vt; a := way.d;
repeat
way.w^.f := way.w^.f + a;
way.w^.back^.f := -way.w^.f;
i := way.p;
until i = vs;
inc(ans);
end;
until way[vt].p = 0;
end;
{
procedure out;
var f : text;
ans, i : integer;
begin
assign(f, '563.log'); rewrite(f);
ans := 0;
for i := 1 to n do
begin
x := g;
while x <> nil do
begin
if x^.f > 0 then writeln(f, i, '->', x^.k, ': ', x^.f);
if (i = vs) and (x^.f > 0) then ans := ans + x^.f;
x := x^.next;
end;
end;
writeln(f, ans);
close(f);
end;
}
begin
while cases > 0 do
begin
dec(cases);
initialize;
flow;
if ans = count then
writeln('possible')
else
writeln('not possible');
{ out; }
end;
end.
[/pascal]

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

563 Crimewave

I got WA.
but I cannot find the wrong.

[c]
#include "stdio.h"
#include "stdlib.h"
#define MAX 50
#define MAXARRAY ( (MAX) * (MAX) * 2 + 2 )
struct BANK{
int x;
int y;
}bank[MAX*MAX];
struct EDGE{
int from;
int to;
int weight;
struct EDGE *next;
};
typedef struct EDGE connect;
typedef connect *edge;
edge map[MAXARRAY];
int row,col,nbank,source,sink,path[MAXARRAY];
{
return( (x*row+y)*2+1 );
}
int tailx(int x,int y)
{
}
{
edge newedge;
newedge=(edge)malloc(sizeof(connect));
newedge->from=from;
newedge->to=to;
newedge->weight=weight;
newedge->next=map[from];
map[from]=newedge;
}
{
edge ptr=map[from];
while(ptr){
if(ptr->to==to){
ptr->weight+=weight;
return;
}
ptr=ptr->next;
}
/*if there is no connection between these*/
}
void make_graph()
{
int i,j,k,x,y;
memset(map,0,sizeof(int)*MAXARRAY);
source=0;
sink=row*col*2+1;
for(i=0;i<row;i++)
for(j=0;j<col;j++)
for(i=1;i<row;i++)
for(j=0;j<col;j++){
}
for(i=0;i<row;i++)
for(j=1;j<col;j++){
}
for(i=0;i<nbank;i++)
for(i=0;i<row;i++){
}
for(j=1;j<col-1;j++){
}
}
int BFS()
{
int queue[MAXARRAY],parent[MAXARRAY],visited[MAXARRAY];
int front=0,tail=1,now,i,j;
edge ptr;
memset(visited,0,sizeof(int)*MAXARRAY);
queue[front]=source;
parent[front]=-1;
visited[source]=1;
while(front<tail){
now=queue[front];
for(ptr=map[now];ptr;ptr=ptr->next){
if(ptr->weight <=0 ) continue;
if(visited[ptr->to]) continue;
parent[tail]=front;
queue[tail]=ptr->to;
visited[ptr->to]=1;
if(ptr->to==sink) goto FIND_PATH;
tail++;
}
front++;
}
return 0;
FIND_PATH:
for(i=tail,j=-1;i>=0;i=parent)
path[++j]=queue;
return j;
}
void maxflow()
{
int flow=0,len,i;
while( (len=BFS())>0 ){
/*reverse*/
for(i=1;i<len;i++){
}
flow++;
}
if(flow==nbank) puts("possible");
else puts("not possible");
}
void main()
{
int N,i;
scanf("%d",&N);
for(;N;N--){
scanf("%d %d %d",&row,&col,&nbank);
for(i=0;i<nbank;i++){
scanf("%d %d",&bank.x,&bank.y);
bank.x--;
bank.y--;
}
make_graph();
maxflow();
}

}
[/c]

I need some test datas...thanks!

inteplus
New poster
Posts: 4
Joined: Fri Oct 26, 2001 2:00 am
Location: NTU Singapore
Contact:
Some criminals can rob the same bank.

inteplus
New poster
Posts: 4
Joined: Fri Oct 26, 2001 2:00 am
Location: NTU Singapore
Contact:
Robbers can rob the same bank

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe
I implemented an O(V*E^2) as well as an O(V^3) max-flow algorithm to solve this problem. However, I always got TLE!

Do I REALLY have to implement some fancy O(V^2/3*E) algortihm - or what did you use?

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

563 - Crimewave

I think there are at least 50 * 50 = 2500 vertices in the graph, and I need to calculate the max flow. But I only know Ford-Fulkerson algorithm whose running time is O(V^2*E) and Relabel-To-Front algorithm with O(V^3) running time. They must cause TLE. Is there any faster max-flow algorithm? Or how do you solve this problem?
Last edited by ImLazy on Fri Feb 10, 2006 9:58 am, edited 1 time in total.
I stay home. Don't call me out.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Max flow is a correct way to solve it.

But your bound on running time is waaay pessimistic!
If you use Ford-Fullkerson, in the worst case you'll need to find just 50*4 augmenting paths. 200 [BD]FS's on a graph of about 2500 vertices, 10000 edges isn't too much.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
50 * 4 paths? I don't quite understand. Thank you any way. I will try.
I stay home. Don't call me out.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
In order to escape, each of robbers' paths has to cross some point on the perimeter of the grid (that is, a point in 1st row, s-th row, 1st column or a-th column), but no two paths may cross the same point. On the largest grid (50x50), there are 50*2+48*2 = 196 such points, so there can't be more vertex-disjoint paths than that.

In each iteration of FF, you find an escape path for at least one bank, hence in worst case you'll need no more than 196 iterations (each iteration=one DFS or BFS.)

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Oh, I see. Sorry, I'm not familiar with max-flow algorithm.
Thank you very much.
But now I get WA. Can you check IO for me? This is the input data:

Code: Select all

``````50
5 5 17
3 5
1 5
5 4
4 3
5 1
1 2
3 2
2 1
3 3
2 2
5 3
4 3
3 2
2 4
1 3
2 2
4 5
5 5 13
3 5
1 5
4 2
3 4
4 5
2 2
4 4
3 5
3 3
3 5
4 2
5 4
2 1
5 5 16
3 4
2 1
3 5
4 2
1 1
5 1
1 2
2 4
4 5
4 5
5 2
1 2
2 2
4 5
5 2
4 3
5 5 14
4 3
5 2
4 1
5 4
5 1
3 2
4 2
2 1
5 3
1 5
3 4
3 3
2 1
2 2
5 5 6
3 1
5 2
3 1
1 2
5 2
1 3
5 5 17
3 3
3 3
4 4
1 5
5 4
2 4
3 2
2 1
4 4
1 2
3 1
1 5
5 3
4 4
1 2
3 1
2 2
5 5 25
1 2
2 4
5 4
5 2
5 4
5 4
4 1
4 3
3 4
4 4
4 3
2 1
3 4
5 5
2 1
2 1
5 5
2 4
4 5
4 5
5 5
3 1
1 4
4 4
3 5
5 5 4
4 1
4 4
1 2
4 2
5 5 15
4 5
3 3
3 4
3 4
5 1
3 4
2 1
4 2
2 3
5 3
1 4
2 3
2 1
4 5
3 5
5 5 17
2 4
3 2
2 5
3 2
3 5
1 3
1 1
4 5
2 4
2 5
1 4
3 1
3 1
4 2
3 3
3 3
5 5
5 5 22
5 2
5 4
3 1
1 5
5 2
3 1
1 4
4 5
4 5
2 3
5 5
3 2
5 4
1 3
2 2
1 4
3 1
5 5
2 2
2 2
4 4
1 1
5 5 4
3 4
3 1
4 2
2 4
5 5 22
3 2
5 2
3 5
2 1
1 4
2 5
5 3
5 4
5 5
1 1
5 2
4 5
3 4
4 3
1 4
2 3
1 3
5 5
5 5
5 3
5 4
1 3
5 5 23
4 3
4 1
4 4
3 1
3 1
4 3
3 5
3 1
4 5
4 3
2 2
4 3
1 4
1 2
3 3
3 2
5 1
3 1
4 5
1 1
1 4
2 1
2 3
5 5 11
1 1
5 1
5 5
1 2
5 4
3 2
2 4
4 2
5 4
5 5
3 1
5 5 13
1 2
1 3
1 1
2 3
4 4
5 5
3 2
1 3
3 5
1 3
5 4
4 1
3 3
5 5 24
2 3
2 1
1 5
1 3
2 1
2 2
2 2
3 4
1 1
5 4
4 1
2 3
5 1
4 4
4 1
3 3
1 4
5 4
1 3
5 3
4 4
3 2
1 1
4 4
5 5 10
1 1
2 5
1 2
3 1
4 1
2 2
2 3
2 3
3 2
5 2
5 5 22
3 3
3 3
2 1
2 4
5 5
1 5
3 2
1 4
3 5
5 5
3 3
5 3
4 3
4 2
1 3
4 1
4 4
3 5
2 2
1 5
1 2
1 2
5 5 10
1 4
1 4
5 2
4 5
3 5
2 4
2 1
3 4
2 1
4 2
5 5 6
1 3
3 2
3 5
4 3
4 2
4 1
5 5 14
1 3
4 1
3 3
3 1
5 2
1 4
1 1
3 5
1 1
4 5
2 1
5 4
1 5
3 1
5 5 15
2 4
5 1
4 3
3 5
2 2
3 3
2 5
1 4
5 2
3 1
4 4
3 5
2 3
5 1
4 3
5 5 10
1 2
4 1
3 3
5 4
2 4
2 4
1 2
5 1
5 3
5 4
5 5 17
5 4
3 1
1 1
5 4
3 4
3 5
4 2
5 4
1 1
3 2
4 5
3 5
1 5
5 1
1 1
4 4
1 2
5 5 24
3 3
3 3
1 4
2 4
4 3
1 5
1 1
4 4
3 4
4 3
5 4
5 2
4 3
4 1
2 4
5 4
2 1
5 4
1 1
4 3
2 4
1 2
1 4
4 5
5 5 25
4 4
5 3
2 5
1 4
2 2
1 1
2 5
2 5
1 5
3 1
4 3
2 4
3 2
2 4
5 5
1 2
3 1
4 1
2 2
2 5
5 2
3 2
4 3
1 1
2 1
5 5 17
1 2
3 2
1 1
3 5
4 4
2 3
4 3
4 5
4 5
4 2
4 5
3 4
5 4
1 1
4 4
1 1
2 5
5 5 4
2 4
5 3
2 5
4 3
5 5 4
5 1
3 4
2 5
4 5
5 5 9
5 2
4 1
2 5
3 1
4 4
5 3
4 3
1 2
5 4
5 5 12
5 4
1 5
3 5
4 1
2 5
3 1
1 1
1 5
3 4
3 5
1 1
5 5
5 5 6
1 2
2 1
5 1
4 4
4 3
3 2
5 5 15
4 4
2 1
4 4
4 5
4 1
2 1
5 2
4 3
4 1
4 1
2 5
1 4
5 4
2 1
2 5
5 5 18
4 5
5 2
1 2
2 2
2 2
3 2
5 1
2 2
3 2
5 5
1 3
4 5
2 1
3 4
2 2
4 4
3 3
3 2
5 5 13
2 1
5 5
5 2
1 4
2 3
5 1
4 4
2 3
2 5
5 4
3 5
1 3
5 5
5 5 14
4 4
2 5
4 2
2 3
4 4
3 2
3 3
1 3
4 3
3 4
1 3
1 4
5 3
4 3
5 5 16
1 1
3 3
2 3
4 3
4 2
2 1
5 1
4 5
1 1
1 3
3 1
1 3
2 5
4 2
5 2
4 5
5 5 14
4 1
1 2
1 1
4 5
1 1
5 3
3 2
5 5
5 1
4 1
4 1
1 3
2 3
4 4
5 5 12
5 5
2 5
1 1
3 5
3 4
5 1
4 4
2 1
3 4
3 5
2 2
2 3
5 5 25
1 5
5 4
2 2
5 5
1 1
1 2
1 1
5 5
2 4
5 5
1 1
4 5
2 3
4 4
2 4
2 1
3 5
5 1
3 3
2 1
5 5
5 3
1 1
5 3
2 3
5 5 23
3 5
1 1
5 1
4 5
2 3
3 5
4 3
3 3
4 1
4 4
5 5
5 2
5 4
1 2
2 1
3 3
3 3
2 5
3 2
4 3
2 2
4 4
4 3
5 5 19
2 1
2 3
2 1
1 5
2 3
5 4
5 3
4 4
2 2
4 4
3 2
2 3
3 4
3 4
1 4
1 4
3 4
4 2
1 4
5 5 12
1 5
3 5
5 2
1 3
4 4
5 3
3 1
2 3
3 3
1 3
5 2
1 4
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
5 5 4
3 1
4 2
3 1
5 4
5 5 9
2 4
2 3
4 5
1 1
1 2
2 4
1 1
4 4
3 4
5 5 16
2 1
1 5
3 3
3 4
3 5
5 5
4 3
3 3
1 4
5 3
4 5
1 2
5 1
3 4
4 2
5 4
5 5 17
1 5
1 3
5 1
4 2
5 1
3 5
1 4
4 3
4 3
2 1
5 1
3 1
5 1
1 2
3 1
5 4
5 2
5 5 3
4 4
1 3
2 2``````
And my output is here: (I also print my answer of max-flow, is it the same as yous?)

Code: Select all

``````(flow: 12) not possible
(flow: 12) not possible
(flow: 14) not possible
(flow: 13) not possible
(flow: 6) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 16) not possible
(flow: 4) possible
(flow: 16) not possible
(flow: 16) not possible
(flow: 11) possible
(flow: 12) not possible
(flow: 16) not possible
(flow: 10) possible
(flow: 15) not possible
(flow: 10) possible
(flow: 6) possible
(flow: 14) possible
(flow: 12) not possible
(flow: 10) possible
(flow: 15) not possible
(flow: 15) not possible
(flow: 14) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 12) possible
(flow: 6) possible
(flow: 14) not possible
(flow: 13) not possible
(flow: 13) possible
(flow: 11) not possible
(flow: 14) not possible
(flow: 14) possible
(flow: 12) possible
(flow: 16) not possible
(flow: 15) not possible
(flow: 13) not possible
(flow: 12) possible
(flow: 13) possible
(flow: 4) possible
(flow: 9) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 3) possible``````
I stay home. Don't call me out.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Some of your test cases are not valid (quote: "although there are never two banks at the same crossing")

Anyway, here's my output:

Code: Select all

``````not possible
not possible
not possible
not possible
not possible
not possible
not possible
possible
not possible
not possible
not possible
possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
possible
possible
possible
not possible
possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
not possible
possible
``````
How do you deal with the requirement, that the paths must not intersect? (or, how do you construct your graph?)

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
I think a bank may be robbed more than Once.
I construct the network in this way:
1. I divide each vertex into two vertexes, the entry and the exit. There is an edge from entry to exit whose capacity is 1;
2. each vertex u is linked to its four adjacent vertexes in the grid. (Four edges from exit(u) to entry(adj), capacity is 1).
3. Exits of vertexes on the boundary of the grid are linked to the sink, capacity is 1;
4. If a vertex is robbed n times, then there is an edge from source to its exit with capacity of n;

Even though there no repeating bank robbings, I think it doesn't influent my answer.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Oh, I see. If one bank is robbed more than once the answer is obviously "not possible". Now I get AC . Thank you very much.
I stay home. Don't call me out.

Landertxu
New poster
Posts: 4
Joined: Tue Feb 14, 2006 9:39 pm
I have RE. My code can read 5000 inputs, citys of 50x50, and 2500 banks. Every tests are OK.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

563 (CRIMEWAVE) whats the time limit?

Whats the time limit of the problem
As I know 10 seconds for every problems

But there are some people who got Accepted over 10 seconds

http://acm.uva.es/cgi-bin/OnlineJudge?P ... 5:175:1.00

check here

But I am getting TLE for being over 10.