Code: Select all

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

Code: Select all

```
3
2
2
```

Any tricky cases? I keep get wa. Thanks.

**Moderator:** Board moderators

Is the following correct?

Any tricky cases? I keep get wa. Thanks.

Code: Select all

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

Code: Select all

```
3
2
2
```

Any tricky cases? I keep get wa. Thanks.

What is the idea for this problem?

I guess we can formulate it as a maxflow. We have both vertex capacities and edges capacities here. And, the main problem is the condition:

Two people cant be on the same iceberg at the same time.

How can I incorporate that condition into maxflow if there is no time in the state?

Thanks,

I guess we can formulate it as a maxflow. We have both vertex capacities and edges capacities here. And, the main problem is the condition:

Two people cant be on the same iceberg at the same time.

How can I incorporate that condition into maxflow if there is no time in the state?

Thanks,

Ah yes, ... but in this case, I guess this approach would work:mf wrote:Just ignore it - time doesn't matter.

In this problem people can stay at the same place for any period of time and nothing bad will happen. So, you could make people move to their destinations by one person at a time, and in this scenario no two persons would ever be at an iceberg at the same time.

Find the shortest path from each person to one of the wooden planks. since each wooden plank has a maximum capacity of P, the only thing we have to minimize in the path is the number of ices plates broken.

So, if we do the above shortest path for each person, repeatedly, and then updating the vertex capacities, it should give the right answer.

But what I said above is the shortest augmenting path algorithm for maxflow, am I right?

mf wrote:If you make and post some inputs, I can show the output of my accepted program for them.

Code: Select all

```
3 3 1
*.*
@#@
*.*
Ans: 1
1 12 1
*#*#*#*##***
Ans: 5
2 12 1
*~*~*~*~#***
..@.@@@@.@@@
Ans: 1
2 12 2
*~*~*~*##***
..@@@@@@.@@@
Ans: 4
```

Okay. I tried many more, got them right.mf wrote:That's all correct.

Let me explain the connections in the graph.

Each cell is a vertex. With a vertex capacity for

1. # => infi

2. @ => inf

3. "." => 1

4. * => 1

5. ~ => 1

Now, create a digraph where there are connections between

. and # @ . of capacity 1

. and * of cap 0

* and . of cap 1

* and # @ of cap inf

* and ~ or * of cap 0

# and # or @ of cap inf

# and . of cap 1

# with others of cap 0

@ and * of cap 0

@ and others cap inf

and (anything and ~) of cap 0

...

Edge capacities, I felt, were required. And not just vertex capacities...

Now, according to the vertex splitting method:

if u,v is an edge:

cap 2u, 2u+1 = vertex_cap u

cap 2u+1, 2v = cap u, v

cap v, 2v+1 = vertex_cap v

and no back edge.

now, edge between # (the odd numbered part) and sink is of capacity P,

edge between src and persons of cap 1.

Did I go wrong in the formulation?

Hmm, but if I do that, for this case:mf wrote:It seems correct to me.

But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell.

Code: Select all

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

Thanks mf, I got it AC.mf wrote:It seems correct to me.

But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell.

I just re-read my program (damn, I should do it properly next time), and the mistake I did was:

Code: Select all

```
for all vertices u,v:
add (2u,2u+1) with vcap(u)
add (2v,2v+1) with vcap(v)
add(2u+1,2v) with edgecap(u,v)
```

Code: Select all

```
add (2u,2u+1) with vcap(u)
add (2v,2v+1) with vcap(v)
```

Silly mistake...