正題

題目大意:https://www.luogu.org/problemnew/show/P3275

---

題目大意

對于$n$個值，給出一系列不等式。求每個值的最小正整數(shù)。

---

解題思路

差分約束

---

$code$

#include<cstdio> #include<queue> #include<cstring> #define MN 300005 using namespace std; queue<int> q; struct line{int to,w,next; }a[MN*30]; int n,m,tot,f[MN],ls[MN],len[MN]; bool v[MN]; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot; } int spfa() {q.push(n);v[n]=1;while (!q.empty()){int x=q.front();q.pop();v[x]=0;for (int i=ls[x];i;i=a[i].next){int y=a[i].to;if (f[x]+a[i].w>f[y]){f[y]=f[x]+a[i].w;len[y]++;if(len[y]>=n) {printf("-1");return 0;}if (!v[y]){v[y]=1;q.push(y);}}}}long long ans=0;for(int i=1;i<n;i++)ans+=f[i];printf("%lld",ans);return 0; } int main() {freopen("data.in","r",stdin);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int S,x,y;scanf("%d%d%d",&S,&x,&y);if(S==1){addl(x,y,0);addl(y,x,0);}if(S==2){if(x==y){printf("-1");return 0;}addl(x,y,1);}if(S==3)addl(y,x,0);if(S==4){if(x==y){printf("-1");return 0;}addl(y,x,1);}if(S==5)addl(x,y,0);}n++;for(int i=n-1;i;--i)addl(n,i,1);spfa(); }

總結(jié)

以上是生活随笔為你收集整理的P3275-[SCOI2011]糖果【差分约束,负环】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。