题目链接：
肉眼观察题目感觉可以跑最大流。 证明是如果拆断一棵树，可以最小割，最小割等于最大流。 注意： 图是无向边，在网络流里建两次边，即四次。 统计一下叶子节点，再建一个超级汇点，所有距离为inf。#include#include #include #include #include using namespace std;const int maxn = 1000000 + 10;const int inf = 1e9;int isleaf[maxn];int n, m, s, t, deep[maxn], maxflow;struct edge{ int next, to, len;}e[maxn<<2];int head[maxn], cnt = -1, cur[maxn];queue q;void add(int u, int v, int w, bool flag){ e[++cnt].next = head[u]; e[cnt].to = v; if(flag) e[cnt].len = w; head[u] = cnt;}bool bfs(int s, int t){ memset(deep, 0x7f, sizeof(deep)); while(!q.empty()) q.pop(); for(int i = 1; i <= n; i++) cur[i] = head[i]; deep[s] = 0; q.push(s); while(!q.empty()) { int now = q.front(); q.pop(); for(int i = head[now]; i != -1; i = e[i].next) { if(deep[e[i].to] > inf && e[i].len) { deep[e[i].to] = deep[now] + 1; q.push(e[i].to); } } } if(deep[t] < inf) return true; else return false;}int dfs(int now, int t, int limit){ if(!limit || now == t) return limit; int flow = 0, f; for(int i = cur[now]; i != -1; i = e[i].next) { cur[now] = i; if(deep[e[i].to] == deep[now] + 1 && (f = dfs(e[i].to, t, min(limit, e[i].len)))) { flow += f; limit -= f; e[i].len -= f; e[i^1].len += f; if(!limit) break; } } return flow;}void Dinic(int s, int t){ while(bfs(s, t)) maxflow += dfs(s, t, inf);}int main(){ memset(head, -1, sizeof(head)); scanf("%d%d",&n,&s); t = 1 + n; for(int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d",&u,&v,&w); add(u, v, w, 1); add(v, u, w, 0); add(v, u, w, 1); add(u, v, w, 0); isleaf[u]++, isleaf[v]++; } for(int i = 1; i <= n; i++) { if(isleaf[i] == 1 && i != s) add(i, t, inf, 1), add(t, i, inf, 0), add(i, t, inf, 0), add(t, i, inf, 1); } Dinic(s, t); printf("%d\n",maxflow); return 0;}