洛谷3530 [POI2012]FES-Festival

题解 图论-最短/最长路 图论-差分约束 图论-Tarjan 省选/NOI-
题目链接 编辑文章

题意

有 $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$ 环就可能无解,所以需要判环。其它题解说正环也不合法,我感觉是错误的。如下例:

4 3 1
2 1
3 2
1 4
3 4

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

1 2 1
2 1 -1
2 3 1
3 2 -1
4 1 1
1 4 -1
3 4 0

这个图里是有正环的,但仍然有解,答案显然为 $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);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。