P3275 [SCOI2011]糖果

这是个假的SLF优化SPFA(我就只是把queue版本中的q.push()全改成了deque q.push_front())，结果过了,为什么？

还有为什么这题超级源点倒着建边就可以过第6个点？

我很菜，劳烦诸位神仙为我解惑，不胜感激！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const int maxn = 1e6;
const int inf = 0x7fffffff;

int m,n;
int num_edge;
int flag;
int head[maxn],dis[maxn];
int cnt[maxn];
bool vis[maxn];

struct Edge{
    int next;
    int dis;
    int to;
}edge[maxn*2];

deque<int> q;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline void add_edge(int from,int to,int dis){
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    edge[num_edge].dis = dis;
    head[from] = num_edge;
}

inline void SPFA(int s)
{
    for(register int i=1;i<=n;++i){
        vis[i] = 0;
        dis[i] = -inf;  
    }
    q.push_front(s);
    vis[s] = 1,dis[s] = 0;
    cnt[s]++;   
    while(!q.empty()){
        int u = q.front();
        vis[u] = 0;
        q.pop_front();
        for(register int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]<dis[u]+edge[i].dis){  
                dis[v] = dis[u] + edge[i].dis;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push_front(v);
                }
                cnt[v]++;
            if(cnt[v]==n+1){  
                    flag = 1;
                    return;
                }
            }
        }
    }
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i)
    {
        int x,a,b;
        x=read();
        if(x==1){
            a=read(),b=read();
            add_edge(a,b,0);
            add_edge(b,a,0);
        }   
        if(x==2){
            a=read(),b=read();
            if(a==b){
                printf("-1");
                return 0;
            }
            add_edge(a,b,1);
        }
        if(x==3){
            a=read(),b=read();
            add_edge(b,a,0);
        }
        if(x==4){
            a=read(),b=read();
            if(a==b){
                printf("-1");
                return 0;
            }
            add_edge(b,a,1);
        }
        if(x==5){
            a=read(),b=read();
            add_edge(a,b,0);
        }
    }   

    for(register int i=1;i<=n;++i){ 
        add_edge(n+1,i,1);
    }

    SPFA(n+1);

    if(flag==1){
        printf("-1");
        return 0;
    }

    ll ans=0;

    for(register int i=1;i<=n;++i){
        ans+=dis[i];
    }

    printf("%lld",ans);

    return 0;
} 

用queue #6 TLE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const int maxn = 1e6;
const int inf = 0x7fffffff;

int m,n;
int num_edge;
int flag;
int head[maxn],dis[maxn];
int cnt[maxn];
bool vis[maxn];

struct Edge{
    int next;
    int dis;
    int to;
}edge[maxn*2];

queue<int> q;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline void add_edge(int from,int to,int dis){
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    edge[num_edge].dis = dis;
    head[from] = num_edge;
}

inline void SPFA(int s)
{
    for(register int i=1;i<=n;++i){
        vis[i] = 0;
        dis[i] = -inf;
    }
    q.push(s);
    vis[s] = 1,dis[s] = 0;
    cnt[s]++;   
    while(!q.empty()){
        int u = q.front();
        vis[u] = 0;
        q.pop();
        for(register int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]<dis[u]+edge[i].dis){
                dis[v] = dis[u] + edge[i].dis;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                    cnt[v]++;
                }
            }
            if(cnt[v]==n+1){
                flag = 1;
                return;
            }
        }
    }
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i)
    {
        int x,a,b;
        x=read();
        if(x==1){
            a=read(),b=read();
            add_edge(a,b,0);
            add_edge(b,a,0);
        }   
        if(x==2){
            a=read(),b=read();
            if(a==b){
                printf("-1");
                return 0;
            }
            add_edge(a,b,1);
        }
        if(x==3){
            a=read(),b=read();
            add_edge(b,a,0);
        }
        if(x==4){
            a=read(),b=read();
            if(a==b){
                printf("-1");
                return 0;
            }
            add_edge(b,a,1);
        }
        if(x==5){
            a=read(),b=read();
            add_edge(a,b,0);
        }
    }   

    for(register int i=1;i<=n;++i){
        add_edge(n+1,i,1);
    }

    SPFA(n+1);

    if(flag==1){
        printf("-1");
        return 0;
    }

    ll ans=0;

    for(register int i=1;i<=n;++i){
        ans+=dis[i];
    }

    printf("%lld",ans);

    return 0;
}