首页 > 搜索 > DFS搜索 > HDU 3947-River Problem-图-[解题报告]HOJ
2015
04-14

HDU 3947-River Problem-图-[解题报告]HOJ

River Problem

问题描述 :

The River of Bitland is now heavily polluted. To solve this problem, the King of Bitland decides to use some kinds of chemicals to make the river clean again.

The structure of the river contains n nodes and exactly n-1 edges between those nodes. It’s just the same as all the rivers in this world: The edges are all unidirectional to represent water flows. There are source points, from which the water flows, and there is exactly one sink node, at which all parts of the river meet together and run into the sea. The water always flows from sources to sink, so from any nodes we can find a directed path that leads to the sink node. Note that the sink node is always labeled 1.

As you can see, some parts of the river are polluted, and we set a weight Wi for each edge to show how heavily polluted this edge is. We have m kinds of chemicals to clean the river. The i-th chemical can decrease the weight for all edges in the path from Ui to Vi by exactly 1. Moreover, we can use this kind of chemical for Li times, the cost for each time is Ci. Note that you can still use the chemical even if the weight of edges are 0, but the weight of that edge will not decrease this time.

When the weight of all edges are 0, the river is cleaned, please help us to clean the river with the least cost.

输入:

The first line of the input is an integer T representing the number of test cases. The following T blocks each represents a test case.

The first line of each block contains a number n (2<=n<=150) representing the number of nodes. The following n-1 lines each contains 3 numbers U, V, and W, means there is a directed edge from U to V, and the pollution weight of this edge is W. (1<=U,V<=n, 0<=W<=20)

Then follows an number m (1<=m<=2000), representing the number of chemical kinds. The following m lines each contains 4 numbers Ui, Vi, Li and Ci (1<=Ui,Vi<=n, 1<=Li<=20, 1<=Ci<=1000), describing a kind of chemical, as described above. It is guaranteed that from Ui we can always find a directed path to Vi.

输出:

The first line of the input is an integer T representing the number of test cases. The following T blocks each represents a test case.

The first line of each block contains a number n (2<=n<=150) representing the number of nodes. The following n-1 lines each contains 3 numbers U, V, and W, means there is a directed edge from U to V, and the pollution weight of this edge is W. (1<=U,V<=n, 0<=W<=20)

Then follows an number m (1<=m<=2000), representing the number of chemical kinds. The following m lines each contains 4 numbers Ui, Vi, Li and Ci (1<=Ui,Vi<=n, 1<=Li<=20, 1<=Ci<=1000), describing a kind of chemical, as described above. It is guaranteed that from Ui we can always find a directed path to Vi.

样例输入:

2
3
2 1 2
3 1 1
1
3 1 2 2
3
2 1 2
3 1 1
2
3 1 2 2
2 1 2 1

样例输出:

Case #1: -1
Case #2: 4

此题是以《NOI2008志愿者招募》为背景的,预做此题需要先体会《志愿者招募》的思想

只不过由线性结构变为树形结构,但是问题的本质没有变,都是一个元素影响连续的若干个位置,构图的本质都是使每个变量x出现分别以+和-的形式出现在两个恒等式中,由此可以看做x变量从+式流入-式流出。设药品为x,为每条河建立一个等式,则x出现在了u的父边到v的父边路径上的所有等式中,因此用每个点的父边减去所有孩子的边(设根节点的父边为全0,即没有限制)得到n个等式,且所有变量x、y均以+和-的形式各出现一次,由此可以构图。若求出最大流==源点的最大容量则最小费用即为解,否则无解。

志愿者招募题解写的不错,体会一下x、y变量的作用应该就会构图了,构图如下:

class node {
		int be, ne;
		int id, val;
		node(int b, int e, int v) {
			be = b;
			ne = e;
			val = v;
		}
	}
	node buf[] = new node[maxn];
	int E[] = new int[maxn], len;
	void add(int a, int b, int v) {
		buf[len] = new node(b, E[a], v);
		id[b] = len;
		E[a] = len++;
	}
	Scanner scan = new Scanner(System.in);
	int n, m, id[] = new int[maxn], sum;
	boolean is[] = new boolean[maxn];
	MINCOST sp = new MINCOST();
	void init() {
		sp.init();
		len = 0;
		Arrays.fill(E, -1);
		Arrays.fill(is, true);
		sum = 0;
	}
	void run() {
		int cas = scan.nextInt();
		for (int k = 1; k <= cas; k++) {
			System.out.print("Case #" + k + ": ");
			n = scan.nextInt();
			init();
			int a, b, v;
			for (int i = 1; i < n; i++) {
				a = scan.nextInt();
				b = scan.nextInt();
				v = scan.nextInt();
				is[a] = false;
				add(b, a, v);
			}
			int root = -1;
			for (int i = 1; i <= n; i++)
				if (is[i]) {
					root = i;
					break;
				}
			id[root] = n - 1;
			int s, t, l, c;
			m = scan.nextInt();
			for (int i = 0; i < m; i++) {
				s = scan.nextInt();
				t = scan.nextInt();
				l = scan.nextInt();
				c = scan.nextInt();
				sp.addcap(id[s], id[t], l, c);
			}
			int temp = 0;
			for (int i = E[root]; i != -1; i = buf[i].ne) {
				temp += buf[i].val;
				sp.addcap(n - 1, i, inf, 0);
				dfs(i);
			}
			sp.addcap(n - 1, n + 1, temp, 0);
			int ans = sp.solve(n, n + 1);
			if (sp.maxflow == sum)
				System.out.println(ans);
			else
				System.out.println(-1);
		}
	}
	void dfs(int a) {
		int temp = buf[a].val;
		int v = buf[a].be;
		for (int i = E[v]; i != -1; i = buf[i].ne) {
			sp.addcap(a, i, inf, 0);
			temp -= buf[i].val;
			dfs(i);
		}
		if (temp > 0) {
			sp.addcap(n, a, temp, 0);
			sum += temp;
		} else
			sp.addcap(a, n + 1, -temp, 0);
	}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/kksleric/article/details/7845188


, ,
  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. [email protected]

  4. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。