## 563 - Crimewave

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
It isn't easy for me to modify my program to print flow value for all tests. (It has some optimizations, and I'm afraid I could break things if I try to patch it now.)
Better you just post your code.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Thanks. Here is my code. I guess it will be understandable for you. otherwise ask me, I will try my best to describe my algorithm.

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define S 60
enum {LEFT=0,RIGHT,UP,DOWN, VER};
int move[5][2]={	{0,-1},{0,1},{-1,0},{1,0},{0,0} };
int rev[5]={RIGHT,LEFT,DOWN,UP,VER};
bool fnet[S][S][5], vis[S][S][2];
int pre[S][S][2], s, a;

bool in(int x, int y){
return (x>=1 && x<=s && y>=1 && y<=a);
}

bool bfs(int x, int y){
queue<int> Q;
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
int u1, v1, w1;
Q.push(x);
Q.push(y);
Q.push(0);
vis[x][y][0]=true;

while(!Q.empty()){
int u=Q.front();Q.pop();
int v=Q.front();Q.pop();
int w=Q.front();Q.pop();

if(w==1 && (u==1 || u==s || v==1 || v==a) ){
while(pre[u][v][w]!=-1){
int pr = pre[u][v][w];
if(w==1)fnet[u][v][pr]=(pr==4);
else fnet[u+ move[pr][0]][v + move[pr][1]][rev[pr]]=(pr!=4);

u = u + move[pr][0];
v = v + move[pr][1];
w = 1 - w;
}
return true;
}

for(int i=0;i<5;++i){
u1 = u + move[i][0];
v1 = v + move[i][1];
w1 = 1 - w;

if( in(u1,v1) && vis[u1][v1][w1]==false ){
if( (w==0 && fnet[u1][v1][rev[i]]==(i<4) ) || (w==1 && fnet[u][v][i]==(i==4) ) ){
Q.push(u1);
Q.push(v1);
Q.push(w1);
vis[u1][v1][w1]=true;
pre[u1][v1][w1]=rev[i];
}
}
}
}
return false;
}

int main (void){
int T, b;
int i, j, k;
int x[S], y[S];
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&s,&a,&b);
for(i=0;i<b;++i)
scanf("%d%d",&x[i],&y[i]);

memset( fnet, 0, sizeof( fnet ) );

for(i=0;i<b;++i){
for(j=0;j<b;++j)
if(bfs(x[j],y[j])==true)
break;
if(j==b)break;
}

//printf("(flow: %d) ",i);
if(i<b)printf("not possible\n");
else printf("possible\n");
}
return 0;
}``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I think that your graph can be wrong.

There should be just these edges (each of capacity 1):
(x,y,0) -> (x,y,1)
(x,y,1) -> (x',y',0), for all 4 grid points (x',y') adjacent to (x,y)

There shouldn't be allowed any moves from (x,y,0) to (x',y',1), except when (x',y') = (x,y).

And another thing, I think that it'll be a lot easier to debug max flow code, if you explicitly build the graph in this problem.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
If first flow contains edge from (x,y,1) to (x',y',0), where (x,y) != (x',y'),
I think it is possible to flow containing edge (x',y',0) to (x,y,1) in next unit flow.
----------- that is how I understand. isnt it?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try to explicitly create the graph and all its edges, and write a max-flow algorithm to work on this explicit graph. It will be a lot simpler for both of us to debug and see what's going on in such a graph.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: some question

can somebody help with "a bank rodded more than one time"?
int my code

if(grid[j].b>1)duplicate = true;

and if duplicate is true, should i always print no possible?

but i try som case
2
3 3 2
3 1
3 1
3 4 2
3 1
3 1
my friend's AC answer give no possible, possible ! why?
in case two, 3 1 is duplicate (robbed than one time )

can somebody help me plz
electron

faximan
New poster
Posts: 1
Joined: Wed Sep 15, 2010 1:19 am

### Re: 563 - Crimewave

I have written a solution that works with all inputs given earlier in this thread.
It uses Ford-Fulkeson with BFS.

However, I get TLE and I've been trying to speed up my code for many hours now, but no success.
Please can someone point me in a direction to go? I want to solve this bloody problem!

Code in Java, but tried the same in c++ as well.

Code: Select all

``````import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

static int szx, szy, nbrBanks, nbrNodes, source, sink;
static int[][] capacity;
static int[] banks, parent;
static boolean seen[];
static Queue<Integer> q;

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int nbrTests = scanner.nextInt();
for (int i = 0; i < nbrTests; i++) {

szx = scanner.nextInt();
szy = scanner.nextInt();
nbrBanks = scanner.nextInt();

nbrNodes = szx * szy * 2 + 2;
source = 0;
sink = nbrNodes - 1;

banks = new int[nbrNodes];
seen = new boolean[nbrNodes];
parent = new int[nbrNodes];
capacity = new int[nbrNodes][nbrNodes];

for (int j = 0; j < nbrBanks; j++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
int index = getIndex(x, y, true);
banks[index] = 1;
capacity[0][index] = 1;
}

buildGraph();

if (maxFlow() == nbrBanks)
System.out.println("possible");
else
System.out.println("not possible");
}
}

