[POI2012]FES-Festival

https://www.zybuluo.com/ysner/note/1252538

题面

有一个数列\(\{a\}\)。现给定多组限制，限制分成\(2\)类，第一类是\(a_x+1=a_y\)，有\(m_1\)个；第二类是\(a_x\leq a_y\)，有\(m_2\)个。求这些数最多有多少种不同的取值。

\(n\leq600,m_1+m_2\leq10^5\)

解析

看到不等式就可以想到差分约束。

根据一些差分约束小常识，可以设\(dis[x][y]\)表示\(a_x\)最多能比\(a_y\)大多少。

于是对第一类，\(dis[x][y]=1,dis[y][x]=-1\)。（双向边适用于定量比较）

第二类，由于是\(a_y\geq a_x\),\(dis[y][x]=0\)。（单向边适用于定性比较）

一般来说，图中只要有非\(0\)环就是不合法的。

观察一下建边，可以发现如果有正环，它的反边就会构成负环。

于是只要判负环就可以了。

如何判负环？

\(SPFA\)判负环（初始化一定要为正无穷）、\(floyd\)判断\(dis[i][i]<0\)都可以。

然而这题用前者会出现点小坑。

因为我们一般出发都会以\(1\)为起点，而这一个图中\(1\)不一定与负环联通。

怎么办？

跑\(tarjan\)找出联通块。虚构一个结点，与各个联通块建边权为\(0\)的边（主要注意防止因该结点的建立而产生新的负环），然后从虚构点出发\(SPFA\)即可。

缩完点后，图中只剩边权为\(0\)的边连接各联通块（第一类自己就能构成一个块）。由于“大于等于”这个关系不限制绝对大小，因而对答案没有影响（因可以无限扩大自己的值），可以忽略这些边。

于是各联通块内\(maxdis+1\)之和即为答案。

（话说只在联通块内跑\(floyd\)的效率真是恐怖，\(SPFA\)判负环成了复杂度瓶颈）

完了？然而还要注意限制条件可以叠加，所以要取\(\min\)。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#define re register

#define il inline

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int mod=1e9+7,N=605;

struct Edge{int to,nxt,w;}e[N*400];

int n,m1,m2,h[N],cnt,dis[N],dfn[N],low[N],tim,sta[N],top,scc,bl[N],sz[N],num[N],d[N][N];

bool vis[N];

ll ans;

queue<int>Q;

il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}

il ll gi()

{

   re ll x=0,t=1;

   re char ch=getchar();

   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

   if(ch=='-') t=-1,ch=getchar();

   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

   return x*t;

}

il void tarjan(re int u)

{

  dfn[u]=low[u]=++tim;vis[u]=1;sta[++top]=u;

  re int v;

  for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);

      else if(vis[v]) low[u]=min(low[u],dfn[v]);

    }

  if(dfn[u]==low[u])

    {

      ++scc;

      do{v=sta[top];bl[v]=scc;vis[v]=0;++sz[scc];top--;}while(u^v);

    }

}

il int fSPFA(re int st)

{

  memset(dis,63,sizeof(dis));memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));

  while(!Q.empty()) Q.pop();

  dis[st]=0;num[st]=1;Q.push(st);vis[st]=1;

  while(!Q.empty())

    {

      re int u=Q.front();Q.pop();

      for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      if(dis[v]>dis[u]+e[i].w)

        {

      if((++num[v])>n) return 0;

          dis[v]=dis[u]+e[i].w;

          if(!vis[v]) vis[v]=1,Q.push(v);

        }

    }

      vis[u]=0;

    }

  return 1;

}

int main()

{

  memset(h,-1,sizeof(h));memset(d,63,sizeof(d));

  re int u,v;

  n=gi();m1=gi();m2=gi();

  fp(i,1,m1) u=gi(),v=gi(),add(u,v,1),add(v,u,-1),d[u][v]=min(d[u][v],1),d[v][u]=min(d[v][u],-1);

  fp(i,1,m2) u=gi(),v=gi(),add(v,u,0),d[v][u]=min(d[v][u],0);

  fp(i,1,n) d[i][i]=min(d[i][i],0);

  fp(i,1,n) if(!dfn[i]) tarjan(i);

  memset(vis,0,sizeof(vis));

  fp(i,2,n)

    if(!vis[bl[i]])

      add(0,i,0),vis[bl[i]]=1;

  memset(vis,0,sizeof(vis));

  //if(!fSPFA(0)) {puts("NIE");return 0;}

  fp(o,1,scc)

  {

    re ll mx=0;

    fp(k,1,n)

    {

      if(bl[k]!=o) continue;

      fp(i,1,n)

      {

    if(bl[i]!=o||d[i][k]==d[0][0]) continue;

        fp(j,1,n)

      {

        if(bl[j]!=o||d[k][j]==d[0][0]) continue;

        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

      }

      }

    }

    fp(i,1,n)

      {

    if(bl[i]!=o) continue;

    fp(j,1,n)

      {

        if(bl[j]!=o) continue;

        mx=max(mx,d[i][j]);

      }

      }

    ans+=mx+1;

  }

  fp(i,1,n) if(d[i][i]<0) {puts("NIE");return 0;}

  printf("%lld\n",ans);

  return 0;

}

巴特西

[POI2012]FES-Festival

https://www.zybuluo.com/ysner/note/1252538

题面

解析

最新文章

热门文章