【题解】Luogu P3275 [SCOI2011] 糖果 差分约束

概述听说是裸的板子，所以开始现学 题目给出的5种 *** 作都能转化为差分约束 如果大于正向连$1$的边 如果小于反向连$1$的边 如果等于要双向建边 另：要开$long long$ code   1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define int long long 5 co

听说是裸的板子，所以开始现学

题目给出的5种 *** 作都能转化为差分约束

如果大于正向连$的边

如果小于反向连$的边

如果等于要双向建边

另：要开$long long$

code

 

 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define int long long 5 const int mod=1e9+7; 6 const int maxn=1e5+10; 7 inline int read(){ 8     int x=0,f=1; 9     char c=getchar();10     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}11     while(c>=‘0‘&&c<=‘9‘){x=(x*10)+c-‘0‘;c=getchar();}12     return x*f;13 }14 int n,m,ans;15 struct edge{16     int to,nxt,w;17 }e[maxn*2];18 int head[maxn],cnt,dis[maxn],vis[maxn],us[maxn];19 inline voID add(int from,int to,int w){20     e[++cnt].to=to;e[cnt].nxt=head[from];21     e[cnt].w=w;head[from]=cnt;22 }23 queue<int>q;24 bool spfa(){25     while(!q.empty()){26         int x=q.front();q.pop();27         vis[x]=0;us[x]=1;28         for(int i=head[x];i;i=e[i].nxt){29             int y=e[i].to;30             if(dis[x]+e[i].w>dis[y]){31                 dis[y]=dis[x]+e[i].w;32                 us[i]++;33                 if(us[i]>=n)return 0;34                 if(!vis[y]){35                     q.push(y);vis[y]=1;36                 }37             }38         }39     }40     return 1;41 }42 int main(){43     n=read();m=read();44     for(int i=1;i<=m;i++){45         int x,a,b;46         x=read();a=read();b=read();47         if(x==1)add(a,b,0),add(b,0);48         if(x==2)add(a,1);49         if(x==3)add(b,0);50         if(x==4)add(b,1);51         if(x==5)add(a,0);52         if(x%2==0&&a==b){53             printf("-1\n");return 0;54         }55     }56     for(int i=1;i<=n;i++){57         dis[i]=1;us[i]=1;vis[i]=1;58         q.push(i);59     }60     if(!spfa()){61         printf("-1\n");return 0;62     }63     for(int i=1;i<=n;i++){64         ans+=dis[i];65     }66     printf("%lld\n",ans);67     return 0;68 }69 }70 signed main(){71   gengyf::main();72   return 0;73 }

VIEw Code 总结

以上是内存溢出为你收集整理的【题解】Luogu P3275 [SCOI2011] 糖果 差分约束全部内容，希望文章能够帮你解决【题解】Luogu P3275 [SCOI2011] 糖果 差分约束所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。