?

差分約束基本題型：

????? 給出一個序列，1至n這n個數字，然后已知從i 到j 的數字和至多a、至少b，給出這么一組，然后求每個數字最小為多少，或者求總和最小為多少。

????? 于是構造，設s[i]為0到i的和，那么s[1]即為第一個數字，s[2]-s[1]即為第二個數字，于是給出的條件轉換為：

s[i] - s[j] >= b

s[i] - s[j] <= a

s[i] - s[i-1] >= 0

s[i] - s[i-1] <= V （*如果是1到n這n個容器，每個容器有容量，或者特殊情況n個布爾值，那么需要加上這個限制條件）

?

題目大意：

給出一些區間[ai,bi]和每個區間最少需要幾個點ci，然后問總共最少需要幾個點滿足所有區間的要求。比如給出1 5 2和 4 6 2，就是說1到5需要2個點，4到6需要2個點，那么最少需要2個點就可以滿足條件了。

?

思路：

這個就是上面說的布爾值了，抽象成

s[bi] - s[ai-1] >= ci?

s[i] - s[i-1] >= 0?

?s[i] - s[i-1] <= 1

注意邊界是s[bi]-s[ai-1]，避免重復。

然后進行差分約束求最長路。另外，此題不需要判斷是否不滿足條件，即存在環。另外，全部初始化為0即可，或者除起始點為0其余點為-INF，然后松弛的時候判斷一下。

PS：昨天去網上搜資料，打印資料，看了一天的差分約束，理解了大概思路，沒實踐。今天懷著忐忑的心情，建圖，寫SPFA，寫完之后對比測試數據，一樣。交第一遍，RE，立馬將數組開到50010，第二遍，RE，想起昨天網上看的資料，一般數組大小都是4*SIZE左右，于是果斷將數組開到200010，看Status，AC了。還得多寫寫差分約束的題。

有關差分約束的簡單證明：http://hi.baidu.com/jffifa/item/ef628c50d37345dcd58bac44

差分約束求的是什么？http://whiteath.weebly.com/1/post/2010/11/2.html

ZOJ差分約束具體應用：http://whiteath.weebly.com/3/post/2010/12/zoj-150814551420.html

?

CODE：

?

#include?<iostream>
#include?<cstdio>
#include?<queue>
using?namespace?std;

const?int?SIZE?=?50010;
const?int?INF?=?0x3f3f3f3f;

int?u[4*SIZE],?v[4*SIZE],?w[4*SIZE],?next[4*SIZE];
int?first[SIZE],?d[SIZE];
int?cnt,?Min,?Max;

void?read_graph(int?u1,?int?v1,?int?w1)
{
????u[cnt]?=?u1;?v[cnt]?=?v1;?w[cnt]?=?w1;
????next[cnt]?=?first[u[cnt]];
????first[u[cnt]]?=?cnt;
????cnt++;
}

void?spfa(int?src)
{
????queue<int>?q;
????bool?inq[SIZE]?=?{0};
????for(int?i?=?Min;?i?<=?Max;?i++)?d[i]?=?(i?==?Min)??0:-INF;
????q.push(Min);
????while(!q.empty())
????{
????????int?x?=?q.front();?q.pop();
????????inq[x]?=?0;
????????for(int?e?=?first[x];?e!=-1;?e?=?next[e])?if(d[v[e]]?<?d[x]+w[e])?//最長路三角不等式
????????{
???????????d[v[e]]?=?d[x]?+?w[e];
???????????if(!inq[v[e]])
???????????{
???????????????inq[v[e]]?=?1;
???????????????q.push(v[e]);
???????????}
????????}
????}
????printf("%d\n",?d[Max]);
}

void?init()
{
????memset(u,?0,?sizeof(u));
????memset(v,?0,?sizeof(v));
????memset(w,?INF,?sizeof(w));
????memset(first,?-1,?sizeof(first));
????memset(next,?0,?sizeof(next));
????Min?=?INF;
????Max?=?0;
}

int?main()
{
????int?n;
????while(~scanf("%d",?&n))
????{
????????init();
????????cnt?=?0;
????????while(n--)
????????{
????????????int?x,?y,?z;
????????????scanf("%d%d%d",?&x,?&y,?&z);
????????????x++;?y++;
????????????Max?=?max(Max,?y);
????????????Min?=?min(Min,?x-1);
????????????read_graph(x-1,?y,?z);
????????}
????????for(int?i?=?Min;?i?<=?Max;?i++)
????????{
????????????read_graph(i-1,?i,?0);
????????????read_graph(i,?i-1,?-1);
????????}
????????spfa(Min);
????}
}

?

轉載于:https://www.cnblogs.com/g0feng/archive/2012/09/14/2684956.html

總結

以上是生活随笔為你收集整理的Hdu 1384 Intervals的全部內容，希望文章能夠幫你解決所遇到的問題。

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