本文共 1891 字，大约阅读时间需要 6 分钟。

一颗二叉树有$n-1$条边

我们把每条边看作一个匹配规则,每个点可以作为父亲至多两次,作为儿子一次

那么可以求一个最大匹配,把每个点作为父亲的状态放在二分图左边,作为儿子的状态放在二分图右边

这样所有匹配规则都是连接这一个父亲一个儿子

源点向父亲节点连边,流量为$2$费用为$0$

儿子节点向汇点连边,流量为$1$费用为$0$

然后按照匹配规则连接父亲和儿子的边,费用为欧几里得距离

由于是个二分图,所以求最大匹配一定没错,最多有$n-1$的流量

跑最小费用最大流即可

#include 
   
    using namespace std;const int maxn = 1e6+10;const int inf = 1e8;const double eps = 1e-7;struct edge{
   	int to,nxt,flow; double w;//分别代表}d[maxn<<1]; int head[maxn],cnt=1;void add(int u,int v,int flow,double w)//最大流量,单位费用{
   	d[++cnt]=(edge){
   v,head[u],flow,w},head[u]=cnt;	d[++cnt]=(edge){
   u,head[v],0,-w},head[v]=cnt;}double dis[maxn];int x[maxn],y[maxn],s,t,n;int vis[maxn],flow[maxn],pre[maxn];bool spfa(){
   	queue
    
     q;	q.push(s);	for(int i=0;i<=t;i++)	dis[i]=inf,vis[i]=0;	dis[s]=0,vis[s]=1; flow[s] = inf;	while( !q.empty() )	{
   		int u=q.front(); q.pop();		vis[u]=0;//出队		for(int i=head[u];i;i=d[i].nxt)		{
   			if( !d[i].flow )	continue;//无流量了			int v=d[i].to;			if( dis[v]>dis[u]+d[i].w+eps )			{
   				dis[v]=dis[u]+d[i].w; flow[v] = min(flow[u],d[i].flow); pre[v]=i;				if( !vis[v] )	vis[v]=1,q.push(v);			}		}	}	if( dis[t]==inf )	return 0;	return 1;}void MCMF(){
       int maxflow = 0; double mincost = 0;	while( spfa() )	{
   		int i,x=t;//倒回去找路径		maxflow += flow[t];  mincost+=dis[t]*flow[t];		while(x != s)		{
   			i=pre[x];			d[i].flow-=flow[t]; d[i^1].flow+=flow[t];//加上流量			x = d[i^1].to;		 }	}    if( maxflow!=n-1 )  cout << -1;    else    printf("%.7lf",mincost );}double get(int i,int j){
   	return sqrt( 1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]) );}signed main(){
   	cin >> n;    s = 0, t = n+n+1;    for(int i=1;i<=n;i++)    {
           add(s,i,2,0); add(i+n,t,1,0);        cin >> x[i] >> y[i];    }    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++)    {
           if( i==j || y[i]<=y[j] ) continue;        add(i,j+n,1,get(i,j) );    }    MCMF();}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115407054 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！