「网络流 24 题」最长 k 可重区间集_综合

#6014. 「网络流 24 题」最长 k 可重区间集

内存限制：256 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者：匿名

题目描述

给定实直线 L L L 上 n n n 个开区间组成的集合 I I I，和一个正整数 k k k，试设计一个算法，从开区间集合 I I I 中选取出开区间集合 S?I S \subseteq I S?I，使得在实直线 L L L 的任何一点 x x x，S S S 中包含点 x x x 的开区间个数不超过 k k k。且 ∑z∈S∣z∣ \sum\limits_{z \in S} | z | z∈S∑?∣z∣ 达到最大。这样的集合 S S S 称为开区间集合 I I I 的最长 k k k 可重区间集。∑z∈S∣z∣ \sum\limits_{z \in S} | z | z∈S∑?∣z∣ 称为最长 k k k 可重区间集的长度。

对于给定的开区间集合 I I I 和正整数 k k k，计算开区间集合 I I I 的最长 k k k 可重区间集的长度。

输入格式

文件的第 1 1 1 行有 2 2 2 个正整数 n n n 和 k k k，分别表示开区间的个数和开区间的可重迭数。
接下来的 n n n 行，每行有 2 2 2 个整数 li l_i li? 和 ri r_i ri?，表示开区间的左右端点坐标，注意可能有 li>ri l_i > r_i li?>ri?，此时请将其交换。

输出格式

输出最长 k k k 可重区间集的长度。

样例

样例输入

样例输出

题意：区间覆盖费用流。注意垂直的时候处理。可以先把所有的坐标*2，然后左端点-1，不影响最终答案！

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
//headconst int maxn = 1e6+11;int ver[maxn],edge[maxn],cost[maxn],nxt[maxn],head[maxn],cnt;
int _edge[maxn];
int d[maxn],incf[maxn],pre[maxn],v[maxn];
int n,m,s,t,ans,maxflow;void add(int x,int y,int z,int c)
{ver[++cnt] = y, edge[cnt] = z;cost[cnt] = c; nxt[cnt]  = head[x];head[x] = cnt;ver[++cnt] = x; edge[cnt] = 0;cost[cnt] = -c;nxt[cnt] = head[y];head[y] = cnt;
}bool spfa()
{queue<int>q;memset(d,0xcf,sizeof d);ms(v);q.push(s);d[s] = 0;v[s] = 1;incf[s] = inf;while(q.size()){int x = q.front();q.pop();v[x] = 0;for(int i = head[x];i;i=nxt[i]){if(!edge[i])continue;int y = ver[i];if(d[y] < d[x] + cost[i]){d[y] = d[x] + cost[i];incf[y] = min(incf[x],edge[i]);pre[y] = i;if(!v[y])q.push(y),v[y] = 1;}}}if(d[t] == 0xcfcfcfcf)return false;return true;
}void update()
{int x = t;while(x != s){int i = pre[x];edge[i] -= incf[t];edge[i^1] += incf[t];x = ver[i^1];}maxflow += incf[t];ans += d[t] * incf[t];
}int w[maxn],a[maxn],l[maxn],r[maxn];int main()
{int n,k;cin >> n >> k;int tot = 0;cnt = 1;rep(i,1,n+1){int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);w[i] = sqrt((ll)(x1-x2)*(x1-x2) + (ll)(y1-y2)*(y1-y2));l[i] = x1 << 1, r[i] = x2 << 1;if(x1 == x2)l[i]--;if(l[i] > r[i])swap(l[i],r[i]);a[++tot] = l[i],a[++tot] = r[i];}sort(a+1,a+1+tot),tot = unique(a+1,a+1+tot)-a-1;s = tot+1,t = s+1;add(s,1,k,0),add(tot,t,k,0);rep(i,1,tot)add(i,i+1,inf,0);rep(i,1,n+1){int L = lower_bound(a+1,a+1+tot,l[i]) - a;int R = lower_bound(a+1,a+1+tot,r[i]) - a;add(L,R,1,w[i]); } while(spfa())update();   cout << ans << endl;}