luogu P3357 最长k可重线段集问题
2024-10-08 12:45:22
这题和3358一模一样,建模形式直接不用变,就两点不一样,一是len变化了,加入y后再更新即可,还有就是可能会出现x0=x1的情况,即一条开线段垂直x轴,如果我们依旧按照上一题的建图方法,就会出现负权环,无法跑出答案,我们就可以把一个点拆成入点和出点,这样无论是否是不是垂直都可以一样建,注意开long long,不开long long可能只有9分
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL; const int maxm = 1e5+;
const LL INF = 0x3f3f3f3f3f3f3f3f; struct edge{
LL u, v, cap, flow, cost, nex;
} edges[maxm]; struct Points{
LL l, r, len;
} point[]; LL head[maxm], cur[maxm], cnt, fa[<<], n, d[<<], allx[];
bool inq[<<]; void init() {
memset(head, -, sizeof(head));
} void add(int u, int v, LL cap, LL cost) {
edges[cnt] = edge{u, v, cap, , cost, head[u]};
head[u] = cnt++;
} void addedge(int u, int v, LL cap, LL cost) {
add(u, v, cap, cost), add(v, u, , -cost);
} bool spfa(int s, int t, int &flow, LL &cost) {
for(int i = ; i <= n+; ++i) d[i] = INF; //init()
memset(inq, false, sizeof(inq));
d[s] = , inq[s] = true;
fa[s] = -, cur[s] = INF;
queue<int> q;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int i = head[u]; i != -; i = edges[i].nex) {
edge& now = edges[i];
int v = now.v;
if(now.cap > now.flow && d[v] > d[u] + now.cost) {
d[v] = d[u] + now.cost;
fa[v] = i;
cur[v] = min(cur[u], now.cap - now.flow);
if(!inq[v]) {q.push(v); inq[v] = true;}
}
}
}
if(d[t] == INF) return false;
flow += cur[t];
cost += 1LL*d[t]*cur[t];
for(int u = t; u != s; u = edges[fa[u]].u) {
edges[fa[u]].flow += cur[t];
edges[fa[u]^].flow -= cur[t];
}
return true;
} int MincostMaxflow(int s, int t, LL &cost) {
cost = ;
int flow = ;
while(spfa(s, t, flow, cost));
return flow;
} void run_case() {
init();
LL l, r, y1, y2;
int k, xcnt = ;
cin >> n >> k;
for(int i = ; i <= n; ++i) {
cin >> l >> y1 >> r >> y2;
LL tmp = 1LL*floor(sqrt(sqr(r-l)+sqr(y2-y1)));
if(l > r) swap(l, r);
l <<= , r <<= ;
if(l == r) r|=; else l|=;
allx[++xcnt] = l, allx[++xcnt] = r, point[i] = Points{l, r, tmp};
}
sort(allx+,allx++xcnt);
int len = unique(allx+,allx++xcnt)-allx;
for(int i = ; i <= n; ++i) {
point[i].l = lower_bound(allx+,allx+len,point[i].l)-allx;
point[i].r = lower_bound(allx+,allx+len,point[i].r)-allx;
}
for(int i = ; i < len-; ++i)
addedge(i, i+, INF, );
int s = , t = len;
for(int i = ; i <= n; ++i) {
addedge(point[i].l, point[i].r, , -point[i].len);
}
addedge(s, , k, ), addedge(len-, t, k, );
LL cost = ;
n = len;
MincostMaxflow(s, t, cost);
cout << -cost;
} int main() {
ios::sync_with_stdio(false), cin.tie();
run_case();
cout.flush();
return ;
}
最新文章
- Hypernetes简介
- HTML问题集锦
- python 函数基础介绍
- BZOJ1520 [POI2006]Szk-Schools
- 使用AnkhSvn-2.5.12478.msi管理vs2013代码的工具安装步骤使用
- LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面
- Generate the Jobs script from msdb Database
- dephi WaitForMultipleObjects 用法
- 不使用var定义变量和使用var的区别
- Java基础知识强化之集合框架笔记21:数据结构之 数组 和 链表
- __attribute__ ((section(";.text";)))的测试
- xcode中折叠打开代码
- 使用redis做mybaties的二级缓存(2)-Mybatis 二级缓存小心使用
- 51nod 1118 机器人走方格 解题思路:动态规划 &; 1119 机器人走方格 V2 解题思路:根据杨辉三角转化问题为组合数和求逆元问题
- python异步并发模块concurrent.futures入门详解
- Loadrunner11中webservice协议脚本总结
- numpy数据集练习
- sonarqube安装的坑
- pt-query-digest简介使用
- 利用DotNetZip服务端压缩文件并下载