banner

原题链接

https://www.luogu.com.cn/problem/P3931

解题思路

根据题意，本题与最小割问题极为相似，根据最大流最小割定理，本题可转化为求网络最大流。

还未学习该知识的，请先学习，然后建议先写模板题练习一下。

首先，提醒一个雷区！题目给的是一个无向图，故我们需要先从树根开始对这个无向图进行dfs预处理，把无向边转换成有向边。（WA 20分的绝大多数都忽略了这一点，包括我）

然后，一个网络流图不仅要有源点（即树的根节点），还要有汇点。我们假设n+1即为汇点，让所有的叶子节点都伸出一条指向n+1的有向边（这个可以在dfs预处理时顺便处理一下，而且要记得建反向边）。

题目要求任何叶子节点都和根节点不连通，而这个条件恰恰和汇点和源点不连通是等价的（因为所有叶子节点都和汇点连通，故但凡有任何一个叶子节点和根节点连通，汇点和源点都是连通的）。

至此，我们已经完成了构造，接下来问题就只剩下求网络流图的最大流了。这里有多种算法可以选择，我使用的是dinic算法，具体实现不再赘述。在存图时我采取的是vector存图，下面的代码供参考。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define N 100005
#define I 0x3f3f3f3f//无穷大
using namespace std;
struct road{int to,w;};
struct edge{int to,w;}e[N<<2];//存储边的信息，考虑到双向建边（包括叶子节点与汇点）的问题，保险起见开四倍数组
vector<road> g[N];//存初始的无向图
vector<int> v[N];//存转化之后的有向图
int n,s,t,t1,t2,t3,cnt,ans,d[N];
void pre(int x,int fa)
{
  if(g[x].size()==1&&g[x][0].to==fa)//判叶子节点，和汇点建边
    {
      v[x].push_back(cnt);
      e[cnt].to=t;
      e[cnt++].w=I;
      v[t].push_back(cnt);//建反向边
      e[cnt].to=x;
      e[cnt++].w=0;
      return;
    }
  for(int i=0;i<g[x].size();i++)
    {
      int to=g[x][i].to,w=g[x][i].w;
      if(to==fa)continue;
      v[x].push_back(cnt);
      e[cnt].to=to;
      e[cnt++].w=w;
      v[to].push_back(cnt);//建反向边
      e[cnt].to=x;
      e[cnt++].w=0;
      pre(to,x);
    }
}
bool bfs()
{
  queue<int> q;
  memset(d,0,sizeof(d));
  d[s]=1;
  q.push(s);
  while(q.size())
    {
      int now=q.front();
      q.pop();
      for(int i=0;i<v[now].size();i++)
    {
      int temp=v[now][i];
      int to=e[temp].to,w=e[temp].w;
      if(!d[to]&&w)
        {
          d[to]=d[now]+1;
          q.push(to);
        }
    }
    }
  return d[t];
}
int dfs(int now,int minn)
{
  if(now==t)return minn;
  for(int i=0;i<v[now].size();i++)
    {
      int temp=v[now][i];
      int to=e[temp].to,w=e[temp].w;
      if(d[to]==d[now]+1&&w)
    {
      int res=dfs(to,min(minn,w));
      if(res)
        {
          e[temp].w-=res;
          e[temp^1].w+=res;
          return res;
        }
    }
    }
  return 0;
}
int main()
{
  scanf("%d%d",&n,&s);
  t=n+1;//设置汇点
  for(int i=1;i<n;i++)
    {
      scanf("%d%d%d",&t1,&t2,&t3);
      g[t1].push_back({t2,t3});//存无向图
      g[t2].push_back({t1,t3});
    }
  pre(s,s);//预处理，无向图转有向图
  while(bfs())//dinic算法求最大流
    ans+=dfs(s,I);
  printf("%d",ans);
  return 0;
}