程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1384 poj1202 Intervals --- 差分約束

hdu1384 poj1202 Intervals --- 差分約束

編輯：C++入門知識

差分約束系統

差分約束系統的應用難點在於將實際問題轉換為差分約束系統。

簡單來說，要構造出一系列滿足題意的不等式形如 Si-Sj<=Ck，且必須含等號。

對於每一個這樣的不等式，構造有向邊 w(j->i)=Ck。

為保證圖的連通，我們引入附加結點Vs。初始化w(s->i)=0，d[Vs]=0

接下來就是求解源點到其他點的單源最短路徑。

由於差分約束系統中通常含負值，所以我們一般用spfa或者bellman來求最短路徑。

這裡有個技巧，不想要添加附加結點的話，可以開始將所有點加入隊列，相當於Vs入隊，接下來的更新沒有指回Vs的結點，所以可以省略。

注意點:
1. 如果要求最大值想辦法把每個不等式變為標准x-y<=k的形式,然後建立一條從y到x權值為k的邊,變得時候注意x-yx-y<=k-1
如果要求最小值的話,變為x-y>=k的標准形式，然後建立一條從y到x的k邊，求出最長路徑即可
2.如果權值為正，用dj，spfa，bellman都可以，如果為負不能用dj，並且需要判斷是否有負環，有的話就不存在

---------------回到這道題--------------

題意：

構造一個集合，要求對每一個給定的區間 [a, b]，至少包含其中的n個數

求滿足條件的集合內最少含多少個數。

思路：

令Si表示在[0,i-1]區間內要選多少個數。則可列出不等式：

S(b+1)-Sa>=C

另外，由於一個數至多取一個，至少取0個，則有：

0=< Si-S(i-1)<=1

根據以上不等式構圖，以給定區間的最小值為起點，最大值為終點，求解最長路即可。

小結：

其實不等式就可以看成圖中邊權需要滿足的條件，將所有不滿足條件的邊更新就是了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;

struct node
{
    int v,w,next;
}e[50010];

int d[50010],head[50010],inq[50010],n,h,minn,maxx;

void init()
{
    memset(head,-1,sizeof head);
    h=0;
}

void addedge(int a,int b,int c)
{
    e[h].v=b;
    e[h].w=c;
    e[h].next=head[a];
    head[a]=h++;
}

void spfa()
{
    memset(d,0,sizeof d);//求最長路 賦值為0
    memset(inq,0,sizeof inq);
   // memset(outq,0,sizeof outq);
    queue q;
    //省略掉那個虛點,可以優化spfa.虛點作用是讓所有點入隊
    //所以省略掉這點的話,需要手動把所有點入隊
    for(int i=minn;i<=maxx;i++)
    {
        q.push(i);
        inq[i]=1;
    }
    d[minn]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        inq[x]=0;
       // outq[x]++;
       // if(outq[x]>n) return -1;//存在負環//此題不存在
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            if(d[e[i].v]minn&&d[x-1]