題目鏈接：點擊查看

題目大意：給定n個閉區間[ai,bi]和n個整數ci，你需要構造一個整數集合Z，使得Z中滿足所有的ai<=x<=bi的整數不少于ci個，求出這樣的整數集合Z最少包含多少個數

題目分析：因為這個題目的數最多只有5e4個，我們可以設一個函數S[k]，表示0~k中最少選出多少個整數才能滿足題意，則我們可以寫出約束方程：

S[bi]-S[ai-1]>=ci，滿足題目條件

1>=S[k]-S[k-1]>=0，因為根據設計函數的本身性質，每個數k只有選或不選兩種狀態，故相鄰兩個函數之間的差非0即1

進行化簡一下就能進一步得到差分約束方程了：

S[k]>=S[k-1]+0

S[k-1]>=S[k]+(-1)

S[bi]>=S[ai-1]+ci

根據上面的方程建邊然后跑最長路的spfa就能得到答案了，設mmin為最小的a-1，mmax為最大的b，則答案就是以mmin為起點的單源最長路跑完后的d[mmax]了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100;//頂點數 const int M=2e5+100;//邊數 struct Edge {int to,w,next; }edge[M];int head[N],d[N],cnt;//鏈式前向星 bool vis[N];void addedge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++; }void spfa(int st) {memset(vis,false,sizeof(vis));memset(d,0xcf,sizeof(d));d[st]=0;vis[st]=true;queue<int>q;q.push(st);while(q.size()){int u=q.front();q.pop();vis[u]=false;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(d[v]<d[u]+w){d[v]=d[u]+w;if(!vis[v]){q.push(v);vis[v]=true;}}}} }void init() {memset(head,-1,sizeof(head));cnt=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF){init();int mmax=0,mmin=inf;for(int i=1;i<=n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);a++,b++;mmax=max(mmax,b);mmin=min(mmin,a-1);addedge(a-1,b,c);}for(int i=mmin;i<mmax;i++){addedge(i,i+1,0);addedge(i+1,i,-1);}spfa(mmin);printf("%d\n",d[mmax]);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 1201 Intervals(差分约束+最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。