P3530 [POI2012]FES-Festival 题解

cminus · 2021-06-07 21:53:47 · 题解

感觉部分题解表述有一点点难以理解，所以蒟蒻第一次尝试自己写题解。

题目分析

仔细考虑这道题，从不等式上来看显然是要差分约束建图的，每个点之间的关系错综复杂，但是我们来看两个点，如果它们之间能互相到达，说明它们t值的差有确定的一个上界和下界，这时候这两个点之间的关系是互相确定的，他们之间的差才有意义，如果只是单向的关系，他们之间并不能确定差值关系。

基于此，如果有一个集合里面包含的所有的点，这些点都可以互相到达（就是一个强连通分量），那这个集合中任意两个点的差值关系都是确定的，此时这个集合中所有点之间最短路的最大值加一的就是这一个集合的答案。

为什么是所有点之间最短路的最大值 + 1 ？

这是这道题的特殊之处，因为题目限制只有两种，一种是相差 1，另一种是 t(a)<t(b) 的限制，此时我们使用差分约束的原理建出来的边权值只有 1，0，-1 这三种，最终算出的正差值虽然是权值之差，却恰好可以反映出它们之间应该有多少个不同值的数量 -1。

举例而言：

存在边 dis(1, 2) = 1, dis(2, 3) = 1, dis(2, 4) = 1，那么dis(1, 4)=3，这个3既是1和4之间的差值上界（即 dis(4)-dis(1) ），又能表示 1 和 4 中间（包括 1，4 )有 3+1 个数字个数字，因此 dis(1, 4) 反应的就是不同取值的数量 -1。
但是如果题目不一定是相差 1，例如 1 和 2 相差 5，还用上面的方法就会算出 6 的奇怪数字，因为我们上面的前提就不存在了。

然后对于不同连通块，显然，他们之间要么没有边，要么是单向边，是没有影响可以做到互不重叠的。

总结一下

根据差分约束的规则建图，先用 Tarjan 找到所有强连通分量，对图中每个强连通分量内使用 Floyd 跑最短路，把每一个连通块中最短路最大值 +1 加起来就是我们的答案。
如果 dis(x, x) < 0 ，说明无解。

有了上面这些理论，剩下的就是平平无奇的建图。

建图方式：

例如：

t(B) <= t(A) + 1

在最短路中，对于某条边，dis数组满足如下条件：

dis(to) <= dis(from) + w

故我们以dis作为我们相求的答案，加一条边 Add(A, B, 1) 就可以保证 dis 数组满足我们的要求。

无解的情况：

结合定义，dis(x, y) 表示的是 dis(y) - dis(x)，就是 y 比 x 最多大了的值，考虑对这道题而言无解的情况，显然，dis(x, x) 表示的是 x 比 x 最多大的值，即 dis(x)-dis(x) 的最大值，这个数字肯定不能小于0。

所以判断有没有 dis(x, x) 小于0就知道有没有无解了。

最后的一点思考：

有一些题解说这道题根据差分约束的条件建边，然后直接 Floyd 跑最短路找最长路就可以，但是因为会T所以才需要缩点，刚看到的时候疑惑了整整一天没想明白，例如：

给出一个 1 的时间小于 2 时间的限制条件，此时最长路为 0，最长路 +1 也是 1，但是显然它们可以最多取两种时间。

当我做完这道题再回头去看刚开始的想法，其实发现了一些有趣的事情，就是如果不管每个点属不属于同一个强连通分量，直接建完图就去跑 Floyd 的话，对于在同一个强连通分量里的点之间的最短路是没有影响的。

就是说如果不会 TLE 的话，刚开始直接建图跑最短路，然后找到所有强连通分量，把所有连通块最短路最大值 +1 加起来我们的答案了。

因为如果某个在强连通外的点能更新这个强连通分量内某两个点的距离，那它一定也属于这个强连通分量，矛盾了，所以整个一起算和单独算每个强连通分量是等价的。

以上。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 610;
int dis[N][N], low[N], dfn[N], num[N], t, n, ans[N];
bool vis[N];
stack < int > s;
void Tarjan(int u) {
    low[u] = dfn[u] = ++t;
    s.push(u); vis[u] = true;
    for (int i = 1; i <= n; i++)
        if (dis[u][i] <= 1) {
            if (!dfn[i]) {
                Tarjan(i);
                low[u] = min(low[i], low[u]);
            }
            else if (vis[i])
                low[u] = min(low[u], dfn[i]); 
        }
    if (dfn[u] == low[u]) {
        int v = s.top(); s.pop();
        while (u != v) {
            num[v] = u;
            vis[v] = false;
            v = s.top(); s.pop();
        }
        num[v] = u;
        vis[v] = false;
    }
}
int main() {
    int m1, m2;
    scanf("%d%d%d", &n, &m1, &m2);
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= m1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        dis[a][b] = min(1, dis[a][b]); 
        dis[b][a] = min(-1, dis[b][a]); 
    }
    for (int i = 1; i <= m2; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        dis[b][a] = min(dis[b][a], 0);
    }
    for (int i = 1; i <= n; i++) {
        dis[i][i] = 0;
        if (!dfn[i])    Tarjan(i);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            if (num[i] == num[k] && dis[i][k] != 0x3f3f3f3f)
                for (int j = 1; j <= n; j++)
                    if (num[i] == num[j])
                        dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (dis[i][i] < 0) {
            flag = false;
            break;
        }
        for (int j = 1; j <= n; j++) 
            if (num[i] == num[j])
                ans[num[i]] = max(ans[num[i]], dis[i][j] + 1);
    }
    if (!flag)  puts("NIE");
    else {
        int tot = 0;
        for (int i = 1; i <= n; i++)
            tot += ans[i];
        printf("%d\n", tot);
    }   
    return 0;
}