题目描述
给定多组限制,限制分成2类,第一类是$ax+1=ay 第二类是ax≤ay$,求这些数最多有多少种不同的取值在使得所给的等式成立的情况下,问最多能有多少不同的数字值。
思路
考虑差分约束。第一类限制:$(x,y,1),(y,x,-1)$,第二类限制:$(y,x,0)$
那么整张图应该是由若干强联通分量组成(因为有单向边),我们只需缩点后累计答案就行了。
对于同一强联通分量,$floyd$判负环跑最短路即可。
code
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=610; const int M=100010; struct node { int to,nxt; }g[M<<1]; int head[N],cnt; int n,m1,m2; int ind,low[N],dfn[N],sta[N],top,col[N],color; bool vis[N]; int dist[N][N]; int ans,ma[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void addedge(int u,int v,int dis) { dist[u][v]=min(dist[u][v],dis); g[++cnt].nxt=head[u]; g[cnt].to=v; head[u]=cnt; } inline void tarjan(int u) { low[u]=dfn[u]=++ind; sta[++top]=u; for(int i=head[u];i;i=g[i].nxt) { int v=g[i].to; if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]); else if(!col[v])low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { color++; while(sta[top]!=u)col[sta[top--]]=color; top--;col[u]=color; } } int main() { n=read();m1=read();m2=read(); memset(dist,0x3f3f3f3f,sizeof(dist)); for(int i=1;i<=n;i++)dist[i][i]=0; for(int i=1;i<=m1;i++) { int x=read(),y=read(); addedge(x,y,1);addedge(y,x,-1); } for(int i=1;i<=m2;i++) { int x=read(),y=read(); addedge(y,x,0); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) { if(dist[i][k]==dist[0][0])continue; if(col[k]!=col[i])continue; for(int j=1;j<=n;j++) { if(dist[k][j]==dist[0][0])continue; if(col[i]!=col[j])continue; dist[i][j]=min(dist[i][k]+dist[k][j],dist[i][j]); } } for(int i=1;i<=n;i++)if(dist[i][i]!=0){cout<<"NIE";return 0;} for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(col[i]==col[j]) ma[col[i]]=max(ma[col[i]],dist[i][j]); } for(int i=1;i<=color;i++)ans+=ma[i]; cout<<ans+color<<endl; }