hdu 1384 差分约束(SPFA实现)

Problem: http://acm.hdu.edu.cn/showproblem.php?pid=1384

在每个区间[ai,bi]上至少选ci个元素组成集合Z，求Z最小时的元素个数

因为是求最小，所以差分约束转化为SPFA求最长路

每个ai,bi,ci转换成点ai指向点bi+1的边，边权为ci

求出最小的ai,Min，最大的bi,Max

加上(Max-Min+2)*2条有向边x->x+1(边权为0)x+1->x(边权为-1) x属于[Min,Max]

最后套上SPFA模版妥妥的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100010
int head[MAXN],n,m,Min,Max,dist[MAXN];
struct Edge{
    int to,next,w;
}e[MAXN*3];
void add_edge(int u,int v,int c){
    e[m].to=v;
    e[m].w=c;
    e[m].next=head[u];
    head[u]=m++;
}
void SPFA(int s){
    bool vis[MAXN];
    memset(vis,false,sizeof(vis));
    for(int i=Min;i<=Max+1;i++)dist[i]=-10000;
    queue<int> que;
    que.push(s);
    vis[s]=false;
    dist[s]=0;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        vis[u]=false;
        int k=head[u];
        while(k>=0){
            if(dist[e[k].to]<dist[u]+e[k].w){
                dist[e[k].to]=dist[u]+e[k].w;
                if(!vis[e[k].to]){
                    que.push(e[k].to);
                    vis[e[k].to]=true;
                }
            }
            k=e[k].next;
        }
    }
}
void init(){
    memset(head,-1,sizeof(head));
    int a,b,c;
    Max=m=0;
    Min=MAXN;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        Min=min(Min,a);
        Max=max(Max,b);
        add_edge(a,b+1,c);
    }
    for(int i=Min;i<=Max;i++){
        add_edge(i,i+1,0);
        add_edge(i+1,i,-1);
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        init();
        SPFA(Min);
        printf("%d
",dist[Max+1]);
    }
    return 0;
}

加上set容器优化了一下

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
#define MAXN 100010
int head[MAXN],n,m,Min,Max,dist[MAXN];
struct Edge{
    int to,next,w;
}e[MAXN*3];
void add_edge(int u,int v,int c){
    e[m].to=v;
    e[m].w=c;
    e[m].next=head[u];
    head[u]=m++;
}
void SPFA(int s){
    bool vis[MAXN];
    memset(vis,false,sizeof(vis));
    for(int i=Min;i<=Max+1;i++)dist[i]=-10000;
    queue<int> que;
    que.push(s);
    vis[s]=false;
    dist[s]=0;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        vis[u]=false;
        int k=head[u];
        while(k>=0){
            if(dist[e[k].to]<dist[u]+e[k].w){
                dist[e[k].to]=dist[u]+e[k].w;
                if(!vis[e[k].to]){
                    que.push(e[k].to);
                    vis[e[k].to]=true;
                }
            }
            k=e[k].next;
        }
    }
}
void init(){
    memset(head,-1,sizeof(head));
    int a,b,c;
    Max=m=0;
    Min=MAXN;
    set<int> S;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        Min=min(Min,a);
        Max=max(Max,b);
        add_edge(a,b+1,c);
        S.insert(a);
        S.insert(b+1);
    }
    b=MAXN;
    set<int>::iterator it=S.end();
    while(it!=S.begin()){//减少边来降低计算量
        --it;
        a=*it;
        add_edge(a,b,0);
        add_edge(b,a,a-b);
        b=a;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        init();
        SPFA(Min);
        printf("%d
",dist[Max+1]);
    }
    return 0;
}

话说200+ms是怎么做到的...