目录
题目题解题解一code1题解2code2
题目
http://poj.org/problem?id=3585
题目大意：给一棵无根树，求出最大流量
题解
题解一
暴力做法枚举源点
s
s
s，让
s
s
s作为整棵树的根，然后就变成了树形
D
P
DP
DP，因为答案的取得与子树有关 设
f
[
x
]
f[x]
f[x]表示已
x
x
x为根，把
x
x
x作为源点，从
x
x
x向子树出发所获得的最大流量。 设
d
e
g
r
e
e
[
i
]
degree[i]
degree[i]表示点
i
i
i的度 那么方程为
f
[
x
]
=
∑
s
o
n
(
x
)
{
min
(
f
[
y
]
,
c
(
x
,
y
)
)
d
e
g
r
e
e
[
y
]
>
1
c
(
x
,
y
)
d
e
g
r
e
e
[
y
]
=
1
f[x]= \sum_{son(x)} \begin{cases} \min(f[y],c(x,y)) & degree[y] > 1\\ c(x,y)°ree[y]=1\end{cases}
f[x]=son(x)∑{min(f[y],c(x,y))c(x,y)degree[y]>1degree[y]=1 时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)
code1
void dp(int x
) {
vis
[x
] = true;
f
[x
] = 0;
for (int i
= lin
[x
]; i
; i
= edge
[i
].next
) {
int y
= edge
[i
].to
;
if (vis
[y
]) continue;
dp(y
);
if (deg
[y
] == 1) f
[x
] += edge
[i
].dis
;
else f
[x
] += min(f
[y
], edge
[i
].dis
);
}
}
int main() {
for (int i
= 1; i
<= n
; ++i
) {
memset(f
, 0x3f, sizeof(f
));
memset(vis
, false, sizeof(vis
));
dp(i
);
ans
= max(ans
, f
[i
]);
}
printf("%d\n", ans
);
}
题解2
本题是一道不定根的树型
D
P
DP
DP，我们可以通过两次扫描来求解此类题目 1、第一次扫描时选取任意一点为根，在“有根树”上执行树形
D
P
DP
DP，也就是在回溯时发生的，自底向上的状态转移 2、第二次扫描时，从刚才选的根出发，
d
f
s
dfs
dfs遍历整棵树，在递归前自上而下的推导，计算换根后的解
具体实现过程为首先任选一个源点作为根节点，记为
r
o
o
t
root
root，利用解法一来
D
P
DP
DP求出
d
r
o
o
t
d_{root}
droot 设
f
[
x
]
f[x]
f[x]表示已
x
x
x为根，把
x
x
x作为源点，从
x
x
x向子树出发所获得的最大流量 有
f
[
r
o
o
t
]
=
d
[
r
o
o
t
]
f[root]=d[root]
f[root]=d[root] 假设
f
[
x
]
f[x]
f[x]已被求出，其子节点
y
y
y的
f
[
y
]
f[y]
f[y]尚未被求出，那么
f
[
y
]
f[y]
f[y]中包含两部分
\qquad
1、从
y
y
y流向已
y
y
y为根的子树的流量为
d
[
y
]
d[y]
d[y]
\qquad
2、从
y
y
y沿着到父亲节点
x
x
x的河道，流向其他区域的流量 因为
f
[
x
]
f[x]
f[x]为
x
x
x的总流量，那么从
x
x
x到
y
y
y的流量为
min
(
d
[
y
]
,
c
(
x
,
y
)
)
\min(d[y],c(x,y))
min(d[y],c(x,y))，所以从
x
x
x流向
y
y
y以外的流量为两者之差，所以把
y
y
y作为源点先流到
x
x
x在流向其他部分的流量就是这个差再于
c
(
x
,
y
)
c(x,y)
c(x,y)相比取最小值的结果。
f
[
y
]
=
d
[
y
]
+
{
m
i
n
(
f
[
x
]
−
m
i
n
(
d
[
y
]
,
c
(
x
,
y
)
)
,
c
(
x
,
y
)
)
d
e
g
r
e
e
[
x
]
>
1
c
(
x
,
y
)
d
e
g
r
e
e
[
x
]
=
1
f[y]=d[y]+\begin{cases} min(f[x]-min(d[y],c(x,y)),c(x,y))°ree[x]>1\\c(x,y)°ree[x]=1\end{cases}
f[y]=d[y]+{min(f[x]−min(d[y],c(x,y)),c(x,y))c(x,y)degree[x]>1degree[x]=1 可以用
d
f
s
dfs
dfs来求得结果 时间复杂度为
O
(
n
)
O(n)
O(n)
code2
#include <bits/stdc++.h>
using namespace std
;
const int maxn
= 2e5 + 100;
const int maxm
= 4e5 + 100;
template <typename T
>
inline void read(T
&s
) {
s
= 0;
T w
= 1, ch
= getchar();
while (!isdigit(ch
)) { if (ch
== '-') w
= -1; ch
= getchar(); }
while (isdigit(ch
)) { s
= (s
<< 1) + (s
<< 3) + (ch
^ 48); ch
= getchar(); }
s
*= w
;
}
template <typename T
>
inline void write(T s
) {
T w
= 0, c
[15];
if (s
< 0) putchar('-'), s
= -s
;
while(s
) c
[++w
] = (s
% 10) + 48, s
/= 10;
while(w
) putchar(c
[w
--]);
}
template <typename T
>
inline void output(T size
, T arr
[maxn
]) {
for (int i
= 1; i
<= size
; ++i
) {
printf("%d ", arr
[i
]);
}
puts("");
}
inline int max(int a
, int b
) { return a
> b
? a
: b
; }
inline int min(int a
, int b
) { return a
< b
? a
: b
; }
int T
, n
, tot
, cnt
, ans
;
int lin
[maxn
], deg
[maxn
], snk
[maxn
], d
[maxn
], f
[maxn
];
bool vis
[maxn
];
struct node
{
int next
, to
, dis
;
} edge
[maxm
];
inline void add(int from
, int to
, int dis
) {
deg
[to
]++;
edge
[++tot
].to
= to
;
edge
[tot
].dis
= dis
;
edge
[tot
].next
= lin
[from
];
lin
[from
] = tot
;
}
void dp(int x
) {
vis
[x
] = true;
d
[x
] = 0;
for (int i
= lin
[x
]; i
; i
= edge
[i
].next
) {
int y
= edge
[i
].to
;
if (vis
[y
]) continue;
dp(y
);
if (deg
[y
] == 1) d
[x
] += edge
[i
].dis
;
else d
[x
] += min(d
[y
], edge
[i
].dis
);
}
}
void dfs(int x
) {
vis
[x
] = true;
for (int i
= lin
[x
]; i
; i
= edge
[i
].next
) {
int y
= edge
[i
].to
;
if (vis
[y
]) continue;
if (deg
[x
] == 1) f
[y
] = d
[y
] + edge
[i
].dis
;
else f
[y
] = d
[y
] + min(f
[x
] - min(d
[y
], edge
[i
].dis
), edge
[i
].dis
);
dfs(y
);
}
}
int main() {
read(T
);
while (T
--) {
tot
= 0;
cnt
= 0;
ans
= -1;
memset(deg
, 0, sizeof(deg
));
memset(lin
, 0, sizeof(lin
));
read(n
);
for (int i
= 1; i
< n
; ++i
) {
int x
, y
, z
;
read(x
), read(y
), read(z
);
add(x
, y
, z
);
add(y
, x
, z
);
}
int root
= 1;
memset(d
, 0x3f, sizeof(d
));
memset(vis
, false, sizeof(vis
));
dp(root
);
memset(vis
, false, sizeof(vis
));
f
[root
] = d
[root
];
dfs(root
);
for (int i
= 1; i
<= n
; ++i
) {
ans
= max(ans
, f
[i
]);
}
write(ans
), putchar('\n');
}
return 0;
}
