563 - Crimewave

[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]

[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!

[inteplus]

Some criminals can rob the same bank.

[inteplus]

Robbers can rob the same bank

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

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

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

[ImLazy]

50 * 4 paths? I don't quite understand. Thank you any way. I will try.

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

[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

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

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

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

[Landertxu]

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

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