[SCOI2011] 糖果

题目

链接

[SCOI2011]糖果

题意简述

有 $n \ (n <= 100000)$ 个点， $k \ (k <= 100000)$ 种关系。

有 $5$ 种关系类型。

• $$W_{A} == W_{B}$$
• $$W_{A} < W_{B}$$
• $$W_{A} >= W_{B}$$
• $$W_{A} > W_{B}$$
• $$W_{A} <= W_{B}$$

找出满足关系的最小总权值。

思路

差分约束

裸的差分约束。
分类讨论：

• $$W_{A} == W_{B} \rightarrow (a - b >= 0 \ and \ b - a >= 0) \rightarrow (edge_{b \rightarrow a} = 0, edge_{a \rightarrow b} = 0)$$
• $$W_{A} < W_{B} \rightarrow (b - a > 0 \rightarrow b - a >= 1) \rightarrow (edge_{a \rightarrow b} = 1)$$
• $$W_{A} >= W_{B} \rightarrow (a - b >= 0) \rightarrow (edge_{b \rightarrow a} = 0)$$
• $$W_{A} > W_{B} \rightarrow (a - b > 0 \rightarrow a - b >= 1) \rightarrow (edge_{b \rightarrow a} = 1)$$
• $$W_{A} <= W_{B} \rightarrow (b - a >= 0) \rightarrow (edge_{a \rightarrow b} = 0)$$

由于每个点都权值至少为 $1$ ，所以 $edge_{S \rightarrow i} = 1$。
跑最长路即可。
时间复杂度： $O(qk)$ 。

代码

#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 3e5 + 10, kmax_int = 0x3f3f3f3f, kmod = 1e9+7;

#define foe(x, y)	for(REG int (x) = head[(y)]; (x); (x) = edges[i].l)

int n, m;

struct SPFA	{
    struct Edge	{
        int v, d, l;
    }	edges[kmax_num];

    int head[(int)1e5 + 10], cnt;
    int dist[(int)1e5 + 10];
    int sum[(int)1e5 + 10];
    bool vis[(int)1e5 + 10];

    inline void AddEdge(REG int u, REG int v, REG int d)	{
        edges[++cnt] = (Edge) {v, d, head[u]};
        head[u] = cnt;
        return ;
    }

    inline bool Solve(REG int num)	{
        std::queue<int>	queue;
        queue.push(num);

        memset(vis, 0, sizeof(vis));
        vis[num] = 1;

        std::fill(dist, dist + n + 1, -1e9);
        dist[num] = 0;

        REG int u;
        while(!queue.empty())	{
            u = queue.front();	queue.pop();
            vis[u] = 0;

            if(sum[u] == n + 1)	{
                puts("-1");
                return false;
            }

            foe(i,u)	{
                if(dist[edges[i].v] < dist[u] + edges[i].d)	{
                    dist[edges[i].v] = dist[u] + edges[i].d;
                    if(!vis[edges[i].v])	{
                        queue.push(edges[i].v);
                        vis[edges[i].v] = 1;
                        ++sum[edges[i].v];
                    }
                }
            }
        }
        return true;
    }

}	spfa;

int main() {
    std::cin >> n >> m;

    REG int cmd, a, b;
    FOR(i,0,m)	{
        std::cin >> cmd >> a >> b;
        if(cmd == 1)	spfa.AddEdge(a, b, 0),	spfa.AddEdge(b, a, 0);
        else	if(cmd == 2)	spfa.AddEdge(a, b, 1);
        else	if(cmd == 3)	spfa.AddEdge(b, a, 0);
        else	if(cmd == 4)	spfa.AddEdge(b, a, 1);
        else	if(cmd == 5)	spfa.AddEdge(a, b, 0);
        if(cmd == 2 || cmd == 4)	if(a == b)	{ puts("-1");	return 0; }
    }

//	For(i,1,n)	spfa.AddEdge(0, i, 1);
    for(REG int i = n; i ; --i)	spfa.AddEdge(0, i, 1);

    if(!spfa.Solve(0))
        return 0;

    REG long long ans = 0;
    For(i,1,n)	ans += spfa.dist[i];
    printf("%lld\n", ans);
    return 0;
}

杂项

• 最后面向源点加边时不知道为什么正着加会被卡掉 $QAQ$ ，所以就倒着加了。