noip的一些模板(参考了神牛的博客)
一、图论 1.单源最短路 洛谷P3371 (1)spfa 已加SLF优化 419ms 1#include2#include3#include4#include5usingnamespacestd;6constintN=1e4+5,M=5e5+5,INF=2147483647;7inlineintread(){8charc=getchar();intx=0,f=1;9while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11returnx*f;12}13intn,m,s,u,v,w;14structedge{15intv,ne,w;16}e[M<<1];17inth[N],cnt=0;18inlinevoidins(intu,intv,intw){19cnt++;20e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;21}22inlinevoidlop(int&x){if(x==N)x=1;elseif(x==0)x=N-1;}23intd[N],q[N],head,tail,inq[N];24voidspfa(ints){25for(inti=1;i<=n;i++)d[i]=INF;26head=tail=1;27q[tail++]=s;inq[s]=1;d[s]=0;28while(head!=tail){29intu=q[head++];inq[u]=0;lop(head);30for(inti=h[u];i;i=e[i].ne){31intv=e[i].v,w=e[i].w;32if(d[v]>d[u]+w){33d[v]=d[u]+w;34if(!inq[v]){35if(d[v]<d[q[head]])head--,lop(head),q[head]=v;36elseq[tail++]=v,lop(tail);37inq[v]=1;38}39}40}41}42}43intmain(){44n=read();m=read();s=read();45for(inti=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}46spfa(s);47for(inti=1;i<=n;i++)printf("%d",d[i]);48} (2)dijkstra 503ms 1#include2#include3#include4#include5#include6usingnamespacestd;7constintN=1e4+5,M=5e5+5,INF=2147483647;8inlineintread(){9charc=getchar();intx=0,f=1;10while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}11while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}12returnx;13}14intn,m,s,u,v,w;15structedge{16intv,ne,w;17}e[M];18inth[N],cnt=0;19inlinevoidins(intu,intv,intw){20cnt++;21e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;22}23structhn{24intu,d;25hn(inta=0,intb=0):u(a),d(b){}26booloperator<(consthn&r)const{returnd>r.d;}27};28priority_queueq;29intd[N],done[N];30voiddij(ints){31for(inti=1;i<=n;i++)d[i]=INF;32d[s]=0;33q.push(hn(s,0));34while(!q.empty()){35hnx=q.top();q.pop();36intu=x.u;if(done[u])continue;37done[u]=1;38for(inti=h[u];i;i=e[i].ne){39intv=e[i].v,w=e[i].w;40if(d[v]>d[u]+w){41d[v]=d[u]+w;42if(!done[v])q.push(hn(v,d[v]));//xiaoyouhua43}44}45}46}47intmain(){48n=read();m=read();s=read();49for(inti=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}50dij(s);51for(inti=1;i<=n;i++)printf("%d",d[i]);52} (3)dijkstra+配对堆 380ms 吊打用SLF优化的spfa啊啊啊啊啊 1#include2#include3#include4#include5#include6#definepapair7#definempmake_pair8usingnamespacestd;9usingnamespace__gnu_pbds;10typedef__gnu_pbds::priority_queue<pa,greater,thin>heap;11constintN=1e4+5,M=5e5+5,INF=2147483647;12inlineintread(){13charc=getchar();intx=0,f=1;14while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}15while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}16returnx*f;17}18intn,m,s,u,v,w;19structedge{20intv,ne,w;21}e[M];22inth[N],cnt=0;23inlinevoidins(intu,intv,intw){24cnt++;25e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;26}2728heapq;29heap::point_iteratorit[N];30intd[N];31voiddij(ints){32for(inti=1;i<=n;i++)d[i]=INF;33d[s]=0;34it[s]=q.push(mp(0,s));35while(!q.empty()){36intu=q.top().second;q.pop();37for(inti=h[u];i;i=e[i].ne){38intv=e[i].v,w=e[i].w;39if(d[v]>d[u]+w){40d[v]=d[u]+w;41if(it[v]!=0)q.modify(it[v],mp(d[v],v));42elseit[v]=q.push(mp(d[v],v));43}44}45}46}47intmain(){48n=read();m=read();s=read();49for(inti=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}50dij(s);51for(inti=1;i<=n;i++)printf("%d",d[i]);52} 2.判负环 VijosP1053Easy sssp 1#include2#include3#include4#include5usingnamespacestd;6constintN=1e3+5,M=1e5+5,INF=1e9+5;7inlineintread(){8charc=getchar();intx=0,f=1;9while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11returnx*f;12}13intn,m,s,u,v,w;14structedge{15intv,ne,w;16}e[M+N];17inth[N],cnt=0;18inlinevoidins(intu,intv,intw){19cnt++;20e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;21}22inlinevoidlop(int&x){x++;if(x==N)x=1;}23intq[N],head=1,tail=1,inq[N];24intd[N],nc[N];25boolspfa(ints){26head=tail=1;27for(inti=1;i<=n;i++)d[i]=INF,inq[i]=nc[i]=0;28q[tail]=s;inq[s]=nc[s]=1;lop(tail);29d[s]=0;30while(head!=tail){31intu=q[head];inq[u]=0;lop(head);32for(inti=h[u];i;i=e[i].ne){33intv=e[i].v,w=e[i].w;34if(d[v]>d[u]+w){35d[v]=d[u]+w;36if(!inq[v]){37inq[v]=1;q[tail]=v;lop(tail);38if(++nc[v]>n)returnfalse;39}40}41}42}43returntrue;44}45intmain(){46n=read();m=read();s=read();47for(inti=1;i<=m;i++){48u=read();v=read();w=read();49if(u==v&&w<0){printf("-1");return0;}50if(u!=v)ins(u,v,w);51}5253intss=n+1;//超级源54for(inti=1;i<=n;i++)ins(ss,i,0);55intflag=spfa(ss);56if(!flag){printf("-1");return0;}57spfa(s);58for(inti=1;i<=n;i++){59if(d[i]>=INF)printf("NoPath\n");60elseprintf("%d\n",d[i]);61}62} 3.最小生成树 洛谷P3366 kruskal 1#include2#include3#include4#include5usingnamespacestd;6constintN=5005,M=2e5+5,INF=1e9+5;7inlineintread(){8charc=getchar();intx=0,f=1;9while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11returnx*f;12}13intn,m,u,v,w;14intcnt=0;15structedge{16intu,v,w;17booloperator<(constedge&r)const{returnw<r.w;}18}e[M];19intfa[N];20inlineintfind(intx){returnx==fa[x]?x:fa[x]=find(fa[x]);}21intkruskal(){22intans=0,cnt=0;23for(inti=1;i<=n;i++)fa[i]=i;24sort(e+1,e+1+m);25for(inti=1;i<=m;i++){26intu=e[i].u,v=e[i].v,w=e[i].w;27intf1=find(u),f2=find(v);28if(f1!=f2){29ans+=w;30fa[f1]=f2;31cnt++;32if(cnt==n-1)break;33}34}35returnans;36}37intmain(){38n=read();m=read();39for(inti=1;i<=m;i++){40e[i].u=read();e[i].v=read();e[i].w=read();41}42intans=kruskal();43printf("%d",ans);44} 4.floyd (1)传递闭包 d[i][j]=d[i][j]||(d[i][k]&&d[k][j]) (2)最小环 Vijos P1046观光旅行 1#include2#include3#include4#include5usingnamespacestd;6constintN=105,M=1e4+5,INF=1e8+5;//1E9+1E9+1E9溢出7inlineintread(){8charc=getchar();intx=0,f=1;9while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11returnx*f;12}13intn,m,u,v,w,g[N][N];14intd[N][N],ans=INF;15voidfloyd(){16ans=INF;17for(intk=1;k<=n;k++){18for(inti=1;i<=k-1;i++)19for(intj=i+1;j<=k-1;j++)20ans=min(ans,g[i][k]+g[k][j]+d[i][j]);21for(inti=1;i<=n;i++)22for(intj=1;j<=n;j++)23d[i][j]=min(d[i][j],d[i][k]+d[k][j]);24}2526}27intmain(){28while(scanf("%d%d",&n,&m)!=EOF){29for(inti=1;i<=n;i++)for(intj=i+1;j<=n;j++)d[i][j]=d[j][i]=g[i][j]=g[j][i]=INF;30for(inti=1;i<=m;i++){31u=read();v=read();w=read();32d[u][v]=d[v][u]=g[u][v]=g[v][u]=w;33}34floyd();35if(ans==INF)puts("Nosolution.");36elseprintf("%d\n",ans);37}38} 5.割点 洛谷P3388 1#include2#include3#include4#include5usingnamespacestd;6constintN=1e5+5,M=1e5+5,INF=1e9+5;7inlineintread(){8charc=getchar();intx=0,f=1;9while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11returnx;12}13intn=0,m,u,v;14structedge{15intv,ne;16}e[M<<1];17inth[N],cnt=0;18inlinevoidins(intu,intv){19cnt++;20e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;21cnt++;22e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;23}24intdfn[N],low[N],dfc=0,iscut[N];25voiddfs(intu,intfa){26dfn[u]=low[u]=++dfc;27intchild=0;28for(inti=h[u];i;i=e[i].ne){29intv=e[i].v;30if(!dfn[v]){31child++;32dfs(v,u);33low[u]=min(low[u],low[v]);34if(low[v]>=dfn[u])iscut[u]=1;35}elseif(v!=fa)low[u]=min(low[u],dfn[v]);36}37if(fa==0&&child==1)iscut[u]=0;38}39intmain(){40n=read();m=read();41for(inti=1;i<=m;i++){u=read();v=read();ins(u,v);}42for(inti=1;i<=n;i++)if(!dfn[i])dfs(i,0);4344intans=0;45for(inti=1;i<=n;i++)if(iscut[i])ans++;46printf("%d\n",ans);47for(inti=1;i<=n;i++)if(iscut[i])printf("%d",i);48} 6.tarjan 强连通分量 POJ2186 1#include2#include3#include4#include5#include6usingnamespacestd;7constintN=1e4+5,M=5e4+5;8typedeflonglongll;9inlineintread(){10charc=getchar();intx=0,f=1;11while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}12while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}13returnx*f;14}15intn,m,u,v;16structedge{17intv,ne;18}e[M];19inth[N],cnt=0;20inlinevoidins(intu,intv){21cnt++;22e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;23}24intdfn[N],belong[N],low[N],dfc,scc,st[N],top;25intsize[N];26voiddfs(intu){27dfn[u]=low[u]=++dfc;28st[++top]=u;29for(inti=h[u];i;i=e[i].ne){30intv=e[i].v;31if(!dfn[v]){32dfs(v);33low[u]=min(low[u],low[v]);34}elseif(!belong[v])35low[u]=min(low[u],dfn[v]);36}37if(low[u]==dfn[u]){38scc++;39while(true){40intx=st[top--];41belong[x]=scc;42size[scc]++;43if(x==u)break;44}45}46}47intoutd[N],ind[N],ans;48voidpoint(){49for(intu=1;u<=n;u++)50for(inti=h[u];i;i=e[i].ne){51intv=e[i].v;52if(belong[u]!=belong[v])outd[belong[u]]++,ind[belong[v]]++;53}54}55intmain(){56n=read();m=read();57for(inti=1;i<=m;i++){u=read();v=read();ins(u,v);}58for(inti=1;i<=n;i++)if(!dfn[i])dfs(i);59point(); 60for(inti=1;i<=scc;i++){61if(outd[i]==0){62if(ans){ans=0;break;}63elseans=size[i]; 64}65}66printf("%d",ans);67} 7.二分图染色 1boolcolor(intu,intc){2col[u]=c; 3for(inti=h[u];i;i=e[i].ne){4intv=e[i].v;5if(col[u]==col[v])returnfalse;6if(!col[v]&&!color(v,3-c))returnfalse;7}8returntrue;9} 8.二分图最大匹配 洛谷P3386 1#include2#include3#include4#include5usingnamespacestd;6constintN=1005;7inlineintread(){8charc=getchar();intx=0,f=1;9while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11returnx*f;12}13intn,m,s,u,v;14structedge{15intv,ne;16}e[N*N<<1];17inth[N],cnt=0;18inlinevoidins(intu,intv){19cnt++;20e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;21}22intvis[N],le[N];23boolfind(intu){24for(inti=h[u];i;i=e[i].ne){25intv=e[i].v;26if(!vis[v]){27vis[v]=1;28if(!le[v]||find(le[v])){29le[v]=u;30returntrue;31}32}33}34returnfalse;35}36intans=0;37voidhungary(){38for(inti=1;i<=n;i++){39memset(vis,0,sizeof(vis));40if(find(i))ans++; 41}42}43intmain(){44n=read();m=read();intt=read();45for(inti=1;i<=t;i++){u=read();v=read();if(v>m)continue;ins(u,v);}46ans=0;47hungary();48printf("%d\n",ans);49} 9、tarjan缩点 洛谷p3387 1#include2#include3#include4#defineN100055#defineM1000056#defineINF1e97usingnamespacestd;8inttot,nxt[M],point[N],v[M],low[N],Dfn[N],nn,cnt,a[N],c[N],x[M],y[M];9inttot1,nxt1[M],point1[N],v1[M],f[N],out[N],stack[N],num,belong[N],ans;10boolvis[N];11voidaddline(intx,inty){++tot;nxt[tot]=point[x];point[x]=tot;v[tot]=y;}12voidaddline1(intx,inty){++tot1;nxt1[tot1]=point1[x];point1[x]=tot1;v1[tot1]=y;} 13voidtarjan(intx)14{15Dfn[x]=low[x]=++nn;vis[x]=1;stack[++cnt]=x;16for(inti=point[x];i;i=nxt[i]) 17if(!Dfn[v[i]])18{19tarjan(v[i]);20low[x]=min(low[x],low[v[i]]);21}22elseif(vis[v[i]])low[x]=min(low[x],Dfn[v[i]]);2324if(low[x]==Dfn[x])25{26num++;27while(stack[cnt]!=x)28{29c[num]+=a[stack[cnt]];30belong[stack[cnt]]=num;31vis[stack[cnt]]=0;32cnt--;33}34c[num]+=a[stack[cnt]];35belong[stack[cnt]]=num;36vis[stack[cnt]]=0;37cnt--;38}39}40voiddp(intx,intfa)41{42if(vis[x])return;43f[x]=c[x];vis[x]=1;intmaxx=0;44for(inti=point1[x];i;i=nxt1[i])45if(v1[i]!=fa)46{47dp(v1[i],x);48maxx=max(maxx,f[v1[i]]);49}50f[x]+=maxx;51}52intmain()53{54intn,m,i;55scanf("%d%d",&n,&m);56for(i=1;i<=n;i++)scanf("%d",&a[i]);57for(i=1;i<=m;i++)58{59scanf("%d%d",&x[i],&y[i]);60addline(x[i],y[i]);61}62for(i=1;i<=n;i++)63if(!Dfn[i])tarjan(i);64for(i=1;i<=m;i++)65if(belong[x[i]]!=belong[y[i]])66addline1(belong[x[i]],belong[y[i]]);67ans=-INF;68memset(vis,0,sizeof(vis));69for(i=1;i<=num;i++)70if(!vis[i])dp(i,0),ans=max(ans,f[i]);71printf("%d",ans);72} 数据结构 1.st表 1inta[N],f[N][21];23voidinit(intn){4for(inti=1;i<=n;i++)f[i][0]=a[i];56for(intj=1;j<=20;j++)7for(inti=1;i+(1<<j)-1<=n;i++)8f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);9}1011intRMQ(intl,intr){12intk=log(r-l+1)/log(2);//2^k<=l~r13returnmin(f[l][k],f[r-(1<<k)+1][k]);14} 2.trie树 1intch[N*L][27],size=0,val[N*L];2voidinsert(chars[],intn,intid){3intu=0;4for(inti=1;i<=n;i++){5intv=s[i]-'a';6if(!ch[u][v])ch[u][v]=++size;7u=ch[u][v];8}9val[u]=id;//printf("ins%d%d\n",u,id);10} 3.单调栈 求最大全flag子矩阵 1voidsol(intflag){2memset(tot,0,sizeof(tot));3for(inti=1;i<=n;i++){4top=0;5for(intj=1;j<=m;j++){6if(a[i][j]==flag)tot[j]++;7elsetot[j]=0;8datat;9t.h=tot[j];t.l=1;t.pos=j;10while(top&&st[top].h>=t.h){11intl=st[top].l+j-1-st[top].pos,h=st[top].h;12ans1=max(ans1,min(l,h)*min(l,h));13ans2=max(ans2,l*h);14t.l+=st[top].l;15top--;16}17st[++top]=t;18}19while(top){20intl=st[top].l+m-st[top].pos,h=st[top].h;21ans1=max(ans1,min(l,h)*min(l,h));22ans2=max(ans2,l*h);23top--;24}25}26} 4.单调队列 q[]保存的是下标 //删除while(head<=tail&&q[head]<=i-k)head++;//也可能<//插入while(heada[i])tail--;//单增q[++tail]=i; 5.并查集 带权 1for(inti=1;i<=n;i++)fa[i]=i,d[i]=0,s[i]=1;23intfa[N],d[N],s[N];4inlineintfind(intx){5if(x==fa[x])returnx;6introot=find(fa[x]);7d[x]+=d[fa[x]];8returnfa[x]=root;9} 6.树状数组 1模板23intlowbit(intx)4{5returnx&(-x);6}7voidmodify(intx,intadd)//一维8{ 9while(x<=MAXN) 10{ 11a[x]+=add; 12x+=lowbit(x); 13}14}15intget_sum(intx)16{ 17intret=0; 18while(x!=0) 19{ 20ret+=a[x]; 21x-=lowbit(x); 22} 23returnret;24}25voidmodify(intx,inty,intdata)//二维26{27for(inti=x;i<MAXN;i+=lowbit(i))28for(intj=y;j<MAXN;j+=lowbit(j))29a[i][j]+=data;30}31intget_sum(intx,inty)32{33intres=0;34for(inti=x;i>0;i-=lowbit(i))35for(intj=y;j>0;j-=lowbit(j))36res+=a[i][j];37returnres;38} 7.线段树 1//下面是某线段树模板题的代码：2#include3#include4usingnamespacestd;56typedeflonglongLL;7staticconstintmaxm=1e6+10;8LLtree[maxm],lazy[maxm],A[maxm],left[maxm],right[maxm];9intn,m;1011voidbuild(intnum,intl,intr){12left[num]=l;right[num]=r;13intmid=(l+r)>>1;14if(l==r){tree[num]=A[l];return;}15build(num<<1,l,mid);16build(num<<1|1,mid+1,r);17tree[num]=tree[num<<1]+tree[num<<1|1];18}1920voidpushdown(intnum){21if(lazy[num]){22intmid=(left[num]+right[num])>>1;23tree[num<<1]+=(mid-left[num]+1)*lazy[num];24tree[num<<1|1]+=(right[num]-mid)*lazy[num];25lazy[num<<1]+=lazy[num];26lazy[num<<1|1]+=lazy[num];27lazy[num]=0;28}29}3031voidupdate(intnum,intl,intr,LLadd){32if(left[num]>=l&&right[num]<=r){33tree[num]+=(right[num]-left[num]+1)*add;34lazy[num]+=add;35return;36}37if(left[num]>r||right[num]<l)return;38pushdown(num);39update(num<<1,l,r,add);40update(num<<1|1,l,r,add);41tree[num]=tree[num<<1]+tree[num<<1|1];42}4344LLQuery(intnum,intl,intr){45if(left[num]>=l&&right[num]<=r)returntree[num];46if(left[num]>r||right[num]<l)return0;47LLret=0;48pushdown(num);49ret+=Query(num<<1,l,r);50ret+=Query(num<<1|1,l,r);51returnret;52}5354intmain(){55scanf("%d%d",&n,&m);56for(inti=1;i<=n;i++)scanf("%lld",&A[i]);57build(1,1,n);58for(inti=1;i<=m;i++){59intf,x,y;LLadd;60scanf("%d",&f);61switch(f){62case1:scanf("%d%d%lld",&x,&y,&add);update(1,x,y,add);break;63case2:scanf("%d%d",&x,&y);printf("%lld\n",Query(1,x,y));break;64default:printf("Orz%%%");break;65}66}6768return0;69} //以下是维护序列的代码：(支持乘法运算)#includetypedeflonglongLL;staticconstintmaxm=100005; LLA[maxm],pls[maxm<<2],mul[maxm<<2],tr[maxm<<2];intleft[maxm<<2],right[maxm<<2];intn,m; LLMOD;intbuild(intid,intl,intr){ left[id]=l;right[id]=r;mul[id]=1;if(l==r)returntr[id]=A[l]%MOD,0;intmid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); tr[id]=(tr[id<<1]+tr[id<<1|1])%MOD; }voidpushdown(intid){intl=left[id];intr=right[id];intmid=(l+r)>>1; pls[id<<1]=(pls[id<<1]*mul[id]%MOD+pls[id])%MOD; pls[id<<1|1]=(pls[id<<1|1]*mul[id]%MOD+pls[id])%MOD; mul[id<<1]=(mul[id]*mul[id<<1])%MOD; mul[id<<1|1]=(mul[id]*mul[id<<1|1])%MOD; tr[id<<1]=(tr[id<<1]*mul[id]%MOD+pls[id]*(mid-l+1)%MOD)%MOD; tr[id<<1|1]=(tr[id<<1|1]*mul[id]%MOD+pls[id]*(r-mid)%MOD)%MOD; mul[id]=1;pls[id]=0; }voidmodify(intid,intl,intr,intc,intopt){if(left[id]>=l&&right[id]<=r){if(opt==1){ mul[id]=(mul[id]*c)%MOD; pls[id]=(pls[id]*c)%MOD; tr[id]=(tr[id]*c)%MOD; }elseif(opt==2){ pls[id]=(pls[id]+c)%MOD; tr[id]=(tr[id]+(LL)c*(right[id]-left[id]+1)%MOD)%MOD; }return; }if(right[id]r)return; pushdown(id); modify(id<<1,l,r,c,opt); modify(id<<1|1,l,r,c,opt); tr[id]=(tr[id<<1]+tr[id<<1|1])%MOD; } LLQuery(intid,intl,intr){if(left[id]>=l&&right[id]<=r)returntr[id]%MOD;if(left[id]>r||right[id]<l)return0; pushdown(id);return(Query(id<<1,l,r)%MOD+Query(id<<1|1,l,r)%MOD)%MOD; }intmain(){intopt,l,r,c; scanf("%d%lld",&n,&MOD);for(inti=1;i<=n;i++)scanf("%lld",&A[i]); scanf("%d",&m); build(1,1,n); while(m--){ scanf("%d",&opt);if(opt!=3){ scanf("%d%d%d",&l,&r,&c); modify(1,l,r,c,opt); }elsescanf("%d%d",&l,&r),printf("%lld\n",Query(1,l,r)%MOD); }return0; } 8、网络最大流 #includeusingnamespacestd;#defineinf233333333#defineilinlineilintgi() {inta=0;charx=getchar();boolf=0;while((x<'0'||x>'9')&&x!='-')x=getchar();if(x=='-')x=getchar(),f=1;while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();returnf?-a:a; }constintN=100005,M=10005;structedge{intto,net,w; }e[N*2];inth[M],cnt=1,n,m,s,t,ans,flow,dis[M]; queue<int>q; ilvoidadd(intu,intv,intw) { e[++cnt].to=v,e[cnt].w=w,e[cnt].net=h[u],h[u]=cnt; } ilintbfs() { memset(dis,-1,sizeof(dis)); dis[s]=0; q.push(s);while(!q.empty()) {intu=q.front(); q.pop();for(inti=h[u];i;i=e[i].net) {intv=e[i].to;if(dis[v]==-1&&e[i].w>0){dis[v]=dis[u]+1;q.push(v);} } }returndis[t]!=-1; } ilintdfs(intu,intop) {if(u==t)returnop;intflow=0,tmp=0;for(inti=h[u];i;i=e[i].net) {intv=e[i].to;if(dis[v]==dis[u]+1&&e[i].w>0){ tmp=dfs(v,min(op,e[i].w));if(!tmp)continue; op-=tmp;flow+=tmp; e[i].w-=tmp;e[i^1].w+=tmp;if(!op)break;//returntmp;} }returnflow; }intmain() { n=gi(),m=gi(),s=gi(),t=gi();intu,v,w;for(inti=1;i<=m;i++) { u=gi(),v=gi(),w=gi(); add(u,v,w),add(v,u,0); }while(bfs())ans+=dfs(s,inf); printf("%d\n",ans);return0; }
