P3275_[SCOI2011]糖果灾区糖果分发成功

╰半夏微凉° 2021-12-09 03:13 255阅读 0赞

[*题面*][Link 1]

**这是一篇用差分约束的题解.**

但是这道题卡SPFA

有5个差分不等式,其实很好推的.

1.  a=b,推出a-b<=0与b-a<=0,于是以a向b建一条权值为0的边,以b向a建一条权值为0的边.(相等的关系都要建2条边的)
2.  a<b,把它变成a+1<=b,推出b-a<=1,于是以a向b建一条权值为1的边.
3.  a<=b,推出a-b<=0,以b向a建一条权值为0的边.
4.  a>b,把它变成a-1>=b,推出b-a<=1,于是以b向a建一条权值为1的边.
5.  a>=b,推出b-a<=0,以a前b建一条权值为0的边.

然后用一个超级源点连接,源点向每个边的权值都为1,因为每个灾民小朋友都要分至少一个糖.

用不等式表达就是a-b>=1.b为源点,自然没有糖,a至少有一个糖.

再用一个数组存一下节点被遍历的次数,如果大于n+1(所有节点+超级源点)就说明存在环了,具体请见[*这篇博客*][Link 2].

什么?你说我没倒序存边?

代码见下,为了显得成分多加了O3,请自行忽略1~49行.

#pragma GCC diagnostic error "-std=c++11" #pragma GCC target("sse2") #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<iomanip> #include<cstring> #include<stack> using namespace std; stack<int>q; struct edge { int val,next,to; }e[300010]; int n,k,size; long long ans; int head[100010],dis[100010],in[100010]; bool flag[100010]; void edge_add(int,int,int); void SPFA(); int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) { int o,a,b; scanf("%d%d%d",&o,&a,&b); if(o==1) { edge_add(b,a,0); edge_add(a,b,0); } if(o==2) { edge_add(a,b,1); } if(o==3) { edge_add(b,a,0); } if(o==4) { edge_add(b,a,1); } if(o==5) { edge_add(a,b,0); } } for(int i=1;i<=n;i++)edge_add(0,i,1); SPFA(); for(int i=1;i<=n;i++)ans+=dis[i]; printf("%lld\n",ans); return 0; } void edge_add(int from,int to,int val) { e[++size].to=to; e[size].val=val; e[size].next=head[from]; head[from]=size; } void SPFA() { memset(dis,-0x3f,sizeof(dis)); memset(flag,false,sizeof(flag)); memset(in,0,sizeof(in)); q.push(0); dis[0]=0; flag[0]=true; while(!q.empty()) { int from=q.top(); q.pop(); flag[from]=false; in[from]++; if(in[from]>n+1) { printf("-1\n"); exit(0); } for(int i=head[from];i!=-1;i=e[i].next) { int to=e[i].to; int val=e[i].val; if(dis[to]<dis[from]+val) { dis[to]=dis[from]+val; if(flag[to]==false) { q.push(to); flag[to]=true; } } } } }

转载于:https://www.cnblogs.com/Lemir3/p/11079336.html

[Link 1]: https://www.luogu.org/problemnew/show/P3275
[Link 2]: https://www.cnblogs.com/Lemir3/p/11061539.html