题目大意
有(n)个区间((1 leq n leq 200)),第(i)个区间覆盖((a_{i}, b_{i}))且有权值(w_{i})((1 leq a_{i} < b_{i} leq 100000),(1 leq w_{i} leq 100000)),每个点最多能被覆盖(k)次((1 leq k leq n)),求最大的权值和为多少。
题解
这里点的坐标很大,所以我们要先离散化,顺便把每个点按照坐标排序。
排完序后,我们可以从(a_{i})向(b_{i})连一条有向边,容量为(1),费用为(w_{i})。
同时,对于每个点(i)((0 leq i leq cnt),其中(cnt)表示离散化后的点数,点(0)为源点(s),点(cnt + 1)为汇点(t)),我们要从点(i)向点(i + 1)连一条有向边,容量为(k),费用为(0)。
建完图后,直接跑最大费用流即可。具体细节可以参考下面的代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX_N (209 + 5)
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
int to;
int weight;
int cost;
int next;
};
int T;
int n, k;
int s, t;
int hash[100005], cnt;
int h[MAX_N << 1], tot;
Edge e[MAX_N << 3];
int dis[MAX_N << 1];
int cur[MAX_N << 1];
bool inque[MAX_N << 1], vis[MAX_N << 1];
queue <int> q;
int maxflow, mincost;
inline void AddEdge(int u, int v, int w, int c)
{
e[++tot].to = v;
e[tot].weight = w;
e[tot].cost = c;
e[tot].next = h[u];
h[u] = tot;
return;
}
bool SPFA()
{
memset(dis, 0x3f, sizeof dis);
memset(inque, 0, sizeof inque);
memcpy(cur, h, sizeof cur);
q.push(s);
dis[s] = 0;
inque[s] = true;
int u, v, w, c;
while(!q.empty())
{
u = q.front();
q.pop();
inque[u] = false;
for(int i = h[u]; i; i = e[i].next)
{
v = e[i].to;
w = e[i].weight;
c = e[i].cost;
if(dis[v] > dis[u] + c && w)
{
dis[v] = dis[u] + c;
if(!inque[v])
{
inque[v] = true;
q.push(v);
}
}
}
}
return dis[t] != INF;
}
int DFS(int u, int flow)
{
vis[u] = true;
if(u == t)
{
maxflow += flow;
mincost += flow * dis[t];
return flow;
}
int v, w, c;
int tmp, sum = 0;
for(int i = cur[u]; i && sum < flow; i = e[i].next)
{
cur[u] = i;
v = e[i].to;
w = e[i].weight;
c = e[i].cost;
if(!vis[v] && dis[v] == dis[u] + c && w)
{
tmp = DFS(v, min(flow - sum, w));
e[i].weight -= tmp;
e[i ^ 1].weight += tmp;
sum += tmp;
}
}
return sum;
}
void Dinic()
{
while(SPFA())
{
do
{
memset(vis, 0, sizeof vis);
DFS(s, k);
}
while(vis[t]);
}
return;
}
int main()
{
scanf("%d", &T);
while(T--)
{
memset(h, 0, sizeof h);
memset(e, 0, sizeof e);
memset(hash, 0, sizeof hash);
cnt = 0;
tot = 1;
maxflow = mincost = 0;
scanf("%d%d", &n, &k);
int u[MAX_N], v[MAX_N], c[MAX_N];
int a[MAX_N << 1];
for(int i = 1; i <= n; ++i)
{
scanf("%d%d%d", &u[i], &v[i], &c[i]);
a[i] = u[i];
a[i + n] = v[i];
}
sort(a + 1, a + n + n + 1);
for(int i = 1; i <= n + n; ++i)
{
if(a[i] != a[i - 1]) hash[a[i]] = ++cnt;
}
for(int i = 1; i <= n; ++i)
{
u[i] = hash[u[i]];
v[i] = hash[v[i]];
AddEdge(u[i], v[i], 1, -c[i]);
AddEdge(v[i], u[i], 0, c[i]);
}
for(int i = 1; i < cnt; ++i)
{
AddEdge(i, i + 1, k, 0);
AddEdge(i + 1, i, 0, 0);
}
s = 0;
t = cnt + 1;
AddEdge(s, 1, k, 0);
AddEdge(1, s, 0, 0);
AddEdge(cnt, t, k, 0);
AddEdge(t, cnt, 0, k);
Dinic();
printf("%d
", -mincost);
}
return 0;
}