Min Cut und Max Flow

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Min Cut und Max Flow

    Hallo Leute, ich hab hier schwiergen Java Code zu schreiben, es geht (glaub ich) um Min Cut und Max Flow Algorithmen,

    paar Ideen wie man das Programm schreiben kann habe ich schon, bin aber net sicher ob sie richtig sind, wenn jemand mir dabei helfen kann, wird es echt super
    [u]
    zuerst hier ist die Aufgabe zu lesen:
    [/u]
    Pool


    You are working for the International Company for Pool Construction, a construction company which
    specializes in building swimming pools. A new client wants to build several new pool areas.
    A pool area is a rectangular grid of w×h square patches, consisting of zero or more (possibly disconnected)
    pools. A pool consists of one or multiple connected hole patches, which will later be filled with water. In
    the beginning, you start with a piece of land where each patch is either a hole in the ground (’.’) or flat
    grass (’#’). In order to transform this land into a pool area, you must adhere to the following:
    • You can leave a patch as it is. This costs nothing.
    • If the patch is grass in the beginning, you can dig a hole there. This costs d EUR.
    • If the patch is a hole in the beginning, you can fill the hole and put grass on top. This costs f EUR.
    • You must place special boundary elements along each edge running between a final grass patch and
    a final hole patch, to ensure that water does not leak from the pool. This costs b EUR per boundary
    element.
    • The outermost rows and columns of the pool area must always be grass.
    You are given the task of calculating the cost of the cheapest possible pool area given the layout of the
    existing piece of land.

    INPUT
    On the first line a positive integer: the number of test cases, at most 100. After that per test case:
    • one line with two integers w and h (2 ≤ w, h ≤ 50): the width and height of the building site.
    • one line with three integers d, f and b (1 ≤ d, f, b ≤ 10000): the costs for digging a new hole, filling
    an existing hole, and building a boundary element between a pool and grass patch.
    • h lines of w characters each, denoting the layout of the original building site.
    OUTPUT
    Per test case:
    • one line with an integer: the cost of building the cheapest possible pool area from the original piece
    of land.

    SAMPLE INPUT
    3
    3 3
    5 5 1
    # . #
    # . #
    ###
    5 4
    1 8 1
    # . . ##
    ## . ##
    # . # . #
    #####
    2 2
    27 11 11
    # .
    . #