Page 1 of 3
563 (crimewave)
Posted: Tue Nov 12, 2002 2:28 pm
by lowai
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]
563 Crimewave
Posted: Sat Jan 04, 2003 2:10 pm
by hank
I got WA.
but I cannot find the wrong.
please help me...^_*
[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! 
Posted: Sun Jan 05, 2003 5:07 pm
by inteplus
Some criminals can rob the same bank.
Posted: Sun Jan 05, 2003 5:09 pm
by inteplus
Robbers can rob the same bank
Posted: Sun Oct 24, 2004 10:37 am
by Tobbi
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?
563 - Crimewave
Posted: Thu Feb 09, 2006 6:00 am
by ImLazy
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?
Posted: Thu Feb 09, 2006 6:27 am
by mf
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.
Posted: Thu Feb 09, 2006 8:43 am
by ImLazy
50 * 4 paths? I don't quite understand. Thank you any way. I will try.
Posted: Thu Feb 09, 2006 9:04 am
by mf
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.)
Posted: Fri Feb 10, 2006 9:52 am
by ImLazy
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
Posted: Fri Feb 10, 2006 12:06 pm
by mf
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?)
Posted: Fri Feb 10, 2006 5:11 pm
by ImLazy
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.
Posted: Fri Feb 10, 2006 5:33 pm
by ImLazy
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.
Posted: Sun Feb 19, 2006 4:51 pm
by Landertxu
I have RE. My code can read 5000 inputs, citys of 50x50, and 2500 banks. Every tests are OK.
563 (CRIMEWAVE) whats the time limit?
Posted: Fri Jun 23, 2006 6:03 pm
by emotional blind
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.
