POJ 3585 Accumulation Degree 树最大流（树形dp+二次扫描与换根法）

不念不忘少年蓝@ 2021-12-01 10:54 162阅读 0赞

## 题意：给出一棵树，树上的边都有其权值，让我们求一个点能往外流的最大流量（会受到其它边权容量的限制）。 ##

## 分析：二次扫描与换根法模板题，详见《算法竞赛进阶指南》P292-295，讲的很详细，一看就懂。 ##

## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N = 1e6+5;
    int d[N], v[N], f[N], deg[N];
    int head[N], ver[N], edge[N], Next[N];
    int n, T, tot, root, ans;
    
    void add(int x, int y, int z) {
    	ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    }
    
    void dp(int x) {
    	v[x] = 1; // 访问标记
    	d[x] = 0;
    	for (int i = head[x]; i; i = Next[i]) { // 邻接表存储
    		int y = ver[i];
    		if (v[y]) continue;
    		dp(y);
    		if (deg[y] == 1) d[x] += edge[i]; // edge[i]保存c(x,y)
    		else d[x] += min(d[y], edge[i]);
    	}
    }
    
    void dfs(int x) {
    	v[x] = 1;
    	for (int i = head[x]; i; i = Next[i]) {
    		int y = ver[i];
    		if (v[y]) continue;
    		if (deg[x] == 1) f[y] = d[y] + edge[i];
    		else f[y] = d[y] + min(f[x] - min(d[y], edge[i]), edge[i]);
    		dfs(y);
    	}
    }
    
    int main() {
    	cin >> T;
    	while (T--) {
    		tot = 1;
    		cin >> n;
    		tot = 1;
    		for (int i = 1; i <= n; i++)
    			head[i] = f[i] = d[i] = deg[i] = v[i] = 0;
    		for (int i = 1; i < n; i++) {
    			int x, y, z;
    			scanf("%d%d%d", &x, &y, &z);
    			add(x, y, z), add(y, x, z);
    			deg[x]++, deg[y]++;
    		}
    		int root = 1; /// 任选一个点为源点
    		dp(root);///第一次扫描
    		for (int i = 1; i <= n; i++) v[i] = 0;
    		f[root] = d[root];
    		dfs(root);///第二次扫描
    		int ans = 0;
    		for (int i = 1; i <= n; i++)
    			ans = max(ans, f[i]);
    		cout << ans << endl;
    	}
    	return 0;
    }