2015
04-14

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

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);
}

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

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

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