当前位置：首页 > news >正文

【一本通】intervals

news 来源：原创 2025/6/26 4:15:09

【一本通】intervals

💐The Begin💐点点关注，收藏不迷路💐

给出n个闭区间[ai,bi]和n个整数c1,……,cn。令Z表示一个整数集合，Z集合中最少要包含多少个整数可以使得每个区[ai,bi]都至少有ci个整数位于Z集合中。

输入

第一行一个整数n，表示区间数量。接下来n行，每行ai，bi，ci三个整数描述一个区间[ai,bi]要用ci个整数在Z集合中。

输出

输出Z集合的最小大小.

样例输入

样例输出

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 50010
#define INF 0x3f3f3f3f

// 定义结构体表示边，用于构建图
typedef struct Edge {
    int v;
    int w;
    struct Edge *next;
} Edge;

// 定义结构体表示图
typedef struct Graph {
Edge *head[MAXN];
} Graph;

// 创建边的函数
Edge *createEdge(int v, int w) {
    Edge e = (Edge )malloc(sizeof(Edge));
    e->v = v;
    e->w = w;
    e->next = NULL;
    return e;
}

// 向图中添加边的函数
void addEdge(Graph *g, int u, int v, int w) {
    Edge *e = createEdge(v, w);
    e->next = g->head[u];
    g->head[u] = e;
}

// 初始化图的函数
void initGraph(Graph *g) {
    for (int i = 0; i < MAXN; i++) {
        g->head[i] = NULL;
    }
}

// 求最长路的函数（这里使用SPFA算法实现）
int spfa(Graph *g, int n, int start, int *dis) {
    int inQueue[MAXN] = {0};
    int count[MAXN] = {0};
    int queue[MAXN];
    int front = 0, rear = 0;

    for (int i = 0; i <= n; i++) {
        dis[i] = -INF;
    }
    dis[start] = 0;
    inQueue[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        int u = queue[front++];
        inQueue[u] = 0;
        Edge *e = g->head[u];
        while (e) {
            int v = e->v;
            int w = e->w;
            if (dis[v] < dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inQueue[v]) {
                    inQueue[v] = 1;
                    // SLF优化，距离比队首大（求最长路情况）则插入队首
                    if (dis[v] > dis[queue[front]] && front < rear) {
                        // 移动元素，腾出队首位置插入当前节点
                        for (int i = rear; i > front; i–) {
                            queue[i] = queue[i - 1];
                        }
                        queue[front] = v;
                        rear++;
                    } else {
                        queue[rear++] = v;
                    }
                    count[v]++;
                    if (count[v] > n) {
                        return -1;  // 存在正环，无解
                    }
                }
            }
            e = e->next;
        }
    }
    return 0;
}

int main() {
    int n;
    scanf(“%d”, &n);
    Graph g;
    initGraph(&g);
    int maxRight = 0;
    // 读入区间信息，同时构建差分约束的图，并记录最右边界
    for (int i = 0; i < n; i++) {
        int ai, bi, ci;
        scanf(“%d %d %d”, &ai, &bi, &ci);
        addEdge(&g, ai, bi + 1, ci);
        if (bi > maxRight) {
            maxRight = bi;
        }
    }
    // 添加额外的边构建完整的差分约束图
    for (int i = 1; i <= maxRight; i++) {
        addEdge(&g, i, i + 1, 0);
        addEdge(&g, i + 1, i, -1);
    }
    int dis[MAXN];
    spfa(&g, maxRight + 1, 1, dis);
    printf(“%d\n”, dis[maxRight + 1]);
    return 0;
}

在这里插入图片描述

💐The End💐点点关注，收藏不迷路💐

【一本通】intervals

相关文章：