Problem： 在SD食堂，所有的座位是一行一行的排列。现在有N个座位排成一行，依次编号1,2,…,N，每个座位只能坐一个人，现在L想数一下有多少个人坐着，一个一个数太慢了，L决定只选择M段连续的座位，对每段分别数出人数。由于食堂噪音十分嘈杂，L无法专心，可能有输错了。但是L认为没有数漏，最多是重复计数导致的。现在他把得到的数据给你，希望你帮他算出，一共最多有多少人。(n,m<=100000)
输入 第一行2个整数N,M，分别是座位数量，和L分成M段
接下来M行，每行3个整数，l,r,k，表示L数了l到r这一段的座位，他数出的结构是k
输出 一行表示答案
Solution： 考虑差分约束 明确所求：最大值；因此跑最短路，把所有不等式的符号变为<=，从小的向大的连边。 当然，差分约束不能忘了要分析两两元素之间隐晦的关系，比如这道题，我们会发现1>=sum[i]-sum[i-1]>=0，需要预连边。
Code
#include<bits/stdc++.h> #define N 200005 using namespace std; int n,m,sum[N],tot,first[N],zdl[N]; bool inque[N]; struct node { int to,next,val; }edge[2*N]; inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } inline void spfa(int s) { queue <int> q; q.push(s); inque[s]=true; zdl[s]=0; while(!q.empty()) { int now=q.front(); q.pop(); inque[now]=false; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(zdl[now]+edge[u].val<zdl[vis]) { zdl[vis]=zdl[now]+edge[u].val; if(!inque[vis]) { inque[vis]=true; q.push(vis); } } } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); memset(zdl,127,sizeof(zdl)); cin>>n>>m; for(int i=1;i<=n;i++) { addedge(i,i-1,0); addedge(i-1,i,1); } for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; addedge(x-1,y,z); } spfa(0); cout<<zdl[n]; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9391498.html
相关资源：2015重庆市NOIP模拟赛题目 数据