亟隐

朝不闻道,夕亦死可矣

07/23
11:38
图论 算法区 网络流

HDU 4067 Random Maze

地址:戳这里

Problem Description
In the game “A Chinese Ghost Story”, there are many random mazes which have some characteristic:
1.There is only one entrance and one exit.
2.All the road in the maze are unidirectional.
3.For the entrance, its out-degree = its in-degree + 1.
4.For the exit, its in-degree = its out-degree + 1.
5.For other node except entrance and exit, its out-degree = its in-degree.

There is an directed graph, your task is removing some edge so that it becomes a random maze. For every edge in the graph, there are two values a and b, if you remove the edge, you should cost b, otherwise cost a.
Now, give you the information of the graph, your task if tell me the minimum cost should pay to make it becomes a random maze.

 

Input
The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
For each test case, there is a line with four integers, n, m, s and t, means that there are n nodes and m edges, s is the entrance’s index, and t is the exit’s index. Then m lines follow, each line consists of four integers, u, v, a and b, means that there is an edge from u to v.
2<=n<=100, 1<=m<=2000, 1<=s, t<=n, s != t. 1<=u, v<=n. 1<=a, b<=100000
Output
For each case, if it is impossible to work out the random maze, just output the word “impossible”, otherwise output the minimum cost.(as shown in the sample output)
Sample Input
2 2 1 1 2 2 1 2 3 5 6 1 4 1 2 3 1 2 5 4 5 5 3 2 3 3 2 6 7 2 4 7 6 3 4 10 5
Sample Output
Case 1: impossible Case 2: 27

首先不考虑度的情况下构造一个费用最小的图,就是当边用的费用比不用的低时才留下。留下的边从建立一条费用为b-a的边,否则建一条a-b的反向边。统计总费用和度,起点入度和终点出度都加1.枚举点,如果出度大于入度,就从源点连接一条流为(出度-入度)的边,否则建一条到汇点的边。然后跑费用流,每次流过的边表示要改变用不用状态,如果满流表示有解。

代码:戳这里