POJ1201Intervals


这是一道差分约束,可以考虑前缀和,对于一个区间$[a_i,b_i]$要使选取数字超过$c_i$,可以得出不等式$s[b_i]-s[a_i-1]\geq c_i$,当然这样的限制还不够,我们要保证它的结果有意义,对于每一个$k$,都存在这样两个不等式$s[k]-s[k-1]\geq0$,$s[k]-s[k-1]\leq1$

由于要从-1开始,不妨把每个数都加一,用spfa求最长路后,便得出结果

#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=500005;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n;
int d[maxn],vis[maxn],head[maxn],num=0;
struct node{
    int v,w,nex;
}e[maxn];
void add(int u,int v,int w)
{
    e[++num].v=v;
    e[num].w=w;
    e[num].nex=head[u];
    head[u]=num;
}
void spfa()
{
    memset(d,-0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(0);
    d[0]=0,vis[0]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nex)
        {
            int v=e[i].v;
            if(d[v]<d[u]+e[i].w)
            {
                d[v]=d[u]+e[i].w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        x=read(),y=read(),z=read();
        add(x,y+1,z);
    }
    for(int i=0;i<=50000;i++)
    {
        add(i,i+1,0);
        add(i+1,i,-1);
    }
    spfa();
    printf("%d\n",d[50001]);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
Tyvj1053 棋盘覆盖 Tyvj1053 棋盘覆盖
二分图最大匹配裸题,甚至不需要建边,直接在棋盘上搜索即可,给点附上编号$n*i+j$ #include<bits/stdc++.h> using namespace std; const int maxn=10000; inline
2019-07-06
下一篇 
POJ3621 Sightseeing Cows POJ3621 Sightseeing Cows
这道题是求最优比率环,使点权和除以边权和最大,二分判断即为存在负环,可以用dfs版的spfa进行判断,注意由于二分答案使用duoble,所以与之相关的变量数组一定要定义为duoble #include<cstdio> #includ
2019-07-05
  目录