首页 > ACM题库 > HDU-杭电 > hdu 3755 Cactus Revolution待解决[解题报告]C++
2015
04-10

hdu 3755 Cactus Revolution待解决[解题报告]C++

Cactus Revolution

问题描述 :

Advanced Cave Megapolis (ACM) is a city that survives in the underground caves after the global nuclear war. The caves are connected by passages and the whole city map can be represented by a graph with caves being vertices and passages between them being nodes.
There is a revolution in the cave city. The whole population of the city is evenly split into k parties that cannot agree on the common laws that they should adopt. They had decided to split their city into k districts and have each district’s citizens impose the laws of their liking upon themselves.
You are given a city map in the form of the graph and your task is to write a program that partitions this graph into k equally sized districts. Each district must form a connected subgraph that is represented by the subset of the graph’s vertices.
Fortunately, the number of vertices in the graph is divisible by k and the graph representing the city happens to be a cactus – a connected undirected graph in which every edge belongs to at most one simple cycle. Intuitively, cactus is a generalization of a tree where some cycles are allowed.
The example of a city map with 15 caves and its partitioning into 3 districts is shown on the picture below.

输入:

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains three integer numbers n, m, and k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 10 000, 1 ≤ k ≤ n). Here n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graph are represented by a set of edge-distinct paths, where m is the number of such paths, k is the number of districts that the city must be partitioned into, n is divisible by k.
Each of the following m lines contains a path in the graph. A path starts with an integer number si (2 ≤ si ≤ 1000) followed by si integers from 1 to n. These si integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go through the same vertex multiple times, but every edge is traversed exactly once in the whole input file. There are no multiedges in the graph (there is at most one edge between any two vertices).
The graph in each case is a cactus.

输出:

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains three integer numbers n, m, and k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 10 000, 1 ≤ k ≤ n). Here n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graph are represented by a set of edge-distinct paths, where m is the number of such paths, k is the number of districts that the city must be partitioned into, n is divisible by k.
Each of the following m lines contains a path in the graph. A path starts with an integer number si (2 ≤ si ≤ 1000) followed by si integers from 1 to n. These si integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go through the same vertex multiple times, but every edge is traversed exactly once in the whole input file. There are no multiedges in the graph (there is at most one edge between any two vertices).
The graph in each case is a cactus.

样例输入:

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

样例输出:

4 5 6 7 8
10 11 12 13 15
1 2 3 9 14
-1


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  3. 在方法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的边不是都没了吗?

  4. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  5. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish