類型：給出一些形如a?b<=k的不等式（或a?b>=k或a?b<k或a?b>k等），問是否有解【是否有負環】或求差的極值【最短/長路徑】。
例子：b?a<=k1，c?b<=k2，c?a<=k3。將a，b，c轉換為節點；k1，k2，k3轉換為邊權；減數指向被減數，形成一個有向圖：

由題可得（b?a）?+?（c?b）?<=?k1+k2，c?a<=k1+k2。比較k1+k2與k3，其中較小者就是c?a的最大值。
由此我們可以得知求差的最大值，即上限被約束，此時我們拿最小的限制，也就是跑最短路；反之，求差的最小值，下限被約束，我們跑最長路。
跑最短路時：d[v]<=d[u]+w
跑最長路時：d[v]>=d[u]+w
路徑中可能會存在負邊，用SPFA跑。判斷負環，最短最長路均可

題意：

[a,b]區間內有>=c個數，計算集合里至少多個元素

思路：

因為數據范圍?0 <= ai <= bi <= 50000，可以設s[i]為i之前元素個數【不含i】,將題意轉化為差分約束，s[b+1]-s[a]>=c，防止a-1出界。

求s[end]>=?，求下限，求最長路，注意數組初始化和d數組更新條件

解決不連通有兩個方法：

1. 新增特殊點或在區間內以1為單位連通

2.所有點全部入隊，并標記

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 const int N=50005; 9 int n,cnt; 10 const int INF=0x3f3f3f3f; 11 int head[N],d[N]; 12 bool vis[N]; 13 14 struct e{ 15 int to,next,w; 16 }edge[N<<2]; // 有反向邊 17 18 void add(int u,int v,int w){ 19 edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++; 20 } 21 22 void init(){ 23 cnt=0; 24 memset(head,-1,sizeof(head)); 25 } 26 27 void SPFA(int s) 28 { 29 memset(d,-INF,sizeof(d)); 30 memset(vis,0, sizeof(vis)); 31 queue<int> q; 32 q.push(s); 33 d[s]=0; 34 vis[s]=1; 35 while(q.size()) 36 { 37 int u = q.front();q.pop(); 38 vis[u]=0; 39 for(int i=head[u];i!=-1;i=edge[i].next) 40 { 41 int v=edge[i].to; 42 int w=edge[i].w; 43 if(d[v]<d[u]+w) 44 { 45 d[v]=d[u]+w; 46 if(!vis[v]) 47 { 48 q.push(v); 49 vis[v]=1; 50 } 51 } 52 } 53 } 54 } 55 56 57 int main(){ 58 while(scanf("%d",&n)!=EOF) { 59 init(); 60 int st = INF, ed = -INF; 61 for (int i = 1; i <= n; i++) { 62 int a, b, c; 63 cin >> a >> b >> c; 64 add(a, b + 1, c); 65 st = min(st, a); 66 ed = max(ed, b + 1); 67 } 68 for (int i = st; i < ed; i++) { 69 add(i, i + 1, 0); 70 add(i + 1, i, -1); 71 } 72 SPFA(st); 73 cout << d[ed] << endl; 74 } 75 return 0; 76 }

?

轉載于:https://www.cnblogs.com/demian/p/9206407.html

總結

以上是生活随笔為你收集整理的HDU 1384 Intervals【差分约束-SPFA】的全部內容，希望文章能夠幫你解決所遇到的問題。

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