P3530 [POI2012]FES-Festival

题目大意 对选手编号有些大小的约束条件 最后求不同编号的最大数目

首先可以想到差分约束 最后答案就是求最最短路+1(最开始的点)

因为缩完点之后各个点之间一定是0连接 所以两边大小可以随便取

判断负环只需要判断dis[i][i]<0 即可

#include

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  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);
}