洛谷P3275 [SCOI2011]糖果 题解

题目链接：P3275 [SCOI2011]糖果

题意：

幼儿园里有 \(N\) 个小朋友，cxy 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，cxy 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，cxy 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式:

输入的第一行是两个整数 \(N,K\)。接下来 \(K\) 行，表示这些点需要满足的关系，每行 \(3\) 个数字，\(X,A,B\) 。

• 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多；
• 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果；
• 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果；
• 如果 \(X=4\)， 表示第 \(A\) 个小朋友分到的糖果必须多于第 \(B\) 个小朋友分到的糖果；
• 如果 \(X=5\)， 表示第 \(A\) 个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果；

输出格式:

输出一行，表示 cxy 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 \(-1\)。

数据范围：

\(1 \le N,K \le 10^5,~1\le X\le5, ~1\le A, B\le N\) 。

差分约束神题。

考虑先只添加 \(1,3,5\) 种边，优先处理可以等于的情况。

如果 \(a \le b\) ，建边 \(u \to v\) ，反之若 \(a \ge b\) ，就建边 \(v \to u\) 。

若 \(a=b\) ，也就是第 \(1\) 种边，我们建边 \(u \to v,~v \to u\) 。

不难发现此时所有的强连通分量中的点一定会取相等的值。

然后我们跑一遍 \(\mathtt{Tarjan}\) 缩点，重新建图，顺便加上 \(2,4\) 种边。

注意此时原先的边应该边权为 \(0\) ，新加的边边权应为 \(1\) 。

此时的图一定是个 DAG ，否则一定无解。然后跑个 \(\mathtt{Toposort}\) 算一下就好了

时间复杂度 \(\mathcal{O}(n + m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ ((int)(1e6))
    char buf1[SIZ+5],*_p1,*_p2;
    char readchar()
    {
        if(_p1 == _p2) _p1=buf1,_p2=buf1+fread(buf1,1,SIZ,stdin);
        return _p1 == _p2 ? EOF : *_p1++;
    }
    template<typename T> void read(T &k)
    {
        char ch = gc(); T x = 0, f = 1;
        while(!isdigit(ch)) { if(ch == '-') f = -1; ch = gc(); }
        while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }
        k = x * f;
    }
    template<typename T> void write(T k)
    {
        if(k < 0) { k = -k; pc('-'); }
        static T _stk[66]; T _top = 0;
        do{ _stk[_top++] = k % 10; k/=10; }while(k);
        while(_top){ pc(_stk[--_top] + '0'); }
    }
}using namespace FastIO;
#define N ((int)(1e5+15))

bitset<N> ins,vis;
int n,m,k,res,pos=1,stktop,scnt,head[N],f[N];
int sz[N],dfn[N],low[N],stk[N],scc[N],top[N],in[N];
struct query { int op,a,b; } qry[N];
struct Edge{ int u,v,w,next; } e[N * 2];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void Tarjan(int u)
{
    static int tim = 0; dfn[u] = low[u] = ++tim;
    ins[stk[++stktop] = u] = 1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            Tarjan(v); down(low[u], low[v]);
        } else if(ins[v]) down(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        top[++scnt] = u;
        for(int p=0; p != u; )
        {
            p = stk[stktop--]; ins[p] = 0;
            scc[p] = scnt; ++sz[scnt];
        }
    }
}
queue<int> q;
void Toposort()
{
    for(int i=1; i<=scnt; i++) if(!in[i]) { q.push(i); f[i] = vis[i] = 1; }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v, w = e[i].w;
            up(f[v], f[u] + w); vis[v] = 1;
            if(!(--in[v])) q.push(v);
        }
    }
    for(int i=1; i<=scnt; i++) if(!vis[i]) return cout << "-1\n",void(0);
    int res = 0;
    for(int i=1; i<=scnt; i++) res += f[i] * sz[i];
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m);
    for(int i=1,op,a,b; i<=m; i++)
    {
        read(op); read(a); read(b);
        if(op & 1)
        {
            if(op == 5 || op == 1) addEdge(a,b,0); // a <= b
            if(op == 3 || op == 1) addEdge(b,a,0); // b <= a
        }else qry[++k] = {op, a, b};
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) Tarjan(i);
    for(int i=1; i<=n; i++) head[i] = 0;
    int tmp = pos; pos = 1;
    for(int i=2; i<=tmp; i++)
    {
        int u = scc[e[i].u], v = scc[e[i].v];
        if(u != v) { addEdge(u,v,0); ++in[v]; }
    }
    for(int i=1; i<=k; i++)
    {
        int u = scc[qry[i].a], v = scc[qry[i].b];
        if(u == v) return cout << "-1\n", 0;
        if(qry[i].op == 2) { addEdge(u,v,1); ++in[v]; } // a < b
        if(qry[i].op == 4) { addEdge(v,u,1); ++in[u]; } // b > a
    }
    Toposort();
    return 0;
}