【题解】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 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,a,0);
48         if(x==2)add(a,b,1);
49         if(x==3)add(b,a,0);
50         if(x==4)add(b,a,1);
51         if(x==5)add(a,b,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 }