题解 UVA1723 【Intervals】

题意

有n个如下形式的条件:

ai bi ci,表示在区间[ai, bi]内至少要选择ci个整数点。

问你满足n个条件的情况下,最少需要选多少个点?

题解

就差分约束呗......

何为差分约束:如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。

由此，可以把它转化为图，跑一波SPFA就完事了。

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#include<iostream>
using namespace std;
struct node
{
    int u,v,w;
    int next;
}wee[500001];
int minnnn=0x7f,maxxxx=-1;//最小和最大
int n,h[500001],cnt;
int u,v,w;
int vis[500001],stackto[500001],qwq[500001];
void add(int u,int v,int w)
{
    wee[++cnt].u=u;
    wee[cnt].v=v;
    wee[cnt].w=w;
    wee[cnt].next=h[u];
    h[u]=cnt;
}
bool spfa()
{
    stack<int>st;
    while(!st.empty()) st.pop();
    memset(stackto,0,sizeof(stackto));
    memset(qwq,0,sizeof(qwq));
    for(int i=minnnn;i<=maxxxx;i++)
        vis[i]=-0x7f;
    st.push(minnnn);
    vis[minnnn]=0;
    stackto[minnnn]=1;
    qwq[minnnn]++;
    while(!st.empty())
    {
        int u=st.top();
        st.pop();
        stackto[u]=0;
        for(int i=h[u];i!=0;i=wee[i].next)
        {
            if(vis[wee[i].v]<vis[u]+wee[i].w)
            {
                vis[wee[i].v]=vis[u]+wee[i].w;
                if(!stackto[wee[i].v])
                {
                    stackto[wee[i].v]=1;
                    st.push(wee[i].v);
                    qwq[wee[i].v]++;
                    if(qwq[wee[i].v]>n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>u>>v>>w;
        add(u,v+1,w);
        minnnn=min(minnnn,u);
        maxxxx=max(maxxxx,v+1);
    }
    for(int i=minnnn;i<maxxxx;i++)
    {
        add(i,i+1,0);
        add(i+1,i,-1);
    }
    spfa();//万能的spfa
    cout<<vis[maxxxx]-vis[minnnn]<<endl;
    return 0;
}