563 - Crimewave

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

Moderator: Board moderators

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

563 (crimewave)

Post by lowai » Tue Nov 12, 2002 2:28 pm

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

procedure insert(u, v, c : integer);
var x : tlink;
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
readln(row, col, count);
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;
x : tlink;
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
inc(head);
i := q[head];
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;
x : tlink;
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
readln(cases);
while cases > 0 do
begin
dec(cases);
initialize;
flow;
if ans = count then
writeln('possible')
else
writeln('not possible');
{ out; }
end;
end.
[/pascal]

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

563 Crimewave

Post by hank » Sat Jan 04, 2003 2:10 pm

I got WA.
but I cannot find the wrong.
please help me...^_*
:oops: :oops:
[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];
int headx(int x,int y)
{
return( (x*row+y)*2+1 );
}
int tailx(int x,int y)
{
return(headx(x,y)+1);
}
void addedge(int from,int to,int weight)
{
edge newedge;
newedge=(edge)malloc(sizeof(connect));
newedge->from=from;
newedge->to=to;
newedge->weight=weight;
newedge->next=map[from];
map[from]=newedge;
}
void addweight(int from,int to,int weight)
{
edge ptr=map[from];
while(ptr){
if(ptr->to==to){
ptr->weight+=weight;
return;
}
ptr=ptr->next;
}
/*if there is no connection between these*/
addedge(from,to,weight);
}
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++)
addedge(headx(i,j),tailx(i,j),1);
for(i=1;i<row;i++)
for(j=0;j<col;j++){
addedge(tailx(i-1,j),headx(i,j),1);
addedge(tailx(i,j),headx(i-1,j),1);
}
for(i=0;i<row;i++)
for(j=1;j<col;j++){
addedge(tailx(i,j-1),headx(i,j),1);
addedge(tailx(i,j),headx(i,j-1),1);
}
for(i=0;i<nbank;i++)
addedge(source,headx(bank.x,bank.y),1);
for(i=0;i<row;i++){
addedge(tailx(i,0),sink,1);
addedge(tailx(i,col-1),sink,1);
}
for(j=1;j<col-1;j++){
addedge(tailx(0,j),sink,1);
addedge(tailx(row-1,j),sink,1);
}
}
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++){
addweight(path,path[i-1],-1);
addweight(path[i-1],path,1);
}
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! :o :oops:

inteplus
New poster
Posts: 4
Joined: Fri Oct 26, 2001 2:00 am
Location: NTU Singapore
Contact:

Post by inteplus » Sun Jan 05, 2003 5:07 pm

Some criminals can rob the same bank.

inteplus
New poster
Posts: 4
Joined: Fri Oct 26, 2001 2:00 am
Location: NTU Singapore
Contact:

Post by inteplus » Sun Jan 05, 2003 5:09 pm

Robbers can rob the same bank

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

Post by Tobbi » Sun Oct 24, 2004 10:37 am

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? :-?

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

563 - Crimewave

Post by ImLazy » Thu Feb 09, 2006 6:00 am

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:

Post by mf » Thu Feb 09, 2006 6:27 am

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.

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

Post by ImLazy » Thu Feb 09, 2006 8:43 am

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:

Post by mf » Thu Feb 09, 2006 9:04 am

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.)

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

Post by ImLazy » Fri Feb 10, 2006 9:52 am

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:

Post by mf » Fri Feb 10, 2006 12:06 pm

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?)

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

Post by ImLazy » Fri Feb 10, 2006 5:11 pm

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.

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

Post by ImLazy » Fri Feb 10, 2006 5:33 pm

Oh, I see. If one bank is robbed more than once the answer is obviously "not possible". Now I get AC :lol: . 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

Post by Landertxu » Sun Feb 19, 2006 4:51 pm

I have RE. My code can read 5000 inputs, citys of 50x50, and 2500 banks. Every tests are OK.

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

563 (CRIMEWAVE) whats the time limit?

Post by emotional blind » Fri Jun 23, 2006 6:03 pm

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 :evil:

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

check here

But I am getting TLE for being over 10. :cry:

Post Reply

Return to “Volume 5 (500-599)”