首页 > 其他分享 >题解 CF277E【Binary Tree on Plane】

题解 CF277E【Binary Tree on Plane】

时间:2023-01-29 22:45:07浏览次数:39  
标签:pre 题解 ll vis Plane text double CF277E dis

费用流。

可以将原问题转化为类似于匹配的问题,只不过这种匹配并不是一对一的。具体地,将每个点 \(u\) 拆成两个点 \(u_\text{fa},u_\text{son}\),设源点为 \(s\)、汇点为 \(t\),则一条流 \(s\to u_\text{fa}\to v_\text{son}\to t\) 就代表 \(u\) 是 \(v\) 的父亲。

一个节点最多作为两个节点的父亲,因此 \(s\to u_\text{fa}\) 的容量为 \(2\)、代价为 \(0\)。一个节点最多作为一个节点的儿子,因此 \(u_\text{son}\to t\) 的容量为 \(1\)、代价为 \(0\)。对于每一对节点 \((u,v)\),若 \(u\) 可以作为 \(v\) 的父亲,则连接一条边 \(u_\text{fa}\to v_\text{son}\),容量为 \(1\)、代价为 \(\sqrt{(\Delta x)^2+(\Delta y)^2}\)。

求出最大流 \(\text{MF}\) 和此时的最小费用 \(\text{MC}\)。根据上面的分析,可以构成一棵二叉树当且仅当 \(\text{MF}=n-1\),此时的 \(\text{MC}\) 就是最小权值和。

// Problem: CF277E Binary Tree on Plane
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF277E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;
const ll N = 1e3+5, M = 3e6+5, inf = 0x3f3f3f3f3f3f3f3fll;

ll n, s, t, x[N], y[N], vis[N], flow[N], pre[N];
double dis[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Edge {
	ll v, w, nxt;
	double c;
	Edge(ll a=0, ll b=0, double c=0.0, ll d=0) : v(a), w(b), c(c), nxt(d) {}
}e[M];
ll h[N], ne = 1;
void add(ll u, ll v, ll w, double c) {
	e[++ne] = Edge(v, w, c, h[u]); h[u] = ne;
	e[++ne] = Edge(u, 0,-c, h[v]); h[v] = ne;
}
bool BellmanFord() {
	fill(dis, dis+1+t, 1e100);
	memset(vis, 0, sizeof(vis));
	memset(flow, 0x3f, sizeof(flow));
	queue<ll> q;
	dis[s] = 0.0;
	vis[s] = 1;
	pre[t] = -1;
	q.push(s);
	while(!q.empty()) {
		ll u = q.front(); q.pop();
		vis[u] = 0;
		for(ll i=h[u];i;i=e[i].nxt) {
			ll v = e[i].v, w = e[i].w;
			double c = e[i].c;
			if(w && dis[v] > dis[u] + c) {
				dis[v] = dis[u] + c;
				pre[v] = i;
				flow[v] = min(flow[u], w);
				if(!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return ~pre[t];
}
tuple<ll, double> MCMF() {
	ll maxflow = 0; double mincost = 0.0;
	while(BellmanFord()) {
		ll now = inf;
		for(ll u = t; u != s; u = e[pre[u]^1].v) chkmin(now, flow[u]);
		for(ll u = t; u != s; u = e[pre[u]^1].v) {
			e[pre[u]].w -= now;
			e[pre[u]^1].w += now;
			mincost += now * e[pre[u]].c;
		}
		maxflow += now;
	}
	return make_tuple(maxflow, mincost);
}
double dist(int i, int j) {
	double dx = x[i] - x[j], dy = y[i] - y[j];
	return sqrt(dx * dx + dy * dy);
}

int main() {
	scanf("%lld", &n);
	s = 2 * n + 1; t = 2 * n + 2;
	rep(i, 1, n) {
		scanf("%lld%lld", &x[i], &y[i]);
		add(s, i, 2, 0.0);
		add(i+n, t, 1, 0.0);
	}
	rep(i, 1, n) rep(j, 1, n) if(y[i] > y[j]) add(i, j+n, 1, dist(i, j));
	int maxflow; double mincost;
	tie(maxflow, mincost) = MCMF();
	if(maxflow < n - 1) puts("-1");
	else printf("%.15f\n", mincost);
	return 0;
}

标签:pre,题解,ll,vis,Plane,text,double,CF277E,dis
From: https://www.cnblogs.com/ruierqwq/p/CF-277E.html

相关文章

  • 题解:【CODE FESTIVAL 2016 Grand Final】90 and 270
    题目链接经典增量构造题。不妨从是否存在构造开始考虑:根据多边形内角和的公式容易得出给定的度数和必须等于\((n-2)\times180^{\circ}\),才有解。换一个角度思考,又因......
  • 【题解】P4707 重返现世
    隔壁友校的初一已经开始做这种题了,准老年选手感到恐惧。思路Min-Max容斥。首先考虑到\(|n-k|\leq10\),感觉有大力做法,考虑用Min-Max容斥求期望。设全集\(U\)......
  • [AHOI2009] 中国象棋 题解
    每行每列的炮数量\(\leq2\),那么整个图就可以被分解为一些环和链。考虑答案的二元生成函数,显然环和链分别的生成函数都是平凡的多项式,而答案的多项式无非是加起来后求exp......
  • 黑白树 题解
    看了半天题解代码大概明白他在干啥了。写篇题解总结一下。题面:一棵树,每个点黑色或白色,有权值。五个操作:改变一个点颜色。使点\(x\)所在的同色连通块权值加\(val\)。......
  • CF468E Permanent 题解
    考虑暴力状压DP。按行DP,记录列哪些被选过,可以做到\(O(2^kk^2)\)。注意到某一列扫完了之后这一列选没选过不重要,可以减少这里的状态。简单优化一下,每次选择最少的一列......
  • CF1033E 题解
    题意传送门交互题,给定一个简单连通图,你可以询问一个点集\(s\),返回其导出子图的边数。判断此图是否为二分图:若是,输出其中一部点的集合;否则输出任一个奇环。最多询问\(20......
  • Good Bye 2022 简要题解
    从这里开始比赛目录过气选手留下了只会套路的眼泪。sad......ProblemA KoxiaandWhiteboards相信大家都会.jpgCode#include<bits/stdc++.h>using......
  • 题解:【CF226D】The table
    题目链接调整构造。发现\(n\)和\(m\)较小只有\(100\),因此可以考虑尝试进行修改从而不断逼近答案。容易发现如果将某一行或列上的数字翻转,那么得到的新的和一定与原......
  • 【题解】ABC287
    \(\text{AtCoderBeginnerContest287}\)AMajority无意义题,问同意的是不是占半数以上。BPostalCard无意义题,对一个字符串集合开桶,对应匹配另一个字符串集合。CPa......
  • P3070 [USACO13JAN]Island Travels G 题解
    题目传送门一道耗费了本蒟蒻与某机房卷王半天的恶心题题目描述给定一个图,求每个X连通块之间的最短Hamilton路径。假如您不知道Hamilton路径是什么分析这题本质......