JennP3275 [SCOI2011]糖果e

差分约束到底在干什么？

最短路的基本不等式是$dis_v<=dis_u+edge_i$

那么要求最大的解要依据这个来建立起来一个图，跑最短路

求最小解要跑最长路，也就是

$dis_v>=dis_u+edge_i$

然后跑最长路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int dis[1000001];
int head[1000001];
int p;
queue<int> q;
struct e{
    int to;
    int ne;
    int v;
}ed[2000001];
void add(int f,int to,int v){
    ed[++p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
    ed[p].v=v;
    return ;
}
int vis[10000001];
int n,k;
int tot[10000001];
int f;int x;int y;
void spfa(){
    q.push(0);
    vis[0]=1;
    memset(dis,0xc0,sizeof(dis));
    dis[0]=0;
    while(!q.empty()){
        int x=q.front();
        //cout<<x<<endl;
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=ed[i].ne){
            int v=ed[i].to;
            //cout<<v<<endl;;
            if(dis[v]<dis[x]+ed[i].v){
                dis[v]=dis[x]+ed[i].v;
                if(!vis[v]){
                    tot[v]++;   
                    if(tot[v]==n){
                        printf("-1");
                        exit(0);
                    }
                    if(!vis[v]){
                    vis[v]=1;
                    q.push(v);;
                    }
                }
            }
        }
    }   
}
int main(){
    read(n);read(k);
    for(int i=1;i<=k;++i){
        read(f);read(x);read(y);
        if(f==1){
            add(x,y,0);
            add(y,x,0);
        }
        if(f==2){
            add(x,y,1);
            if(x==y){
                printf("-1");
                return 0;
            }
        }
        if(f==3){
            //add(y,x,0);
            add(y,x,0);
        }
        if(f==4){
            add(y,x,1);
            if(x==y){
                printf("-1");
                return 0;
            }
        }
        if(f==5){
            add(x,y,0);
        }
    }
    for(int i=n;i>=1;--i){
        add(0,i,1);
    }

    spfa();
    long long ans=0;
    for(int i=1;i<=n;++i){
        ans+=dis[i];
    }
    cout<<ans;
    return 0;
}