题解 P3530 【[POI2012]FES-Festival】
ysner
·
·
题解
看到不等式就可以想到差分约束。
根据一些差分约束小常识，可以设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环就是不合法的。
观察一下建边，可以发现如果有正环，它的反边就会构成负环。
于是只要判负环就可以了。
如何判负环？
然而这题用前者会出现点小坑。
因为我们一般出发都会以$1$为起点，而这一个图中$1$不一定与负环联通。
怎么办？
跑$tarjan$找出联通块。虚构一个结点，与各个联通块建边权为$0$的边（主要注意防止因该结点的建立而产生新的负环），然后从虚构点出发$SPFA$即可。
缩完点后，图中只剩边权为$0$的边连接各联通块（第一类自己就能构成一个块）。由于“大于等于”这个关系不限制绝对大小，因而对答案没有影响（因可以无限扩大各联通块的值），可以忽略这些边。
于是各联通块内$maxdis+1$之和即为答案。
（话说**只在联通块内跑$floyd$**的效率真是恐怖，$SPFA$判负环成了复杂度瓶颈）
完了？然而还要注意限制条件可以叠加，所以$dis$的赋值要取$\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;
}
```