题意
给定多组限制，限制分成2类，第一类是ax+1=ay 第二类是ax≤ay，求这些数最多有多少种不同的取值
在使得所给的等式成立的情况下，问最多能有多少不同的数字值。
差分约束题目
问最多有多少种取值
那么求最短路判负环
第一类限制可以 换为
\(y-x<=1\)
连边
\(x – > y, w=1\)
\(x-y<=-1\)
连边
\(y – > x , w=-1\)
第二类限制直接
\(y->x, w=0\)
对于每个强连通分块之间是没有限制的
于是就可以在每个强连通分块中判负环
最后累加一下答案就行了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<bits/stdc++.h> using namespace std; inline int read(){ int X=0,w=1; char ch=0; while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();} while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar(); return X*w; } const int maxn=1e5+10; int dis[605][605],m1,m2,n,head[maxn],cnt; struct E{ int next,to,val; }tu[maxn]; void add(int next,int to,int val){ tu[cnt].next=head[next]; tu[cnt].to=to; tu[cnt].val=val; head[next]=cnt++; } int dfn[maxn],low[maxn],tim,num,bel[maxn],vis[maxn]; stack<int>s; void tarjan(int x){ dfn[x]=low[x]=++tim; s.push(x); vis[x]=1; for(int i=head[x];~i;i=tu[i].next){ int u=tu[i].to; if(!dfn[u]){ tarjan(u); low[x]=min(low[x],low[u]); } else if(vis[u]){ low[x]=min(low[x],dfn[u]); } } if(dfn[x]==low[x]){ int j; num++; do{ j=s.top(); s.pop(); vis[j]=0; bel[j]=num; }while(j!=x); } } bool spfa(int lvl,int x){ vis[x]=1; for(int i=head[x];~i;i=tu[i].next){ int u=tu[i].to; if(bel[u]!=bel[x])continue; if(dis[lvl][u]>dis[lvl][x]+tu[i].val){ dis[lvl][u]=dis[lvl][x]+tu[i].val; if(vis[u])return 0; else if(!spfa(lvl,u))return 0; } } vis[x]=0; return 1; } int ans; int main(){ memset(head,-1,sizeof(head)); memset(dis,127,sizeof(dis)); n=read(),m1=read(),m2=read(); for(int i=1;i<=m1;i++){ int x=read(),y=read(); add(y,x,-1);add(x,y,1); } for(int i=1;i<=m2;i++){ int x=read(),y=read(); add(y,x,0); } for(int i=1;i<=n;i++)dis[i][i]=0; for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ if(!spfa(i,i)){puts("NIE");return 0;} } for(int i=1;i<=num;i++){ int mn=0; for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ if(bel[j]==i&&bel[k]==i)mn=max(mn,dis[j][k]); } } ans+=mn+1; } printf("%d\n",ans); return 0; } /* x<y x-y<=0 y - > x 0 */ /* y-x<=1 y-x>=1 x-y<=-1; y - > x -1 x - > y 1 */ |
说点什么