BZOJ 2330, 糖果

2019-11-06 06:29:09

字体：大中小

来源：转载

供稿：网友

PRoblem

传送门

Mean

求最少需多少糖果若干约束条件。

Analysis

说起来这还是我的第一道差分约束题，汗颜。条件一等价于A-B≥0 , B-A≥0；条件二等价于B-A≥1；条件三等价于A-B≥0；条件四等价于A-B≥1；条件五等价于B-A≥0。具体怎么连边可以手画三角形脑补一下。同时要注意条件二和条件四如果给出了同一个人，则必定无法满足要求。

Code

#include<cstdio>const int N=200005,INF=~0U>>2;int n,k,p,a,b,h,t,ed,min=1,g[N>>1],v[N],w[N],nxt[N],q[N],d[N>>1],cnt[N>>1];long long ans;bool in[N>>1];void read(int &x){ char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}void add(int x,int y,int c){ v[++ed]=y,w[ed]=c; nxt[ed]=g[x]; g[x]=ed;}bool ADD(int x,int y){ if(y<=d[x]) return 0; d[x]=y; if(!in[x]){ in[x]=1,cnt[x]++; if(d[x]<d[h]){ h--; if(!h) h=N-1; q[h]=x; }else{ t++; if(t==N) t=0; q[t]=x; } } return cnt[x]>=n;}int main(){ read(n),read(k); while(k--){ read(p),read(a),read(b); if(p==1) add(a,b,0),add(b,a,0); else if(p==2){ if(a==b){printf("-1");return 0;} add(a,b,1); }else if(p==3) add(b,a,0); else if(p==4){ if(a==b){printf("-1");return 0;} add(b,a,1); }else add(a,b,0); } h=1,t=n; for(int i=1;i<=n;i++) q[i]=i,in[i]=d[i]=1; while(h!=(t+1)%N){ int x=q[h++]; if(h==N) h=0; in[x]=0; for(int i=g[x];i;i=nxt[i]) if(ADD(v[i],d[x]+w[i])){printf("-1");return 0;} } for(int i=1;i<=n;i++) ans+=d[i]; printf("%lld",ans); return 0;}

上一篇：1001. Battle Over Cities - Hard Version (35)

下一篇：NYOJ 1085 数单词【AC自动机】