題意：
? ? ? 給你一個(gè)集合，然后有如下輸入，a ,b ,c表示在范圍[a,b]里面有至少有c個(gè)元素，最后問你整個(gè)集合最少多少個(gè)元素。

思路：
? ? ? 和HDU1384一模一樣，首先這個(gè)題目可以用差分約束來(lái)解決，是大于等于所以跑最長(zhǎng)路（如果非要跑最短路建-權(quán)也可以），說下建圖，首先我們把每個(gè)區(qū)間抽象出來(lái)，區(qū)間的兩個(gè)端點(diǎn)之間的元素個(gè)數(shù) [a ,b]?= c 可以抽象成 點(diǎn)a,和點(diǎn)(b + 1)之間的距離 大于等于c，那么這樣就可以把輸入建進(jìn)去了，還有個(gè)關(guān)鍵的地方就是題目的隱含條件，一般的查分約束的關(guān)鍵都是在于找隱含條件，這個(gè)題目的隱含條件就是相鄰的

兩個(gè)點(diǎn)的元素個(gè)數(shù) >= 0 && <= 1，其他的沒啥了。

#include<stdio.h> #include<string.h> #include<queue>#define N_node 55000 #define N_edge 210000 #define INF 100000000000000using namespace std;typedef struct { int to ,next;__int64 cost; }STAR;STAR E[N_edge]; int list[N_node] ,tot; __int64 s_x[N_node];void add(int a ,int b ,__int64 c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }bool spfa(int s ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = -INF;int mark[N_node] = {0};int in[N_node] = {0};s_x[s] = 0;mark[s] = in[s] = 1;queue<int>q;q.push(s);while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] < s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;q.push(xin);if(++in[xin] > n) return 0;}}}}return 1; }int maxx(int x ,int y) {return x > y ? x : y; } int minn(int x ,int y) {return x < y ? x : y; }int main () {int n ,a ,b ,i;__int64 c;while(~scanf("%d" ,&n)){memset(list ,0 ,sizeof(list));tot = 1;int Max = 0 ,Min = 100000000;for(i = 1 ;i <= n ;i ++){scanf("%d %d %I64d" ,&a ,&b ,&c);b ++;add(a ,b ,c);Max = maxx(Max ,b);Min = minn(Min ,a);}for(i = Min ;i <= Max ;i ++){add(i - 1 ,i ,0);add(i ,i - 1 ,-1);}spfa(Min ,Max);printf("%I64d\n" ,s_x[Max]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1201 差分约束（集合最小元素个数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。