水题笔记_ 最长k可重区间集问题 [网络流24, 费用流, 清奇脑回路]

考虑把一条线段转化成一个点

懵逼的 题目

传送至 Luogu

扯淡的 题解

不会, 看的书,
显然这么大的坐标范围而线段数却并不多, 所以需要离散化端点, 注意这个题的线段是开区间比较恶心人, 需要判断两个端点的坐标相同的时候端点是左端点还是右端点

然后考虑连边, 像下图一样:

  • 给原先在一个线段上的两个端点两边, 容量为1, cost为线段的长度
  • 给相邻的两个端点连边, 容量为INF, cost = 0
  • s连到最左边的端点上, 容量为k, cost = 0, t连在最右边的端点上, 容量为INF, cost = 0

连边

解释:
选一条线段就一定会选上她的两个端点, 所以对于一条线段, 都有选一条和不选两种艹作,
所以一条线段上的两个端点之间连边的容量为1, 选了这个线段就可以得到对答案有cost的贡献
相邻的两个端点连容量为0的边就是可以跳过这条边
显然对于覆盖点的次数, 线段端点被覆盖的次数是最多的(先看成闭区间), 所以只要保证每一个端点被选的次数不超过k次就可以了, 而上面这样连边, 一定会保证在增广一次后, 经过的线段都是不相交的, 因为边的方向都是向右, 选了一条线段, 左端点在这条线段右端点左边的点就都不会在这次增广中被选中了, 而一次增广最多只会增加1单位的流量, 所以s出发的边容量为k就保证了没有覆盖数超过k的端点, 也就没有覆盖数超过k的点…

Emmmm…差不多就是酱

但你以为就结束了嘛…
这个题…首先数据有左端点在右端点之后输入的…还有重复的线段…Emmmmmmmm….

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXD (500 + 5)
#define MAXN (MAXD << 1)
#define MAXM (MAXN << 3)
#define INF (0x7ffffff)
#define rev(a) (((a - 1) ^ 1) + 1)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define mabs(a) ((a) > 0 ? (a) : (-(a)))
#define swap(a, b) {int t = a; a = b; b = t;}
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from;
int to;
int next;
int cap;
int flow;
int cost;
edg(){}
edg(int a, int b, int c, int d, int e, int f): from(a), to(b), next(c), cap(d), flow(e), cost(f) {}
}b[MAXM << 1];
int g[MAXN];
int cntb = 0;

struct node
{
int wz;
int bh;
int cost;
bool isl;
int ri;
node(){}
node(int a, int b, int c, bool d): wz(a), bh(b), cost(c), isl(d) {}
}a[MAXD << 1];

int xdn;
int ans;
int pre[MAXN];
int k;
bool cmp(node, node);
void adn(int, int, int, int);
void init();
void solve();
int spfa();
int main()
{
scanf("%d%d", &xdn, &k);
pair<int, int> youdu[MAXD];
for (int i = 1; i <= xdn; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
if (sry < srx)
swap(srx, sry);
youdu[i] = make_pair(srx, sry);
}
xdn = unique(youdu + 1, youdu + xdn + 1) - youdu;
for (int i = 1; i <= xdn; i++)
{
int srx = youdu[i].first;
int sry = youdu[i].second;
a[i] = node(srx, i, sry - srx, true);
a[i + xdn] = node(sry, i, sry - srx, false);
}
init();
solve();
printf("%d\n", ans);
return 0;
}
bool cmp(node x, node y)
{
if (x.wz == y.wz)
{
if (x.isl)
{
return !y.isl;
}
else
{
return y.isl;
}
}
return x.wz < y.wz;
}
void adn(int from, int to, int cap, int cost)
{
b[++cntb] = edg(from, to, g[from], cap, 0, cost);
g[from] = cntb;
}
void init()
{
sort(a + 1, a + (xdn << 1), cmp);
int bh[MAXD];
adn(s, 1, k, 0);
adn(1, s, 0, 0);
for (int i = 1; i <= (xdn << 1); i++)
{
if (a[i].isl)
bh[a[i].bh] = i;
else
{
adn(bh[a[i].bh], i, 1, a[i].cost);
adn(i, bh[a[i].bh], 0, -a[i].cost);
}
if (i < (xdn << 1))
{
adn(i, i + 1, INF, 0);
adn(i + 1, i, 0, 0);
}
else
{
adn(i, t, INF, 0);
adn(t, i, 0, 0);
}
}
}
void solve()
{
while (true)
{
int zl = spfa();
if (!zl)
return ;
for (int i = t; i != s; i = b[pre[i]].from)
{
b[pre[i]].flow += zl;
b[rev(pre[i])].flow -= zl;
ans += zl * b[pre[i]].cost;
}
}
}
int spfa()
{
bool inq[MAXN];
int dis[MAXN];
int at[MAXN];
memset(inq, false, sizeof(inq));
memset(dis, 0, sizeof(dis));
memset(at, 0, sizeof(at));
queue<int> q;
q.push(s);
inq[s] = true;
at[s] = INF;
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
inq[dq] = false;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] < dis[dq] + b[i].cost)
{
dis[b[i].to] = dis[dq] + b[i].cost;
at[b[i].to] = min(at[dq], b[i].cap - b[i].flow);
pre[b[i].to] = i;
if (!inq[b[i].to])
{
q.push(b[i].to);
inq[b[i].to] = true;
}
}
}
}
return at[t];
}

/*
4 2
1 7
6 8
7 10
9 13
*/

By Cansult

最近状态不佳 要加油了…