private static int maxFlow() {

int maxFlow = 0;
while (findAugmentingPath()) {
maxFlow++;
}
return maxFlow;
}

private static boolean findAugmentingPath() {
for (int i = 0; i < nbrNodes; i++) {
seen[i] = false;
parent[i] = -1;
}

seen[source] = true;

while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i <= sink; i++) {
if (!seen[i] && capacity[cur][i] > 0) {
seen[i] = true;
parent[i] = cur;
if (i == sink)
return true;
}
}
}
return false;

}

int cur = sink;
int prev = parent[sink];
while (prev != -1) {
capacity[prev][cur]--;
capacity[cur][prev]++;
cur = prev;
prev = parent[cur];
}

}

private static void buildGraph() {
for (int i = 1; i <= szx * 2; i++)
for (int j = 1; j <= szy; j++) {
connectNode(i, j);
}
}

private static void connectNode(int x, int y) {
if (x > szx) {
capacity[getIndex(x, y, false)][getIndex(x - szx, y, false)] = 1;
} else {
if (x == 1 || y == 1 || x == szx || y == szy)
capacity[getIndex(x, y, false)][nbrNodes - 1] = 1;
if (x > 1)
capacity[getIndex(x, y, false)][getIndex(x - 1, y, true)] = 1;
if (x < szx)
capacity[getIndex(x, y, false)][getIndex(x + 1, y, true)] = 1;
if (y > 1)
capacity[getIndex(x, y, false)][getIndex(x, y - 1, true)] = 1;
if (y < szy)
capacity[getIndex(x, y, false)][getIndex(x, y + 1, true)] = 1;
}
}

public static int getIndex(int x, int y, boolean entry) {
if (entry)
return szx * szy + (y - 1) * szx + x;
else if (x > szx)
return szx * szy + (y - 1) * szx + (x - szx);
else
return (y - 1) * szx + x;
}
}
``````

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 563 - Crimewave

I don't know whether you got accepted it..However you could reduce number of iterations in following portion.
You don't need to look over all the node's possible to find adjacent of current node rather you should look up only four node up,
down,left ,right of current node..this should avoid TLE...

Code: Select all

