563 - Crimewave

[mf]

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]

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]

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]

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]

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]

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

[faximan]

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++;
			adjustCapacity();
		}
		return maxFlow;
	}

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

		q = new LinkedList<Integer>();
		q.add(source);
		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;
					q.add(i);
				}
			}
		}
		return false;

	}

	private static void adjustCapacity() {
		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]

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;
               q.add(i);
            }

[@li_kuet]

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]

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

[brianfry713]

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

[ackoroa]

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

[int2char]

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？