首页 > 搜索 > DFS搜索 > HDU 3488-Tour-DFS-[解题报告]HOJ
2014
04-04

HDU 3488-Tour-DFS-[解题报告]HOJ

Tour

问题描述 :

In the kingdom of Henryy, there are N (2 <= N <= 200) cities, with M (M <= 30000) one-way roads connecting them. You are lucky enough to have a chance to have a tour in the kingdom. The route should be designed as: The route should contain one or more loops. (A loop is a route like: A->B->……->P->A.)
Every city should be just in one route.
A loop should have at least two cities. In one route, each city should be visited just once. (The only exception is that the first and the last city should be the same and this city is visited twice.)
The total distance the N roads you have chosen should be minimized.

输入:

An integer T in the first line indicates the number of the test cases.
In each test case, the first line contains two integers N and M, indicating the number of the cities and the one-way roads. Then M lines followed, each line has three integers U, V and W (0 < W <= 10000), indicating that there is a road from U to V, with the distance of W.
It is guaranteed that at least one valid arrangement of the tour is existed.
A blank line is followed after each test case.

输出:

An integer T in the first line indicates the number of the test cases.
In each test case, the first line contains two integers N and M, indicating the number of the cities and the one-way roads. Then M lines followed, each line has three integers U, V and W (0 < W <= 10000), indicating that there is a road from U to V, with the distance of W.
It is guaranteed that at least one valid arrangement of the tour is existed.
A blank line is followed after each test case.

样例输入:

1
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4

样例输出:

42

三道类基本一样的题(费用流);

题意: 一个无向图(or 有向图), 没一个点都必须属于一个圈, 并且只能属于一个圈, 求满足要求的最小费用。

比如:

1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42

 

像这杨构成圈并且每个点只能属于一个圈的题, 可以转化成2 分图, 每个点只能属于一个圈, 那么出度和入度必定为1 , 那么把一个点拆开i, i`, i控制入读, i` 控制出度, 流量只能为1 。 那么对于原来途中有的边 可以 i - > j`, j - > i`;连起来构图, 然后建立超级远点s,超级汇点t,s – > i , i` – > t ; 然后求最小费用流。。这样就抱着了每个点只能属于一个圈, 因为入读 == 出度 == 1 ;这类也问题可以  做为判断性问题出。

因为出入度 都是1 所以也可以用 km 求最值。。

代码:

 

 

 

参考:http://blog.csdn.net/yuhailin060/article/details/5865362


,
  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?