题目: https://www.lydsy.com/JudgeOnline/problem.php?id=2330
差分约束, 再建立一个源点 0, 向所有点连边权为 1 的边, 表示每个人都会分到糖果;
答案较大, 需要开 long long;
据说有个大数据会 T, 所以需要 0 点从 n 向 1 连边;
WA 了数次, 竟然是没看清条件... 不少于, 不多于什么的...
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- using namespace std;
- queue<int>q;
- int const MAXN=1e5+5;
- int n,k,head[MAXN],ct,dis[MAXN],cnt[MAXN];
- bool in[MAXN];
- long long ans;
- struct N{
- int to,next,w;
- N(int t=0,int n=0,int w=0):to(t),next(n),w(w) {}
- }edge[MAXN<<2];
- bool spfa(int s)
- {
- memset(in,0,sizeof in);
- memset(dis,-3,sizeof dis);
- dis[s]=0;in[s]=1;q.push(s);cnt[s]=1;
- while(q.size())
- {
- int x=q.front();q.pop();in[x]=0;
- for(int i=head[x],u;i;i=edge[i].next)
- {
- if(dis[u=edge[i].to]<dis[x]+edge[i].w)
- {
- if(++cnt[u]>=n)return 0;
- dis[u]=dis[x]+edge[i].w;
- if(!in[u])in[u]=1,q.push(u);
- }
- }
- }
- return 1;
- }
- int main()
- {
- scanf("%d%d",&n,&k);
- int tp,x,y;
- for(int i=1;i<=k;i++)
- {
- scanf("%d%d%d",&tp,&x,&y);
- if(tp==1){edge[++ct]=N(y,head[x],0),head[x]=ct;
- edge[++ct]=N(x,head[y],0),head[y]=ct;}
- if(tp==2){if(x==y){printf("-1");return 0;}
- else edge[++ct]=N(y,head[x],1),head[x]=ct;}
- if(tp==3)edge[++ct]=N(x,head[y],0),head[y]=ct;
- if(tp==4){if(x==y){printf("-1");return 0;}
- else edge[++ct]=N(x,head[y],1),head[y]=ct;}
- if(tp==5)edge[++ct]=N(y,head[x],0),head[x]=ct;
- }
- for(int i=n;i;i--)
- edge[++ct]=N(i,head[0],1),head[0]=ct;
- if(!spfa(0))
- {
- printf("-1");return 0;
- }
- for(int i=1;i<=n;i++)ans+=dis[i];
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2567309.html