洛谷3530 [POI2012]FES-Festival

Luogu

分析

差分约束+ $\mathrm{tarjan}$ + $\mathrm{spfa}$ 。

首先按照差分约束的那一套理论建图。设 $dis[i][j]$ 表示 $a_i$ 最多比 $a_j$ 大多少。那么:

  • 对于每个 $a_x+1=a_y$ 的条件,从 $x$ 向 $y$ 连边权为 $-1$ 的边,从 $y$ 向 $x$ 连边权为 $1$ 的边。
  • 对于每个 $a_x\leq a_y$ 的条件,从 $x$ 向 $y$ 连边权为 $0$ 的边。

显然图中存在正环或负环时都不合法。发现如果存在正环,那么反向边一定会构成一个负环,于是只要判负环即可。


但是如果你直接跑 $\mathrm{floyd}$ 判负环,你会收获 $\mathrm{\color{blue}{TLE}}$ ;如果你直接从 $1$ 开始跑 $\mathrm{SPFA}$ ,你会收获 $\mathrm{\color{red}{WA}}$ 。

可能的原因是,负环没有和 $1$ 相连。

然后如果你每个点都跑一边 $\mathrm{spfa}$ 的话,大概会 $\mathrm{\color{blue}{TLE}}$ 。


于是,需要跑一遍 $\mathrm{tarjan}$ 缩点,然后每次只要跑同一个强连通分量内的点就行了。

至于怎么算答案,枚举一个强连通分量内的两个点,然后取 $dis$ 的最大值 $+1$ 累加。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

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

const int N=600+10;
const int M=200000+10;

int n,m1,m2;

struct Edge { int v,w,nxt; } e[M];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int dfn[N],low[N],tim=0;
int bl[N],sz[N],tot=0;
int sta[N],in[N],top=0;

inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]) {
        ++tot;
        while (233) {
            int now=sta[top--];
            bl[now]=tot,++sz[tot],in[now]=0;
            if (now==u) break;
        }
    }
}

int dis[N][N],inq[N],cnt[N];

inline int spfa(int s) {
    memset(dis[s],0x3f,sizeof(dis[s])),memset(cnt,0,sizeof(cnt));
    queue<int> Q; Q.push(s); dis[s][s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (bl[s]!=bl[v]) continue;
            if (dis[s][u]+w<dis[s][v]) {
                dis[s][v]=dis[s][u]+w,cnt[v]=cnt[u]+1;
                if (cnt[v]>sz[bl[s]]) return 1;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return 0;
}

int main() {
    n=read(),m1=read(),m2=read();
    for (re int i=1;i<=m1;++i) {
        int u=read(),v=read();
        addEdge(u,v,-1),addEdge(v,u,1);
    }
    for (re int i=1;i<=m2;++i) {
        int u=read(),v=read();
        addEdge(u,v,0);
    }
    for (re int i=1;i<=n;++i)
        if (!dfn[i]) tarjan(i);
    for (re int i=1;i<=n;++i)
        if (spfa(i)) { puts("NIE"); return 0; }
    int ans=0;
    for (re int t=1;t<=tot;++t) {
        int now=0;
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                if (bl[i]==t&&bl[j]==t) now=max(now,dis[i][j]);
        ans+=now+1;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 12 : 58 PM

发表评论