保龄了！因为图论只自学过最短路
Problem 1. 礼物分配
为了庆祝大佬 \(wxh\) 的生日，众人决定为他准备礼物。现在有 \(n\) 个礼品盒排成一行，从 \(1\) 到 n 编号，每个礼品盒中可能有 \(1\) 个或 \(0\) 个礼品。大佬 \(wxh\) 提出了 \(m\) 个要求，形如“第 \(l[i]\) 到第 \(r[i]\) 个礼品盒当中至少有 \(c[i]\) 个礼品”。现在众人想知道，为了满足这些要求，所需准备的最少礼品数。
Input
第一行两个整数 \(n,m\)，接下来 \(m\) 行每行三个整数 \(l[i],r[i],c[i]\)。
Output
一行一个整数代表答案。
Note
对于 30%的数据，\(n,m \leq 10\)。
对于所有数据，\(n\leq1000,m\leq10000,1 \leq l[i],r[i] \leq n,0\leq c[i]\leq r[i]-l[i]+1\)
分析
差分约束。
把题目条件转化为对于前缀和 \(sum[r_i] - sum[l_i-1] \ge c_i\) ，即 \(sum[l_i-1]-sum[r]\le -c_i\) 建出对应边 \((r_i,l_i-1,-c_i)\) ;
注意到前缀和又另一组隐藏性质 \(0\le sum[i+1]-sum[i]\le1\) 建出对应边 \((i+1,i,0) 和 (i,i+1,1)\)；
最后再连出从超级源点出发的各点 \((s,i,0)\);
建完图直接SPFA跑最短路，输出 \(sum[n]-sum[0]\) 即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int f = 1, otto = 0;
char a = getchar();
while(!isdigit(a)) {
if(a == '-') f = -1;
a = getchar();
}
while(isdigit(a)) {
otto = (otto << 1) + (otto << 3) + (a ^ 48);
a = getchar();
}
return f * otto;
}
const int maxn = 1e3 + 10, maxm = 1e4 + 10;
struct edge{
int v, nxt, w;
}e[maxm << 1];
int head[maxm], tot = 0;
void add(int u, int v, int w) {
e[++tot].nxt = head[u];
head[u] = tot;
e[tot].v = v;
e[tot].w = w;
}
queue<int> q;
int s, vis[maxn], d[maxn];
void spfa() {
memset(d, 0x3f, sizeof d);
d[s] = 0;
vis[s] = 1;
q.push(s);
while(q.size()) {
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if(d[u] + w < d[v]) {
d[v] = d[u] + w;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return;
}
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
int n = read(), m = read();
for(int i = 1; i <= m; i++) {
int l = read(), r = read(), c = read();
add(r, l - 1, -c);
}
for(int i = 0; i <= n; i++) {
add(i + 1, i, 0); add(i, i + 1, 1);
}
s = n + 1;
for(int i = 1; i <= n; i++) add(s, i, 0);
spfa();
printf("%d", d[n] - d[0]);
return 0;
}
Problem 2.
Input
Output
Note
分析
AC代码：
Problem 3.
Input
Output
Note
分析
AC代码：
Problem 4.
Input
Output
Note
分析
AC代码：