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自動機】