费用流。
可以将原问题转化为类似于匹配的问题,只不过这种匹配并不是一对一的。具体地,将每个点 \(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