题解 [POI2012] FES-Festival

P3530 [POI2012]FES-Festival - 洛谷计算机科学教育新生态

题目大意

给定 \(n\) 个整数 \(x_1, x_2, \cdots , x_n\) ，以及 \(m_1\) 个形如 \(x_a + 1 = x_b\) 的约束条件，和 \(m_2\) 个形如 \(x_c \leqslant x_d\) 的约束条件。求所有变量最多能有多少不同的取值，若无解输出无解。

其中 \(2 \leqslant n \leqslant 600\), \(1 \leqslant m_1 + m_2 \leqslant 10^5\) 。

算法选择

见到此类约束条件，考虑用差分约束。本题中差分约束求最短路或最长路均可，此处以求最短路为例。因为求最短路，故图中不能有负环。

算法差分约束 | 散虑の春雨寻风

考虑若是图中有多个强连通分量，那么各个强连通分量之间的结果必然互不干扰，因为可以让每个强联通分量内部的变量取值范围均不相同。最终将每个强连通分量的结果分别相加便是总结果。所以此题还考虑缩点。

具体思路

接下来问题便是在一个强连通分量内求差分约束的结果。考虑在按最短路建好图后，按照差分约束算法，从一个点 \(a\) 到另一个点 \(b\) 的最短路代表 \(x_b - x_a\) 的最大值，并考虑到边权只有 \(\left\{ 0, 1, -1 \right\}\) 三种，可以得到结论：一个强连通分量内的最多取值个数等于强连通分量两两之间最短路的最大值\(+1\) ，即所求答案就是全源最短路最大值\(+1\) 。证明如下：

由于边权只有 \(\left\{ 0, 1, -1 \right\}\) 三种，因此对于任一单源最短路，取值数 = 最大值 - 最小值\(+1\) ；

不妨设最短路的最大值为 \(maxd\) ，那么对于这个差分约束系统的任意一组解，我选择最小的数\(x_a\) 和最大的数 \(x_b\) ，由于这个图强连通，因此 \(a\) 到 \(b\) 必然存在至少一条路径，设 \(dis(a, b)\) 为其最短路径；

则有 取值数\(-1 = x_b - x_a \leqslant dis(a, b) \leqslant maxd\) ；

由于本图的特性，一定存在一组解，即一定存在一个点，使得 取值数\(-1 = maxd\) 。故 \(maxd +1\) 就是最大的取值数。

算法总结

按最短路差分约束法建边；
Tarjan 缩点，分离出强连通分量；
分别在每个强连通分量内跑 Floyd，判断是否存在负环并计算结果；
若是每个强连通分量内均无负环，将所有结果相加即可。

时间复杂度

Tarjan 算法复杂度 \(O(n +m)\) ，Floyd 最坏情况 \(O(n^3)\) 。

代码实现

邻接表转为邻接矩阵时注意重边的判断，只保留边权最小的边；
注意要在每个强连通分量内跑 Floyd ，而不是每次都全局跑；
只要有一个强连通分量内有负环，便无解。

本题邻接表用了 STL ，故开启 \(O2\) 加速，用时 442ms 。

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 605;
const int INF = 0x3f3f3f3f;
const int SMAX = 100005;

// 全局
int n, m1, m2;
// 图
vector<pair<int, int> > edges[NMAX];
// Floyd
int dis[NMAX][NMAX];
// Tarjan
int low[NMAX], dfn[NMAX], scc[NMAX], sizescc[NMAX];
int dfncnt, scccnt;
stack<int> stk;

bool Floyd(int sccno)
{
    memset(dis, INF, sizeof(dis));
    for (register int i = 1; i <= n; i++)
        if (scc[i] == sccno)
        {
            dis[i][i] = 0;
            for (auto j : edges[i])
                dis[i][j.first] = min(dis[i][j.first], j.second);
        }
    for (register int k = 1; k <= n; k++)
        if (scc[k] == sccno)
            for (register int i = 1; i <= n; i++)
                if (scc[i] == sccno)
                    for (register int j = 1; j <= n; j++)
                        if (scc[j] == sccno && dis[i][j] > dis[i][k] + dis[k][j])
                            dis[i][j] = dis[i][k] + dis[k][j];
    for (register int i = 1; i <= n; i++)
        if (scc[i] == sccno && dis[i][i])
            return true;
    return false;
}

void Tarjan(int cur)
{
    low[cur] = dfn[cur] = dfncnt++;
    stk.push(cur);
    for (auto to : edges[cur])
        if (dfn[to.first] == -1)
        {
            Tarjan(to.first);
            low[cur] = min(low[cur], low[to.first]);
        }
        else if (scc[to.first] == -1)
            low[cur] = min(low[cur], dfn[to.first]);
    if (low[cur] == dfn[cur])
    {
        int tmp;
        do
        {
            tmp = stk.top();
            stk.pop();
            scc[tmp] = scccnt;
            sizescc[scc[tmp]]++;
        } while (tmp != cur);
        scccnt++;
    }
}

int main()
{
    memset(dfn, -1, sizeof(dfn));
    memset(low, -1, sizeof(low));
    memset(scc, -1, sizeof(scc));
    scanf("%d%d%d", &n, &m1, &m2);
    for (register int i = 1, u, v; i <= m1; i++)
    {
        scanf("%d%d", &u, &v);
        edges[u].push_back(make_pair(v, 1));
        edges[v].push_back(make_pair(u, -1));
    }
    for (register int i = 1, u, v; i <= m2; i++)
    {
        scanf("%d%d", &u, &v);
        edges[v].push_back(make_pair(u, 0));
    }

    for (int i = 1; i <= n; i++)
        if (dfn[i] == -1)
            Tarjan(i);

    int ans = 0, flag = false;
    for (int i = 0; i < scccnt; i++)
    {
        if ((flag = Floyd(i)))
            break;
        int dismax = 0;
        for (register int j = 1; j <= n; j++)
            if (scc[j] == i)
                for (register int k = 1; k <= n; k++)
                    if (scc[k] == i && dismax < dis[j][k])
                        dismax = dis[j][k];
        ans += dismax + 1;
    }

    if (flag)
        puts("NIE");
    else
        printf("%d\n", ans);

    system("pause");
    return 0;
}

aytony