11380 - Down Went The Titanic

[smilitude]

I made the same mistake, and even some more! I should have been more careful while building the graph. X(
Here are some IOs.

Code: Select all

4 5 1
*#*~.
.@*##
**#.#
.#~#~

13 3 1
.*@
#.#
.##
#.#
*@~
#.@
@**
@#*
@.*
~@@
#~#
.#*
*.@

6 5 1
@@~~*
..*.@
~#@#.
##~~@
##*@*
@*@#*

5 7 2
@.*~~.@
*@~@~~.
@@.@@##
*~@@@#@
..~~~##

6 3 2
*.~
*..
~@.
##.
#@#
@@#

Output

Code: Select all

4
8
6
1
1

[Shafaet_du]

Code: Select all

2 4 1
**##
@@@~

ans:2

i got stuck for this little case for hours

[nbacool2]

Hi. So I constructed a graph with the standard vertex splitting technique and super source/sink. Then I made an implementation of Edmond-Karp's algorithm with O(V^3*E) I guess since I'm using a matrix for the residual graph. The problem is I keep getting TLEs and don't really know how to make the code any faster. Could the Ford-Fulkerson actually perform better in this problem?
Here's the code:

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <utility>
#include <cmath>
#include <sstream>
#include <ctime>
using namespace std;
typedef pair<int, int> ii;
const int MAXR = 32;
const int MAXN = 2*MAXR*MAXR;
const int SOURCE = 2045;
const int SINK = 2046;
int X, Y, P;
char matrix[MAXR][MAXR];
int resG[MAXN][MAXN];
vector<int> answers;

int flow;
int parent[MAXN];
bool visited[MAXN];
void augment(int node, int minEdge)
{
    if(node == SOURCE)
    {
        flow = minEdge;
        return;
    }
    if(parent[node] == -1) return;
    augment(parent[node], min(minEdge, resG[parent[node]][node]));
    resG[parent[node]][node] -= flow;
    resG[node][parent[node]] += flow;
}
void BFS()
{
    memset(parent, -1, sizeof parent);
    memset(visited, 0, sizeof visited);
    queue<int> Q;
    Q.push(SOURCE);
    while(!Q.empty())
    {
        int node = Q.front(); Q.pop();
        for(int i = 0; i < MAXN; ++i)
        {
            int child = i;
            if(resG[node][child] > 0 && !visited[child])
            {
                visited[child] = true;
                parent[child] = node;
                Q.push(child);
                if(child == SINK) break;
            }
        }
    }
}
vector<ii> getAdjacent(int x, int y)
{
    vector<ii> adj;
    if(x + 1 < X) adj.push_back(ii(x+1, y));
    if(x - 1 >= 0) adj.push_back(ii(x-1, y));
    if(y + 1 < Y) adj.push_back(ii(x, y+1));
    if(y - 1 >= 0) adj.push_back(ii(x, y-1));
    return adj;
}
void read()
{
    memset(resG, 0, sizeof resG);
    cin >> Y >> P;
    for(int i = 0; i < X; ++i)
    {
        for(int j = 0; j < Y; ++j)
        {
            cin >> matrix[i][j];
        }
    }
    //construct the graph
    for(int i = 0; i < X; ++i)
    {
        for(int j = 0; j < Y; ++j)
        {
            int node = 2*(i*Y + j);
            if(matrix[i][j] == '~') continue;
            //adding a vertex to the split node
            int capacity = 1;
            if(matrix[i][j] == '@' || matrix[i][j] == '#') capacity = 10000;
            resG[node][node+1] = capacity;
            //added the vertex
            vector<ii> neighbours = getAdjacent(i, j);
            for(int k = 0; k < neighbours.size(); ++k)
            {
                int x = neighbours[k].first;
                int y = neighbours[k].second;
                if(matrix[x][y] == '~') continue;
                resG[node+1][2*(x*Y + y)] = 10000;
            }
            //now try to connect the vertext to the SuperSource/SuperSink
            if(matrix[i][j] == '*')
            {
                resG[SOURCE][node] = 1;
            }
            else if(matrix[i][j] == '#')
            {
                resG[node+1][SINK] = P;
            }
        }
    }
    //graph constructed
    int maxFlow = 0;
    while(true)
    {
        flow = 0;
        BFS();
        augment(SINK, 1000000);
        if(flow == 0) break;
        maxFlow += flow;
    }
    answers.push_back(maxFlow);
}
int main()
{
    int start = clock();
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while(cin >> X && X != 0)
    {
        read();
    }
    for(int i = 0; i < answers.size(); ++i)
    {
        cout<<answers[i]<<endl;
    }
    int end = clock() - start;
    cout<<"time: "<<(float) end / CLOCKS_PER_SEC<<endl;
    return 0;
}

Sample Input:

Code: Select all

3 4 2
*~~#
...@
.~.*

3 5 1
~~*~~
#.@.#
~~*~~

1 4 2
**#~

30 30 22
~~*~~~~*~**~*~~~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~*~~*~~~~**~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~**~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~**~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~#~*~~~~*~~~~*~~~~*~~~~*~~
#.@.#*.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~**~*~~~~*~~~~*~~
~~*~~~~*~~~~***~~*~~~~*~~~~*~~
#.@.##.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~*~~~~*~~~~*~~~~*~~
~~*~~~~*~~~~***~~*~~~~*~~~~*~~
#.@.#@.@.##.@.##.@.##.@.##.@.#
~~*~~~~*~~~~***~~*~~~~*~~~~*~~

and the output of my program:

Code: Select all

2
2
1
132

[martinezgjuan]

Code: Select all

3 4 2
*~~#
...@
.~.*

3 5 1
~~*~~
#.@.#
~~*~~

1 4 2
**#~

2 4 1
**##
@@@~

3 5 2
##@**
.~*~.
.....

3 5 2
##.**
.~*~.
.....

3 5 2
##.*.
.~*~~
.....

2 3 1
##*
~*~

3 4 1
***.
###*
~*~.

3 4 1
***.
@#@*
**~.

3 4 2
***.
@#@*
**~.

3 4 3
***.
@#@*
**~.

3 4 4
***.
@#@*
**~.

3 4 5
***.
@#@*
**~.

3 4 6
***.
@#@*
**~.

3 4 7
***.
@#@*
**~.

3 4 1
*@##
*@~#
*@~~

3 3 1
*.*
@#@
*.*

1 12 1
*#*#*#*##***

2 12 1
*~*~*~*~#***
..@.@@@@.@@@

2 12 2
*~*~*~*##***
..@@@@@@.@@@

6 3 2
*.~
*..
~@.
##.
#@#
@@#

4 5 1
*#*~.
.@*##
**#.#
.#~#~

13 3 1
.*@
#.#
.##
#.#
*@~
#.@
@**
@#*
@.*
~@@
#~#
.#*
*.@

6 5 1
@@~~*
..*.@
~#@#.
##~~@
##*@*
@*@#*

5 7 2
@.*~~.@
*@~@~~.
@@.@@##
*~@@@#@
..~~~##

6 3 2
*.~
*..
~@.
##.
#@#
@@#

Ans:

Code: Select all

2
2
1
2
3
2
2
2
3
1
2
3
4
5
6
6
3
1
5
1
4
1
4
8
6
1
1

[jddantes]

Why WA? I've been passing all the test cases.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

char input[32][32];

int res[32][32][2][5];
int src_res[32][32];
int sink_res[32][23];

typedef pair<int, int> pi;
typedef pair<int, pi> pii;

#define INF (1<<28)

class bfs_node{
public:
	int row, col;
	int flow;
	int on_top;

	int pred_row, pred_col;
	int pred_on_top;

	bfs_node(int R, int C, int ON_TOP, int PR, int PC, int PON_TOP, int FLOW){
		row = R;
		col = C;
		on_top = ON_TOP;

		pred_row = PR;
		pred_col = PC;
		pred_on_top = PON_TOP;

		flow = FLOW;
	}


};

pii pred[32][32][2];
bool visited[32][32][2];

int dy[] = {-1, 0, 1, 0, 0};
int dx[] = {0, 1, 0, -1, 0};

int get_dir(int curI, int curJ, int preI, int preJ){
	for(int dir = 0; dir<5; dir++){
		if(preI + dy[dir] == curI && preJ + dx[dir] == curJ){
			return dir;
		}
	}
	return -1;
}

int main(){
	int numRows, numCols, numCap;
	while(scanf("%d %d %d", &numRows, &numCols, &numCap)!=EOF){
		for(int i = 0; i<=numRows+1; i++){
			for(int j = 0; j<=numCols+1; j++){
				src_res[i][j] = 0;
				sink_res[i][j] = 0;
				
				for(int dir = 0; dir<5; dir++){
					res[i][j][0][dir] = 0;
					res[i][j][1][dir] = INF;
				}
				res[i][j][1][4] = 0;

			}
		}

		vector<pi> sources;
		vector<pi> sinks;

		for(int i = 1; i<=numRows; i++){
			for(int j = 1; j<=numCols; j++){
				scanf(" %c", &input[i][j]);
				if(input[i][j] == '#'){
					sinks.push_back(pi(i,j));
					sink_res[i][j] = numCap;
					res[i][j][0][4] = INF;
				}
				if(input[i][j] == '*'){
					sources.push_back(pi(i,j));
					src_res[i][j] = 1;
					res[i][j][0][4] = 1;
				}
				if(input[i][j] == '.'){
					res[i][j][0][4] = 1;
				}
				if(input[i][j] == '@'){
					res[i][j][0][4] = INF;
				}
				if(input[i][j] == '~'){
					res[i][j][0][4] = 0;
				}
			}
		}

		int ans_cnt = 0;

		while(1){

			queue<bfs_node> que;
			que.push(bfs_node(0,0,0,-1,-1,0,INF));

			for(int i = 0; i<=numRows+1; i++){
				for(int j = 0; j<=numCols+1; j++){
					for(int k = 0; k<2; k++){
						visited[i][j][k] = false;
						pred[i][j][k] = pii(-1,pi(-1,-1));
					}
				}
			}

			bool found_path = false;
			int chosen_flow = -1;
			// printf("Finding path\n");
			while(!que.empty()){

				bfs_node b = que.front();
				que.pop();

				int row = b.row;
				int col = b.col;
				int flow = b.flow;
				int on_top = b.on_top;

				int pred_row = b.pred_row;
				int pred_col = b.pred_col;
				int pred_on_top = b.pred_on_top;

				if(visited[row][col][on_top]){
					continue;
				}
				visited[row][col][on_top] = true;
				pred[row][col][on_top] = pii(pred_on_top, pi(pred_row, pred_col));

				// printf("Visited (%d,%d)_%d from (%d,%d)_%d\n", row, col, on_top, pred_row, pred_col, pred_on_top);

				if(row == numRows+1 && col == numCols+1){
					found_path = true;
					chosen_flow = flow;
					break;
				}

				if(row == 0 && col == 0){

					for(auto src : sources){
						if(src_res[src.first][src.second]){
							que.push(bfs_node({
								src.first, src.second, 0,
								0,0,0,
								INF
							}));
						}
					}
					continue;

				}

				for(int dir = 0; dir<5; dir++){
					int I = row + dy[dir];
					int J = col + dx[dir];

					if(I<=0 || I>=numRows+1 || J <= 0 || J>=numCols+1){
						continue;
					}
					int next_on_top = on_top ^ 1;
					if(input[I][J] == '~' || visited[I][J][next_on_top]){
						continue;
					}

					if(res[row][col][on_top][dir]){
						int next_flow = min(flow, res[row][col][on_top][dir]);
						que.push(bfs_node({
							I,J,next_on_top,
							row, col, on_top,
							next_flow
						}));
					}
				}

				if(sink_res[row][col] && on_top){
					que.push(bfs_node({
						numRows+1, numCols+1, 0,
						row,col, on_top,
						flow
					}));
				}

			}

			if(found_path){
				// printf("Found path\n");

				ans_cnt++;

				int cur_row = numRows+1;
				int cur_col = numCols+1;
				int cur_on_top = 0;

				while(cur_row || cur_col || cur_on_top){
					int pre_row = pred[cur_row][cur_col][cur_on_top].second.first;
					int pre_col = pred[cur_row][cur_col][cur_on_top].second.second;
					int pre_on_top = pred[cur_row][cur_col][cur_on_top].first;

					int dir = get_dir(cur_row, cur_col, pre_row, pre_col);
					int from_dir = (dir+2) % 4;

					if(cur_row == pre_row && cur_col == pre_col){
						from_dir = dir;
					}

					// printf("Got (%d,%d)_%d -> (%d,%d)_%d\n", pre_row, pre_col, pre_on_top, cur_row, cur_col, cur_on_top);

					if(cur_row == numRows +1 && cur_col == numCols+1){

						sink_res[pre_row][pre_col] -= chosen_flow;

					} else if (!pre_row && !pre_col){

						src_res[cur_row][cur_col] -= chosen_flow;

					} else {
						res[pre_row][pre_col][pre_on_top][dir] -= chosen_flow;
						res[cur_row][cur_col][cur_on_top][from_dir] += chosen_flow;

					}

					cur_row = pre_row;
					cur_col = pre_col;
					cur_on_top = pre_on_top;

				}



			} else {
				break;
			}


		}

		printf("%d\n", ans_cnt);




	}


	return 0;
}