POJ3159 Candies（差分限制）

題意：給n個人分糖果，下标1到n，給出m個限制條件a b c，a的糖果數比b的糖果少的個數不多于c，即 b的糖果-a的糖果<=c。求n的糖果比1的糖果最多多多少。

思路：查分限制系統的第一題，b-a<=c 換成 b<=a+c ，即求最短路中的松弛操作，于是轉化成了最短路問題。用最短路的求法得到的解一定都是最大值，對應地，最長路的求法可以得到解的最小值。此題把點1作為源點，進行一次最短路操作即可保證n-1最大。

題目沒有負權，是以可以用Dijkstra，加上堆優化。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<list>
#include<algorithm>
#include<queue>
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=30001;
const int M=150001;
struct ed{
    int v,c,next;
}edge[M];
struct node{
    int d,u;
    node(int d,int u):d(d),u(u){}
    bool operator < (const node& b)const{
        return d>b.d;
    }
};
int pre[N],dis[N],n,cnt;
bool vis[N];
void addEdge(int u,int v,int c){
    edge[cnt].v=v;
    edge[cnt].c=c;
    edge[cnt].next=pre[u];
    pre[u]=cnt++;
}
void dijkstra(){
    int cur;
    priority_queue<node> q;
    for(int i=1;i<=n;++i){
        dis[i]=inf;
        vis[i]=0;
    }
    dis[1]=0;
    q.push(node(0,1));
    while(!q.empty()){
        cur=q.top().u;
        q.pop();
        if(vis[cur])continue;
        vis[cur]=1;
        for(int i=pre[cur];i!=-1;i=edge[i].next){
            if(!vis[edge[i].v]&&dis[edge[i].v]>dis[cur]+edge[i].c){
                dis[edge[i].v]=dis[cur]+edge[i].c;
                q.push(node(dis[edge[i].v],edge[i].v));
            }
        }
    }
}
int main(){
    int m,a,b,c;
    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        for(int i=1;i<=n;++i){
            pre[i]=-1;
        }
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
        }
        dijkstra();
        printf("%d\n",dis[n]);
    }
}
           

此外還有能判負環的spfa，通過這題真是看出了spfa的不穩定orz。。。用隊列和棧居然能差那麼大，棧的速度跟Dij差不多，隊列果斷逾時，優化也無果。。

spfa+棧

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<list>
#include<algorithm>
#include<queue>
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=150001;
struct ed{
    int v,c,next;
}edge[N];
int n,cnt,dis[30005],pre[30005];
bool vis[30005];
void addEdge(int u,int v,int c){
    edge[cnt].v=v;
    edge[cnt].c=c;
    edge[cnt].next=pre[u];
    pre[u]=cnt++;
}
void spfa(){
    int s[30005],top=0,cur;
    for(int i=1;i<=n;++i){
        vis[i]=false;
        dis[i]=inf;
    }
    s[top++]=1;
    dis[1]=0;
    while(top){
        cur=s[--top];
        vis[cur]=false;
        for(int i=pre[cur];i!=-1;i=edge[i].next){
            if(dis[edge[i].v]>dis[cur]+edge[i].c){
                dis[edge[i].v]=dis[cur]+edge[i].c;
                if(!vis[edge[i].v]){
                    vis[edge[i].v]=1;
                    s[top++]=edge[i].v;
                }
            }
        }
    }
}
int main(){
    int m,a,b,c;
    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        for(int i=1;i<=n;++i){
            pre[i]=-1;
        }
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
        }
        spfa();
        printf("%d\n",dis[n]);
    }
}
           

spfa有兩個廣為流傳的優化方法SLF和LLL，據說一起用可以優化50%。

SLF：Small Label First政策，設要加入的節點是j，隊首元素為i，若dist（j）<dist（i），則将j插入隊首，否則插入隊尾。

LLL：Large Label Last政策，設隊首元素為i，隊列中所有dist的平均值為x，若dist（i）>x則将i插入隊尾，查找下一進制素，直到找出某一i使得dist（i）<=x，則将i出隊進行松弛。（摘自：http://www.cnblogs.com/cj695/archive/2012/07/27/2611215.html）

終于模拟出了兩種政策，卻還是逾時，看來這題隊列實在無解，WA得一聲哭出來。。。

附上逾時代碼

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<list>
#include<algorithm>
#include<queue>
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=150001;
struct ed{
    int v,c,next;
}edge[N];
int n,cnt,dis[30005],pre[30005];
bool vis[30005];
void addEdge(int u,int v,int c){
    edge[cnt].v=v;
    edge[cnt].c=c;
    edge[cnt].next=pre[u];
    pre[u]=cnt++;
}
void spfa(int s,int e){
    int q[30005],l=0,r=0,len=0,cur;
    ll sum=0;
    for(int i=1;i<=n;++i){
        dis[i]=inf;
        vis[i]=false;
    }
    dis[s]=0;
    len=1;
    q[r++]=s;
    while(l!=r){
        cur=q[l++];
        if(30005==l)l=0;
        //LLL
        while((ll)dis[cur]*(ll)len>sum){
            q[r++]=cur;
            if(30005==r)r=0;
            cur=q[l++];
            if(30005==l)l=0;
        }
        sum-=dis[cur];
        --len;
        vis[cur]=false;

        for(int i=pre[cur];i!=-1;i=edge[i].next){
            if(dis[edge[i].v]>dis[cur]+edge[i].c){
                dis[edge[i].v]=dis[cur]+edge[i].c;
                if(!vis[edge[i].v]){
                    ++len;
                    sum+=dis[edge[i].v];
                    vis[edge[i].v]=true;
                    //LSF
                    if(l!=r){
                        if(dis[edge[i].v]<dis[q[l]]){
                            if(0==l)l=30004;
                            q[l]=edge[i].v;
                        }else{
                            q[r++]=edge[i].v;
                            if(30005==r)r=0;
                        }
                    }else{
                        q[r++]=edge[i].v;
                        if(30005==r)r=0;
                    }
                }
            }
        }
    }
}
int main(){
    int m,a,b,c;
    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        for(int i=1;i<=n;++i){
            pre[i]=-1;
        }
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
        }
        spfa(1,n);
        printf("%d\n",dis[n]);
    }
}