Intervals（差分约束）

http://poj.org/problem?id=1201

题意：给出N个整数区间[ai,bi]，并且给出一个约束ci，（ 1<= ci <= bi-ai+1），使得数组Z在区间[ai,bj]的个数>= ci个，求出数组Z的最小长度。

思路：建立差分约束系统。因为这里要求数组长度的最小值，要变为 x-y>=k的标准形式。

设数组 s[j] 表示数组 Z 区间[0,j]里包含的元素个数。所以 s[bi+1] - s[ai] >= ci,注意是 j+1,

隐含条件 0 <= s[i+1]-s[i] <= 1;

故差分约束系统为：

s[bi+1] - s[ai] >= ci；

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

s[i] - s[i+1] >= -1;

然后邻接表建图求最长路。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stack>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 struct node

 {

     int u,v,w;

     int next;

 }edge[maxn];

 int n,p[maxn],cnt;

 int Min,Max;

 int dis[maxn],instack[maxn],vexcnt[maxn];

 void add(int u, int v, int w)

 {

     cnt++;

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = p[u];

     p[u] = cnt;

 }

 bool SPFA()

 {

     stack<int>st;

     while(!st.empty()) st.pop();

     memset(instack,,sizeof(instack));

     memset(vexcnt,,sizeof(vexcnt));

     for(int i = Min; i <= Max; i++)

         dis[i] = -INF;

     st.push(Min);

     dis[Min] = ;

     instack[Min] = ;

     vexcnt[Min]++;

     while(!st.empty())

     {

         int u = st.top();

         st.pop();

         instack[u] = ;

         for(int i = p[u]; i; i = edge[i].next)

         {

             if(dis[edge[i].v] < dis[u] + edge[i].w)

             {

                 dis[edge[i].v] = dis[u] + edge[i].w;

                 if(!instack[edge[i].v])

                 {

                     instack[edge[i].v] = ;

                     st.push(edge[i].v);

                     vexcnt[edge[i].v]++;

                     if(vexcnt[edge[i].v] > n)

                         return false;

                 }

             }

         }

     }

     return true;

 }

 int main()

 {

     int u,v,w;

     scanf("%d",&n);

     cnt = ;

     memset(p,,sizeof(p));

     Min = INF,Max = -;

     for(int i = ; i < n; i++)

     {

         scanf("%d %d %d",&u,&v,&w);

         add(u,v+,w);

         Min = min(Min,u);

         Max = max(Max,v+);

     }

     for(int i = Min; i < Max; i++)

     {

         add(i,i+,);

         add(i+,i,-);

     }

     SPFA();

     printf("%d\n",dis[Max]-dis[Min]);

     return ;

 }

关于差分约束：

比如给出三个不等式,b-a<=k1,c-b<=k2,c-a<=k3,求出c-a的最大值,我们可以把a,b,c转换成三个点，k1，k2，k3是边上的权，如图

由题我们可以得知，这个有向图中，由题b-a<=k1,c-b<=k2,得出c-a<=k1+k2,因此比较k1+k2和k3的大小，求出最小的就是c-a的最大值了

根据以上的解法，我们可能会猜到求解过程实际就是求从a到c的最短路径，没错的....简单的说就是从a到c沿着某条路径后把所有权值和k求出就是c -a<=k的一个

推广的不等式约束，既然这样，满足题目的肯定是最小的k，也就是从a到c最短距离...

理解了这里之后，想做题还是比较有困难的，因为题目需要变形一下，不能单纯的算..

首先以poj3159为例,这个比较简单，就是给出两个点的最大差，然后让你求1到n的最大差，直接建图后用bellman或者spfa求最短路就可以过了

稍微难点的就是poj1364，因为他给出的不等式不是x-y<=k形式，有时候是大于号，这样需要我们去变形一下，并且给出的还是>,<没有等于，都要变形

再有就是poj1201，他要求出的是最长距离，那就要把形式变换成x-y>=k的标准形式

注意点:

1. 如果要求最大值想办法把每个不等式变为标准x-y<=k的形式,然后建立一条从y到x权值为k的边,变得时候注意x-y<k =>x-y<=k-1

如果要求最小值的话,变为x-y>=k的标准形式，然后建立一条从y到x的k边，求出最长路径即可

2.如果权值为正，用dj，spfa，bellman都可以，如果为负不能用dj，并且需要判断是否有负环，有的话就不存在

巴特西

Intervals（差分约束）

最新文章

热门文章