洛谷3530 [POI2012]FES-Festival

2021.11.18更新：

“最长路径 $+1$ 就是答案”有误，因为对于 $M_2$ 的情况，两点间的距离其实可以是无穷大的。但强连通分量中就不会有这种情况，因为点之间两两互通，所以它们之间的距离也就有上限。

题意

有 $N$ 个数和 $M_1+M_2$ 种关系。前 $M_1$ 种关系 $(x,y)$ 表示 $S_x+1=S_y$ ，后 $M_2$ 种关系表示 $S_x\le S_y$ 。求最多有多少个数字值。如果无解输出 NIE 。

$N\le 600 , M_1+M_2\le 100000$ 。

题解

不等式关系可以先差分约束建图。边 $(x,y)$ 的权值表示 $S_x-S_y$ 的最大值，对于 $M_1$ 就连边 $(x,y,-1)$ 和 $(y,x,1)$ ，对于 $M_2$ 就连 $(x,y,0)$ 。~~显然最长路径 $+1$ 就是答案。~~

容易想到用 $\text{Floyd}$ 来实现，但 $N^3\approx 2\times 10^8$ ，会爆。

不过可以发现强连通分量之间是没有关系的，所以可以对每个强连通分量跑最长路径。因为数值的个数都要 $+1$ ，所以最后的答案为最长路径和 $+$ 强连通分量个数。

但如果存在非 $0$ 环就可能无解，所以需要判环。其它题解说正环也不合法，我感觉是错误的。如下例：

建边的方法为（因为Graph Editor画出来两条边会重在一起所以就不放图了自己画一下吧）

这个图里是有正环的，但仍然有解，答案显然为 $4$ 。

继续分析可以发现，正环无解的情况仅有环上全为 $1$这一种，否则就可以把权值为 $0$ 的边拆开使其满足条件。

不过全为 $1$ 的情况下反过来走就是个负环，所以可以只判负环。跑完 $\text{Floyd}$ 后如果存在 $dis[i][i] < 0$ ，就说明有负环。

最后对每个强连通分量记录最长路径，加起来统计答案即可。

注意：对于读入，如果有多组限定关系应该选择较小的那个，所以需要取最小值。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[200005];
stack <int> s;
int scnt,dfsord,id[605],low[605],scc[605];
int cnt,head[605],n,m1,m2,a,b,dis[605][605],mx[605],ans;

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}

void dfs(int x) //Tarjan
{
    s.emplace(x);
    id[x]=low[x]=++dfsord;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            if (t==x) break;
        }
    }
}

signed main()
{
    n=read(); m1=read(); m2=read();
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=n;i++) dis[i][i]=0;
    for (int i=1;i<=m1;i++)
    {
        a=read(); b=read();
        add(a,b,-1); add(b,a,1);
        dis[a][b]=min(dis[a][b],-1); dis[b][a]=min(dis[b][a],1); //取较小值
    }
    for (int i=1;i<=m2;i++)
    {
        a=read(); b=read();
        add(a,b,0);
        dis[a][b]=min(dis[a][b],0);
    }
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i);
    }
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=n;i++)
        {
            if (scc[i]!=scc[k]) continue;
            for (int j=1;j<=n;j++)
            {
                if (scc[j]!=scc[i]) continue;
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); //对每个强连通分量求出最短路
            }
        }
    }
    for (int i=1;i<=n;i++) if (dis[i][i]) return 0&puts("NIE"); //判负环
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (scc[i]!=scc[j]) continue;
            mx[scc[i]]=max(mx[scc[i]],dis[i][j]); //强连通分量
        }
    }
    for (int i=1;i<=scnt;i++) ans+=mx[i];
    return !printf("%d",ans+scnt);
}

题意

题解

新评论