2013
12-09

# Intervals

You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.

Write a program that:

> reads the number of intervals, their endpoints and integers c1, …, cn from the standard input,

> computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i = 1, 2, …, n,

> writes the answer to the standard output

The first line of the input contains an integer n (1 <= n <= 50 000) – the number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50 000 and 1 <= ci <= bi – ai + 1.

Process to the end of file.

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, …, n.

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

6

Problem – 1384

好歹用了一天，也算是看懂了差分约束的原理，做出第一条查分约束了。

题意是告诉你一些区间中最少有多少元素，最少需要多少个元素才能满足所有要求。

构图的方法是，(a)->(b+1)=c。还有就是所有的相邻的点都要连上(i+1)->(i)=0，(i)->(i+1)=-1。因为我对点离散了，所以就变成(rx[i])->(rx[i+1])=rx[i]-rx[i+1]。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

const int N = 55555;
const int INF = 0x55555555;
struct Edge {
int id, nx, val;
Edge() {}
Edge(int id, int nx, int val) : id(id), nx(nx), val(val) {}
} edge[N << 2];
int eh[N], ec;

void init() {
ec = 0;
memset(eh, -1, sizeof(eh));
}

void addedge(int u, int v, int w) {
edge[ec] = Edge(v, eh[u], w);
eh[u] = ec++;
}

int rx[N << 1], dis[N];
bool vis[N];
queue<int> Q;

void spfa(int s) {
while (!Q.empty()) Q.pop();
memset(vis, 0, sizeof(vis));
for (int i = 0; i < N; i++) dis[i] = -INF;
Q.push(s);
vis[s] = true;
dis[s] = 0;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
vis[cur] = false;
for (int t = eh[cur]; ~t; t = edge[t].nx) {
if (dis[edge[t].id] < dis[cur] + edge[t].val) {
dis[edge[t].id] = dis[cur] + edge[t].val;
if (vis[edge[t].id]) continue;
Q.push(edge[t].id);
vis[edge[t].id] = true;
}
}
}
}

int main() {
//    freopen("in", "r", stdin);
int n, x, y, z;
while (~scanf("%d", &n)) {
init();
int cnt = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
rx[cnt++] = x;
rx[cnt++] = y + 1;
}
sort(rx, rx + cnt);
cnt = unique(rx, rx + cnt) - rx;
for (int i = 1; i < cnt; i++) addedge(rx[i], rx[i - 1], rx[i - 1] - rx[i]), addedge(rx[i - 1], rx[i], 0);
spfa(rx[0]);
printf("%d\n", dis[rx[cnt - 1]]);
}
return 0;
}

跑的比较慢，元素进队的次数比较多。用固定大小的queue因为越界WA了好多次。

——written by Lyon

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

3. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？