563 - Crimewave
Moderator: Board moderators
563 (crimewave)
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]
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
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!
![:oops:](./images/smilies/icon_redface.gif)
but I cannot find the wrong.
please help me...^_*
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
[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](./images/smilies/icon_eek.gif)
![:oops:](./images/smilies/icon_redface.gif)
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.
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.)
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.)
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:
And my output is here: (I also print my answer of max-flow, is it the same as yous?)
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
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.
Some of your test cases are not valid (quote: "although there are never two banks at the same crossing")
Anyway, here's my output:
How do you deal with the requirement, that the paths must not intersect? (or, how do you construct your graph?)
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
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 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.
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- 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.![:cry:](./images/smilies/icon_cry.gif)
As I know 10 seconds for every problems
But there are some people who got Accepted over 10 seconds
![:evil:](./images/smilies/icon_evil.gif)
http://acm.uva.es/cgi-bin/OnlineJudge?P ... 5:175:1.00
check here
But I am getting TLE for being over 10.
![:cry:](./images/smilies/icon_cry.gif)