DLKKILL

DLKKILL's world

POJ - 1201 - Intervals (差分约束系统)

题目链接:POJ – 1201 

题目大意:有一个序列,题目用n个整数组合 [ai,bi,ci]来描述它,[ai,bi,ci]表示在该序列中处于[ai,bi]这个区间的整数至少有ci个。如果存在这样的序列,请求出满足题目要求的最短的序列长度是多少。

题目分析:

利用差分约束转化成图的最短路关系。

设S[i]为从[1,i]闭区间内的整数个数。

则:

  • s[b] – s[a-1] >= c

  • S[b]-S[b-1] >=0

  • S[b-1]-S[b] >=-1

给出代码:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=50000+10;
int R,len,L;
bool vis[maxn];
int  dis[maxn];
int  head[maxn];
int n;
struct node
{
    int next;
    int to;
    int val;
}g[maxn*3];
void init()
{
    R=len=0;L=0x7fffff;
    memset(head,-1,sizeof(head));
}
void add_edge(int from,int to,int val)
{
    g[len].to=to;
    g[len].next=head[from];
    g[len].val=val;
    head[from]=len++;
}
int spfa()
{
    queue<int> q;
    for(int i=L;i<=R;i++)
    {
        vis[i]=1;
        dis[i]=0;
        q.push(i);
    }
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        vis[cur]=false;
        for(int i=head[cur];i!=-1;i=g[i].next)
        {
            int id=g[i].to;
            if(dis[id]<g[i].val+dis[cur])
            {
                dis[id]=g[i].val+dis[cur];
                if(!vis[id])
                {
                    vis[id]=true;
                    q.push(id);
                }
            }
        }
    }
    return dis[R];
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        for(int i=0;i<n;i++)
        {
            int from,to,val;
            scanf("%d%d%d",&from,&to,&val);
            add_edge(from,to+1,val);
            L=min(L,from);
            R=max(R,to+1);
        }
        for(int i=L;i<=R;i++)
        {
            add_edge(i,i+1,0);
            add_edge(i+1,i,-1);
         //   g[i].push_back(node(i+1,0));
         //g[i+1].push_back(node(i,-1));
        }
        printf("%d\n",spfa());
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注