``````         for (int i = 0; i <= sink; i++) {
if (!seen[i] && capacity[cur][i] > 0) {
seen[i] = true;
parent[i] = cur;
if (i == sink)
return true;
}

``````

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 563 - Crimewave

Who are getting WA should be aware of this case

Code: Select all

``````2
1 1 1
1 1
5 5 2
2 3
2 3
``````
Output :

Code: Select all

``````possible
not possible
``````

ackoroa
New poster
Posts: 4
Joined: Mon Mar 18, 2013 8:27 am

### Re: 563 - Crimewave

I also have a code which solves the sample inputs above but am still getting WA Can somebody help see what might be the problem?

Code: Select all

``````AC
``````
Last edited by ackoroa on Tue Apr 16, 2013 6:23 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 563 - Crimewave

Input:

Code: Select all

``````10
6 11 28
1 1
1 3
1 4
1 5
1 7
1 9
1 10
1 11
2 1
2 7
2 10
2 11
3 5
3 6
3 9
3 10
4 1
4 4
4 5
4 9
5 5
5 8
5 11
6 4
6 7
6 8
6 9
6 11
16 20 158
1 2
1 5
1 8
1 10
1 11
1 13
1 15
1 16
1 19
1 20
2 1
2 2
2 3
2 4
2 6
2 10
2 11
2 12
2 13
2 14
2 15
2 17
2 19
3 1
3 6
3 8
3 9
3 10
3 14
3 20
4 4
4 5
4 6
4 7
4 8
4 9
4 11
4 14
4 15
4 16
4 18
4 20
5 4
5 5
5 7
5 11
5 14
5 15
5 16
6 2
6 4
6 6
6 12
6 16
6 18
6 19
7 1
7 3
7 4
7 5
7 7
7 9
7 10
7 12
7 13
7 16
8 3
8 6
8 9
8 10
8 14
8 16
8 18
8 19
8 20
9 2
9 4
9 6
9 7
9 9
9 10
9 13
9 16
9 17
9 19
10 2
10 3
10 5
10 6
10 7
10 8
10 10
10 17
10 18
10 20
11 2
11 3
11 4
11 5
11 6
11 10
11 11
11 16
11 17
11 18
11 20
12 3
12 4
12 5
12 6
12 7
12 11
12 13
12 15
12 18
13 2
13 4
13 5
13 9
13 10
13 11
13 13
13 14
13 15
13 19
13 20
14 3
14 4
14 5
14 6
14 7
14 8
14 11
14 12
14 13
14 14
14 16
14 17
14 19
15 1
15 2
15 4
15 6
15 7
15 11
15 13
15 14
15 18
15 19
16 1
16 3
16 4
16 5
16 6
16 10
16 12
16 14
16 19
1 11 6
1 1
1 2
1 3
1 4
1 5
1 6
12 10 72
1 1
1 2
1 3
1 4
1 5
1 9
1 10
2 1
2 2
2 3
2 4
2 7
2 8
2 9
2 10
3 6
3 9
3 10
4 1
4 2
4 6
4 7
5 1
5 2
5 3
5 4
5 7
5 8
5 9
6 2
6 4
6 5
6 8
6 9
6 10
7 1
7 4
7 5
7 6
7 7
7 9
7 10
8 2
8 4
8 7
8 8
8 9
9 1
9 4
9 5
9 6
9 7
9 8
9 9
10 3
10 4
10 5
10 10
11 1
11 4
11 5
11 7
11 8
11 9
11 10
12 1
12 3
12 4
12 5
12 7
12 8
12 9
8 14 53
1 4
1 10
1 13
2 1
2 3
2 5
2 7
2 12
2 13
2 14
3 1
3 2
3 3
3 4
3 5
3 6
3 14
4 2
4 3
4 4
4 5
4 8
4 10
4 11
4 13
5 1
5 2
5 3
5 7
5 8
5 11
6 3
6 5
6 8
6 13
6 14
7 1
7 3
7 5
7 6
7 7
7 8
7 9
7 11
7 12
8 1
8 2
8 4
8 5
8 6
8 8
8 9
8 12
17 16 135
1 1
1 2
1 3
1 4
1 5
1 6
1 10
1 11
1 12
1 13
1 14
2 7
2 8
2 10
2 11
2 13
2 14
2 15
3 3
3 4
3 5
3 6
3 9
3 10
3 11
3 14
3 16
4 3
4 7
4 9
4 13
4 14
4 16
5 3
5 4
5 5
5 6
5 7
5 10
5 14
5 15
6 1
6 8
6 10
6 11
6 15
7 4
7 5
7 6
7 8
7 12
7 13
7 14
7 15
7 16
8 3
8 6
8 10
8 12
8 13
8 15
8 16
9 2
9 3
9 5
9 6
9 7
9 8
9 9
9 10
9 12
9 13
9 16
10 2
10 3
10 6
10 8
10 9
10 10
10 13
10 14
10 16
11 1
11 2
11 3
11 6
11 7
11 8
11 12
12 1
12 5
12 7
12 9
12 10
12 11
12 14
12 16
13 2
13 3
13 6
13 7
13 8
13 9
13 12
13 14
13 15
14 1
14 2
14 5
14 6
14 7
14 8
14 11
14 13
14 14
14 16
15 1
15 2
15 3
15 4
15 8
15 10
15 12
15 14
15 15
15 16
16 2
16 3
16 7
16 12
16 16
17 2
17 6
17 11
17 15
10 13 64
1 2
1 3
1 4
1 5
1 6
1 9
1 12
1 13
2 2
2 3
2 4
2 5
2 7
2 8
2 10
2 11
2 13
3 1
3 2
3 4
3 8
4 1
4 4
4 5
4 6
4 10
4 11
4 12
5 1
5 3
5 6
5 7
5 10
6 3
6 8
6 9
6 10
6 12
7 3
7 4
7 5
7 7
7 10
7 11
7 13
8 1
8 2
8 8
8 9
8 10
8 11
8 12
9 1
9 2
9 5
9 7
9 9
10 1
10 4
10 5
10 6
10 8
10 9
10 13
6 8 24
1 1
1 3
1 5
1 6
2 1
2 2
2 5
2 6
3 4
3 6
3 7
3 8
4 1
4 3
4 4
4 5
5 1
5 2
5 6
5 7
5 8
6 2
6 3
6 6
11 1 8
1 1
3 1
4 1
5 1
7 1
8 1
9 1
11 1
8 8 34
1 3
1 4
1 8
2 1
2 2
2 4
2 7
3 2
3 6
3 7
3 8
4 7
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 7
6 8
7 1
7 2
7 3
7 7
8 1
8 2
8 3
8 4
8 5
8 7
``````
AC output:

Code: Select all

``````not possible
not possible
possible
not possible
not possible
not possible
not possible
not possible
possible
not possible
``````
Check input and AC output for thousands of problems on uDebug!

ackoroa
New poster
Posts: 4
Joined: Mon Mar 18, 2013 8:27 am

### Re: 563 - Crimewave

I found that I mixed up one of the widths/heights in one of the formulas. Thanks so much!

int2char
New poster
Posts: 1
Joined: Fri Jan 29, 2016 9:51 am

### Re: 563 - Crimewave

I saw someone solved it in 0.000 seconds,I use the Edmonds-Karp algorithm，but it takes 0.3 seconds. anyone know how to save time？