题目大意

有\(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\n", -mincost);

    }

    return 0;

}

巴特西

【题解】Intervals

题目大意

题解

最新文章

热门文章