luogu_3275【题解】糖果 差分约束

题面：https://www.luogu.org/problemnew/show/P3275

大意：emmmmmmmm看到题面就知道真的不好总结。

差分约束的裸题。

将各类关系建成不同的边。

当op为1的时候，建一个双向边权值为0；

为2的时候，建立从a到b权值为1的边；

为3的时候，建立从b到a权值为0的边；

为4的时候建立从b到a权值为1的边；

为5的时候建立从a到b权值为0的边；

然后直接跑spfa，但是和普通最短路有区别。

不要更新最小。

而是要取最大，因为要满足所有人。

当一个点更新的次数大于等于n的时候，证明有环，不可行。

vis[ ] 就为spfa的vis[ ]数组，us[ ]为更新过几次。

代码如下。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxm=100010;
long long ans=0;
int head[maxm],tot;
struct node{
    int to,nxt,va;
    #define to(x) e[x].to
    #define nxt(x) e[x].nxt
    #define va(x) e[x].va
}e[maxm<<1];

inline void add(int from,int to,int w){
    to(++tot)=to;va(tot)=w;
    nxt(tot)=head[from];head[from]=tot;
}

int dis[maxm],us[maxm],vis[maxm];
queue<int> q;
inline bool spfa() {
    while (!q.empty()) {
        int now = q.front(); q.pop();
        vis[now] = 0;
        us[now]=1;
        for (int i = head[now]; i; i = nxt(i)) {
            if (dis[now] + va(i) > dis[to(i)]) {
                dis[to(i)] = dis[now] + va(i);
                us[i]++;
                if(us[i]>=n) return 0;
                if (!vis[to(i)]) {
                    q.push(to(i));
                    vis[to(i)] = 1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,a,b;
        scanf("%d%d%d",&x,&a,&b);
        if(x==1) add(a,b,0),add(b,a,0);
        if(x==2) add(a,b,1);
        if(x==3) add(b,a,0);
        if(x==4) add(b,a,1);
        if(x==5) add(a,b,0);
        if(x%2==0&&a==b){
            printf("-1
");return 0;
        }
    }
    for(int i=1;i<=n;i++){
        dis[i]=1;us[i]=1;vis[i]=1;
        q.push(i);
    }
    if(!spfa()){
        printf("-1
");
        return 0;
    }
    for(int i=1;i<=n;i++)
        ans+=dis[i];
    printf("%lld
",ans);
    // system("pause");
    return 0;
}