2014
02-17

# Watering Hole

Farmer John has decided to bring water to his N (2 <= N <= 5,000) pastures which are conveniently numbered 1..N. And He has M (1 <= M <= 25,000) pipes. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs p (1 <= p <= 100,000). Since the length and quality are different, there may be more than one pipes in different costs connecting pasture i and j.

Luckily, farmer John found there was only one plan to minimize his cost.

Farmer Jack, farmer John’s friend, has P (1 <= P <= 1,000) pipes. He promised that he could give one pipe to Farmer John, and farmer John can use it to connect his pasture i and j. Now, farmer John wants to know how much the minimum amount he will have to pay to water all of his pastures if he chooses one more pipe from Jack.

There are serveral cases:
Line 1: Three integers: N, M and P

Lines 2: N space-separated integers; the i-th integer is W_i

Lines 3..M+3: Three integers: i, j, p. Means a pipe connecting pasture i and j costs p

Lines M+4..P+M+4: Two Integers: i, j. Farmer Jack can give Farmer John a pipe connecting pasture i and j.

There are serveral cases:
Line 1: Three integers: N, M and P

Lines 2: N space-separated integers; the i-th integer is W_i

Lines 3..M+3: Three integers: i, j, p. Means a pipe connecting pasture i and j costs p

Lines M+4..P+M+4: Two Integers: i, j. Farmer Jack can give Farmer John a pipe connecting pasture i and j.

4 6 1
5 4 4 3
1 2 2
1 3 2
1 4 2
2 3 3
2 4 3
3 4 4
3 4

7

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

const int N = 5005;
const int M = N << 4;

int p[N], n, m, sum, w[N];

struct Edge {
int u, v, w;

void init(int a, int b, int c) {
u = a, v = b, w = c;
}

bool operator <(const Edge& e) const {
return w < e.w;
}
}E[M];

int find(int u) {
if (p[u] != u)
p[u] = find(p[u]);
return p[u];
}

const int lim = 17;

struct Tree {

struct Edge {
int v, w;
Edge* next;

void init(int a, Edge* e, int b) {
v = a;
w = b;
next = e;
}
};

Edge E[M];
Edge* it, * head[N];
int pa[N][lim], dep[N], dis[N];
int maxv[N][lim];
int W[N];
int n;

void init(int n) {
this->n = n;
for (int i = 0; i < n; head[i++] = 0);
it = E;
}

void add(int u, int v, int w) {
it->init(v, head[u], w);
head[u] = it++;
it->init(u, head[v], w);
head[v] = it++;
}

int lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
if (dep[u] < dep[v]) {
int d = dep[v] - dep[u];
for (int i = 0; i < lim; i++)
if (d & (1 << i))
v = pa[v][i];
}
if (u != v) {
for (int i = lim - 1; i >= 0; i--)
if (pa[u][i] != pa[v][i]) {
u = pa[u][i];
v = pa[v][i];
}
u = pa[u][0];
}
return u;
}

int query(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
int res = -1;

if (dep[u] < dep[v]) {
int d = dep[v] - dep[u];
for (int i = 0; i < lim; i++)
if (d & (1 << i)) {
res = max(maxv[v][i], res);
v = pa[v][i];
}
}

if (u != v) {
for (int i = lim - 1; i >= 0; i--) {
if (pa[u][i] != pa[v][i]) {
res = max(res, maxv[u][i]);
res = max(res, maxv[v][i]);
u = pa[u][i];
v = pa[v][i];
}
}
res = max(res, maxv[u][0]);
res = max(res, maxv[v][0]);
}
return res;
}

void dfs(int u, int fa) {
pa[u][0] = fa;
maxv[u][0] = W[u];
dep[u] = dep[fa] + 1;
for (int i = 1; (1 << i) < n; i++) {
pa[u][i] = pa[pa[u][i - 1]][i - 1];
maxv[u][i] = max(maxv[u][i - 1], maxv[pa[u][i - 1]][i - 1]);
}
for (Edge* e = head[u]; e; e = e->next) {
int v = e->v;
if (v != fa) {
W[v] = e->w;
dfs(v, u);
}
}
}

void run(int rt) {
dep[rt] = -1;
W[rt] = -1;
dfs(rt, rt);
}
}T;

int main() {
int u, v, w, c;
while (~scanf("%d%d%d", &n, &m, &sum)) {
c = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &w);
E[c].init(0, i, w);
c++;
}
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
E[c].init(u, v, w);
c++;
}

n++;
m += n;

T.init(n);

int res = 0;
sort(E, E + c);
int cnt = 0;

for (int i = 0; i < n; i++) p[i] = i;

for (int i = 0; i < c; i++) {
int fu = find(E[i].u), fv = find(E[i].v);
if (fu != fv) {
p[fu] = fv;
res += E[i].w;
T.add(E[i].u, E[i].v, E[i].w);
cnt++;
}
if (cnt == n - 1) break;
}

T.run(0);

for (int i = 0; i < sum; i++) {
scanf("%d%d", &u, &v);
int tmp = T.query(u, v);
printf("%d\n", res - tmp);
}

}
return 0;
}

1. 第二种想法，我想来好久，为啥需要一个newhead，发现是把最后一个节点一直返回到嘴上面这层函数。厉害，这道题之前没样子想过。

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