差分约束 get ！

A4paper · 2018-08-29 21:14:38 · 个人记录

将不等式组转化成图，

想想松弛的操作：

移项，代换，变成如下式子：

或

所以，把所有不等式变成大于号或大于等于号，再建图

特别的，如果是等于，则变成 a >= b\ \&\&\ b >= a 的形式

然后，用 SPFA 跑最短路就好了

模板：

传送门

inline void add(int u, int v, int w)
{
    map[++cnt] = (node){v,head[u],w};
    head[u] = cnt;
}
inline bool SPFA()
{
    while(!que.empty())
    {
        int u = que.front();    que.pop();
        vis[u] = 0;
        use[u] = 0;
        for(int k=head[u];k;k=map[k].next)
        {
            int v = map[k].to;
            if( dis[v] < dis[u] + map[k].w)
            {
                dis[v] = dis[u] + map[k].w;
                use[k]++;
                if(use[k] > n-1)    return 0;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return 1;
}
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1,num,u,v;i<=m;i++)
    {
        scanf("%d%d%d",&num,&u,&v);
        switch(num)
        {
            case 1: add(u,v,0); add(v,u,0); break;
            case 2: add(u,v,1);             break;
            case 3: add(v,u,0);             break;
            case 4: add(v,u,1);             break;
            case 5: add(u,v,0);             break;
        }
        if(num%2==0 && u==v)
        {
            cout << "-1" << endl;
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        vis[i] = 1;
        dis[i] = 1;
        use[i] = 1;
        que.push(i);
    }
    if(SPFA())
    {
        for(int i=1;i<=n;i++)   ans += dis[i];
        cout << ans << endl;
    }
    else cout << "-1" << endl;
    return 0;
}