元旦晚会 | FFY's Blog

题意

P1986 元旦晚会

• 差分约束
• 最长路

差分裸题

1. dis[i]>=dis[i-1]
2. dis[i]-dis[i-1]<=1
3. dis[b]-dis[a-1]>=c

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=3e4+10,inf=-1e9;
int n,m,head[maxn],num,root,dis[maxn];
bool use[maxn];
struct fy{int from,to,d,next;}q[maxn<<2];
void add(int a,int b,int c){q[++num]=(fy){a,b,c,head[a]};head[a]=num;}
void sp()
{
    for(int i=1;i<=n;i++)dis[i]=inf;dis[root]=0;
    queue<int>qq;qq.push(root);use[root]=true;
    while(!qq.empty())
    {
        int a=qq.front();qq.pop();use[a]=false;
        for(int i=head[a];i;i=q[i].next)
        {
            int b=q[i].to;
            if(dis[b]<dis[a]+q[i].d)
            {
                dis[b]=dis[a]+q[i].d;
                if(!use[b]){use[b]=true;qq.push(b);}
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);int a,b,c;
    root=maxn;int out=0;
    for(int i=1;i<=n;i++)
    {
        add(i,i-1,-1);
        add(i-1,i,0);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        root=min(a-1,root);
        out=max(out,b);
        add(a-1,b,c);
    }
    sp();
    printf("%d\n",dis[out]);
    return 0;
}

差分约束算是非常复杂的方法
这题其实可以用贪心来做(区间选点模型)