赞
踩
栈思想:先进后出
tips:栈里能放下标就放下标
(牛客)小c的计事本(直接用stack可以简化代码,且不会被自己绕晕,当时没意识到)
(牛客)吐泡泡(没意识到用栈),(牛客)好串
1.后缀表达式(栈)
- #include <stack>
- #include <cstring>
- 栈
- 有关一些细节
- #include <iostream>
- #include <cstdio>
- #include <stdlib.h>
- using namespace std;
- int main()
- {
- char a,b[100];
- stack<int> s;
- int q=0;
- while(1)
- {
- while((a=getchar())!='.'&&(a!='@'))
- {
- if(a>='0'&&a<='9') b[q++]=a;//临时字符串存数字
- else//运算符
- {
- int x1,x2;//x2为前一个数,x1为后一个数
- x1=s.top();s.pop();
- if(s.empty())x2=0;//特判,若取完x1后栈空,则再取一个数为0
- if(!s.empty()){x2=s.top();s.pop();}
- if(a=='+')s.push(x1+x2);
- else if(a=='-')s.push(x2-x1);//
- else if(a=='*')s.push(x1*x2);
- else if(a=='/')s.push(x2/x1); //容易整反
- }
- }
- if(a=='@')break;
- s.push(atoi(b));//将字符转化为数字
- q=0;//重置
- memset(b,0,sizeof(b));
- }
- printf("%d",s.top());
- return 0;
- }

单调栈 :求第一个大于或小于 x的数
1.(洛谷)单调栈(记住stack一般存放下标)
- 单调栈
- 求第一个大于的数模板
- 从右往左扫描
- #include <cstdio>
- #include <stack>
- using namespace std;
- int a[10000000],f[10000000];//a存放输入,f存放答案
- int main()
- {
- int n,i;
- stack<int> q; //栈
- scanf("%d",&n);
- for(i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- }
- for(i=n;i>=1;i--)//倒叙录入
- {
- while(!q.empty()&&a[i]>=a[q.top()])q.pop();//若小于则pop出
- f[i]=q.empty()?0:q.top();//三目运算
- q.push(i);//存放数字下标 ****细节,省去了很多操作
- }
- for(i=1;i<=n;i++)
- {
- if(i>1)printf(" ");
- printf("%d",f[i]);
- }
- return 0;
- }

(牛客)小A的柱状图(单调栈总和应用)
- #include <iostream>
- #include <algorithm>
- #include <stack>
- using namespace std;
- const int maxn=1e6+7;
- int brr[maxn],sum1[maxn],sum2[maxn];
- long long ans,arr[maxn];
- pair<int,int>mark[maxn];//记录以该矩形为中心向两边扩散时的最小左坐标和最大右坐标
- inline long long get_s(int x,int y,int i)
- {
- return arr[i]*(sum1[x]-sum1[y+1]);
- }
- int main()
- {
- int n;scanf("%d",&n);
- stack<int>s;//存放数字下标而非数字,可以省很多操作
- for(int i=1;i<=n;i++)
- {
- scanf("%d",brr+i);//宽度
- sum2[i]=brr[i]+sum2[i-1];//记录从左到右的宽度前缀和
- }
- for(int i=1;i<=n;i++)
- {
- scanf("%lld",arr+i);//长度
- }
- //
- sum1[n+1]=0;
- for(int i=n;i>=1;i--)
- {
- sum1[i]=sum1[i+1]+brr[i];//记录从右到左的宽度前缀和
- }
- //从右-左遍历arr,查找从左-右第一个小于第i个元素的坐标
- arr[n+1]=-maxn;//将栈底设为最小值
- s.push(n+1);
- for(int i=n;i>=1;i--)
- {
- while(arr[i]<=arr[s.top()])s.pop();//栈顶如果比待处理值大,出栈
- mark[i].second=s.top()-1;//最大右坐标(即从左到右第一个小于arr[i]的值的坐标-1)
- //ans=max(ans,get_s(i,s.top()-1));//此时栈顶比待处理值小
- s.push(i);
- }
- //从左-右遍历arr,查找从右-左第一个小于第i个元素的坐标
- stack<int>ss;ss.push(0);arr[0]=-maxn;
- for(int i=1;i<=n;i++)
- {
- while(arr[i]<=arr[ss.top()])ss.pop();
- mark[i].first=ss.top()+1;
- ans=max(ans,get_s(mark[i].first,mark[i].second,i));
- ss.push(i);
- }
- printf("%lld",ans);
- return 0;
- }

--------------------------------------------------------------------------------------------------------------------------------
队列***
队列思想:先进先出
(牛客)Keep In Line(很快做出来了)
(洛谷)约瑟夫问题(循环队列)
- 循环队列
- #include <cstdio>
- #include <iostream>
- #include <queue>
- using namespace std;
- int main()
- {
- int n,m,i,k=0;
- queue<int> q;
- scanf("%d %d",&n,&m);
- for(i=1;i<=n;i++)
- q.push(i);
- while(!q.empty())
- {
- for(i=1;i<=m-1;i++)
- {
- q.push(q.front());//将队头元素放队尾
- q.pop();
- }
- if(k>0)printf(" ");
- printf("%d",q.front());
- k++;
- q.pop();
- }
- return 0;
- }

5.队列安排(list容器*****(唯一用处啊:迭代器数组和s.insert(pos,elem)返回值用处)
- 迭代器数组以及s.insert(pos,elem)返回值的用处
- #include <list>
- #include <algorithm>
- #include <iostream>
- #define maxn 100010
- using namespace std;
- list<int>s;
- int k=0;
- list<int>::iterator pos[maxn];//存放迭代器的数组
- bool erased[maxn];//判断是否重复删除(优化速度)//初始值为false***
- void print(int val)
- {
- if(k)cout<<" ";
- cout<<val;
- k++;
- }
- int main()
- {
- int k,p,n,m;
- s.insert(s.begin(),1);
- pos[1]=s.begin();
- cin>>n;
- for(int i=2;i<=n;i++)
- {
- cin>>k>>p;
- if(p==1)
- {
- list<int>::iterator nextpos=pos[k];
- nextpos++;
- pos[i]=s.insert(nextpos,i);//s.insert返回elem插入的位置(迭代器),用pos[i]来接收元素i的位置
- }
- else
- {
- pos[i]=s.insert(pos[k],i);
- }
- }
- cin>>m;
- for(int i=0;i<m;i++)
- {
- int x;
- cin>>x;
- if(!erased[x])//不重复删除(优化速度)
- {
- s.erase(pos[x]);
- erased[x]=true;
- }
-
- }
- for_each(s.begin(),s.end(),print);
- return 0;
- }

(牛客)滑动窗口(单调队列(不是用stl的队列))
- 单调队列
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- const int maxn = 1e6+7;
- int arr[maxn],qu[maxn],pu[maxn];
- int main()
- {
- int n,k;scanf("%d%d",&n,&k);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",arr+i);
- }
- //单调递增队列维护最小值
- int l=1,r=0;
- for(int i=1;i<=n;i++)
- {
- while(l<=r&&arr[i]<=qu[r])
- {
- r--;
- }
- qu[++r]=arr[i];//待处理值入队
- pu[r]=i;//记录编号
- if(i-pu[l]>=k)//队首元素过时,出队
- {
- l++;
- }
- if(i>=k)printf("%d ",qu[l]);//输出最小值,即队首元素
- }
- cout<<endl;
- //单调递减队列维护最大值
- l=1,r=0;memset(qu,0,sizeof qu);memset(pu,0,sizeof pu);
- for(int i=1;i<=n;i++)
- {
- while(l<=r&&arr[i]>=qu[r])
- {
- r--;
- }
- qu[++r]=arr[i];
- pu[r]=i;
- if(i-pu[l]>=k)
- {
- l++;
- }
- if(i>=k)printf("%d ",qu[l]);
- }
- return 0;
- }

--------------------------------------------------------------------------------------------------------------------------------
堆(**优先队列**):一个能够维护当前最大/最小值的队列
(牛客)优先队列,并查集题单:
合并果子,第k小,tokisukaze and soldier,建筑抢修,缓存交换(似懂非懂)(目前有点不理解什么题要用到堆)
对顶堆(洛谷:中位数)(用于*动态*维护第k大的数,,eg,中位数)
- 对顶堆,求解中位数
- #include <iostream>
- #include <queue>
- #include <algorithm>
- #include <vector>
- using namespace std;
- priority_queue<int,vector<int>,greater<int>>last;//小根堆
- priority_queue<int,vector<int>>pre;//大根堆
- int main()
- {
- int n,ch;
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>ch;
- if(!pre.size()||ch<pre.top())
- {
- pre.push(ch);
- }
- else if(ch>pre.top())
- {
- last.push(ch);
- }
- int u=pre.size(),v=last.size();
- while(abs(u-v)>1) //使大小根堆元素个数差值<=1直接abs(pre.size()...洛谷会报错dev不会
- {
- if(pre.size()>last.size())
- {
- last.push(pre.top());pre.pop();
- }
- else
- {
- pre.push(last.top());last.pop();
- }
- u=pre.size(),v=last.size();
- }
- if(i%2!=0)
- {
- if(pre.size()>last.size())cout<<pre.top()<<endl;
- else cout<<last.top()<<endl;
- }
- }
- return 0;
- }

对顶堆2(牛客:直播获奖)
- 直播获奖
- 用multiset来自动排序求第p大的数,复杂度o(n^2),tle了
- 而对顶堆可以动态维护第k大的值
- #include <queue>
- #include <algorithm>
- #include <vector>
- #include <iostream>
- using namespace std;
- priority_queue<int>pre;
- priority_queue<int,vector<int>,greater<int>>last;
- int main()
- {
- int n,w,p;scanf("%d%d",&n,&w);
- for(int i=1;i<=n;i++)
- {
- int ch;
- scanf("%d",&ch);
- if(!last.size()||ch>last.top())
- {
- last.push(ch);
- }
- else
- {
- pre.push(ch);
- }
- p=max(1,(int)(i*w/100));
- while(last.size()!=p)//令大根堆的数量=p,则大根堆的top即是两个队列中排位第p的元素
- {
- if(last.size()<p)
- {
- last.push(pre.top());pre.pop();
- }
- else
- {
- pre.push(last.top());last.pop();
- }
- }
- printf("%d ",last.top());
- }
- return 0;
- }

对顶堆3 (牛客)第k小
st表(o(logn)预处理,o(1)查找静态区间最大值)
(洛谷)【模板】ST 表
视频:STUACM-算法讲堂-ST表(区间最值问题)_哔哩哔哩_bilibili
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- int n,m,dp[111111][40];//定义dp[i][j]为从起点i开始长度为2的j次方(1<<j)的区间的最大值
- int main()
- {
- scanf("%d %d",&n,&m);
- for(int i=1;i<=n;i++)scanf("%d",&dp[i][0]);
- int lc=(int)(log(n)/log(2));//计算log2(n),即最大的 j
- for(int j=1;j<=lc;j++)//i和j不能换,从小区间推大区间
- {
- for(int i=1;i+(1<<j)-1<=n;i++)//RE的原因大概是循环条件写错了
- {
- dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);//区间对半分开
- }
- }
- while(m--)
- {
- int l,r;
- scanf("%d %d",&l,&r);
- int x=(int)(log(r-l+1)/log(2));//计算log2(len),为向下取整数
- printf("%d\n",max(dp[l][x],dp[r-(1<<x)+1][x]));//这里的区间大概率有重叠,但不影响答案
- }
- return 0;
- }

---------------------------------------------------------------------------------------------------------------------------------
1.***差分:(牛客)借教室
题解:(25条消息) 【每日一题】7月1日题目精讲 借教室_Jozky86的博客-CSDN博客
二维差分+二维前缀和 (牛客)瓜瓜选妃 K-瓜瓜选妃_浙江农林大学第二十二届程序设计竞赛(同步) (nowcoder.com)
- #include <iostream>
- #include <cstring>
- using namespace std;
- int n,m,k,x1[111111],y1[111111],x2[111111],y2[111111],sum[600][600],ans=-1;
- bool check(int x)
- {
- memset(sum,0,sizeof sum);
- for(int i=1;i<=x;i++)
- {
- sum[x1[i]][y1[i]]++;//二维差分
- sum[x1[i]][y2[i]+1]--;//哪些地方要加1?有2的地方
- sum[x2[i]+1][y1[i]]--;
- sum[x2[i]+1][y2[i]+1]++;
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//二维前缀和
- if(!sum[i][j])return false; //注意一定是+=
- }
- }
- return true;
- }
- int main()
- {
- cin>>n>>m>>k;
- for(int i=1;i<=k;i++)
- {
- cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
- }
- int l=1,r=k;
- while(l<=r)
- {
- int mid=(l+r)>>1;
- if(check(mid))
- {
- r=mid-1;
- ans=mid;
- }
- else
- {
- l=mid+1;
- }
- }
- cout<<ans;
- return 0;
- }

(acwing 1761)二维前缀和+二维差分+(二维前缀和中对面积的特殊处理)
图解:
(牛客)货物种类 *
(map存点的前缀和,差分)acwing:4195(具有特殊性,一般差分题用不到,因为不能维护每个点的状态)
2.***前缀和(写之前记得数据上下界,让数据下界从1开始(因为sum[i]=sum[i-1])
若从0开始可能回忽略掉sum[0]的情况
异或前缀和:(牛客)Xorto
二维前缀和:(牛客)「土」秘法地震
图解
(牛客)储物点的距离
(牛客)激光炸弹
(牛客)周周的泡泡(用前缀和+二分 枚举任意长的一段区间(符合题意的))
L-周周的泡泡_浙江农林大学第二十二届程序设计竞赛(同步) (nowcoder.com)
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define ll long long
- ll sum[222222],ans=-1;
- int n,h,arr[222222];
- int main()
- {
- scanf("%d %d",&n,&h);
- for(int i=1;i<=n;i++)//思路:用前缀和来表示中间x个连续的泡泡的高度和
- { //(考场上任意x个连续泡泡的高度和不会用nlgn枚举,虽然想到upper,但是不知道搜啥)
- scanf("%d",&arr[i]);
- sum[i]=sum[i-1]+arr[i];
- }
- if(sum[n]<h){cout<<h-sum[n];return 0;}//如果不用删
- for(int i=1;i<=n;i++)
- {
- int x=upper_bound(sum+1,sum+1+n,sum[n]+sum[i-1]-h)-sum;//二分查找
- if(i<=x&&x<=n)
- ans=max(ans,sum[n]-sum[x]+sum[i-1]);
- //x表示连续泡泡的右区间,用i来枚举左区间
- //sum[n]-(sum[x]-sum[i-1])<h
- //sum[n]+sum[i-1]-h<sum[x]
- }
- cout<<h-ans;
- return 0;
- }

3.***并查集
有时不开sz数组来比较,直接合并可能会爆内存
(牛客)经商
(牛客)(类似二维并查集)小c的周末
(牛客)奶酪
(牛客)「Nhk R1 C」Zet'ubou Another(并查集解决联通块+思维)
(天梯赛)L2-013 红色警报 (动态判断割点)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- #define N 600
- #define M 5005*2
- int n,m,sum,cnt;
- int head[N],k,fa[N];
- int vis1[N],vis2[N];
- struct EDGE
- {
- int x,y;
- }edge[M];
-
- int f_ind(int x)
- {
- return fa[x]=fa[x]==x?x:f_ind(fa[x]);
- }
- int judge()
- {
- int sum=0;
- memset(vis2,0,sizeof vis2);
- for(int i=0;i<n;i++)fa[i]=i;
-
- for(int i=1;i<=cnt;i++)
- {
- int x =edge[i].x;
- int y =edge[i].y;
- if(vis1[x]||vis1[y])continue;//如果这个点被删了,这条边就不要了
-
- fa[f_ind(x)]=fa[f_ind(y)];
- }
- for(int i=0;i<n;i++)
- {
- if(vis1[i])continue;//该点已经被删掉
- int x = f_ind(i);
- if(!vis2[x])//这个集合被统计过了
- {
- sum++;
- vis2[x]=1;
- }
- }
- //cout<<sum<<endl;
- return sum;
- }
- int main()
- {
- cin>>n>>m;
- while(m--)
- {
- int x=0,y=0;
- cin>>x>>y;
- edge[++cnt].x=x;
- edge[cnt].y=y;
- }
- int las = 0;
- las = judge();//判断集合个数,用las记录上一次统计的集合数
- cin>>k;
- int tem = n;
- for(int i=1;i<=k;i++)
- {
- int x=0;
- cin>>x;
- vis1[x]=1;//删点
- int tmp = judge();
- //cout<<tmp<<endl;
- if(las<tmp)//如果删了这个点,集合数变多了,则该点是割点
- printf("Red Alert: City %d is lost!\n",x);
- else printf("City %d is lost.\n",x);
- tem--;
- if(tem<=0)cout<<"Game Over."<<endl;
- las = tmp;
- }
- return 0;
- }

种类并查集:
(牛客)食物链 讲解:并查集专题讲解 边带权+扩展域_哔哩哔哩_bilibili
(牛客)关押罪犯
带权并查集
(牛客)食物链 图解:
讲解:AcWing 240 食物链(并查集)_哔哩哔哩_bilibili
- #include <iostream>
- using namespace std;
- int n,k,fa[60000],d[60000];
- long long ans;
- int mod(int x)
- {
- return (x+3)%3;
- }
- int f_ind(int x)
- {
- if(fa[x]==x)return x;
- int root=f_ind(fa[x]);
- d[x]=mod(d[x]+d[fa[x]]);
- fa[x]=root;
- return fa[x];
- }
- void Union(int x,int y,int t)
- {
- int fx=f_ind(x),fy=f_ind(y);
- fa[fx]=fy;
- d[fx]=mod(t+d[y]-d[x]);
-
- return;
- }
- int main()
- {
- scanf("%d %d",&n,&k);
- for(int i=1;i<=n;i++)fa[i]=i;
- while(k--)
- {
- int t,x,y;
- scanf("%d %d %d",&t,&x,&y);
- if((x==y&&t==2)||x>n||y>n)ans++;
- else if(t==1)
- {
- if(f_ind(x)==f_ind(y))//在一个集合里
- {
- if(mod(d[x])!=mod(d[y]))ans++;
- }
- else//不在一个集合里
- {
- Union(x,y,0);//将x和y以同类形式合并
- }
- }
- else if(t==2)
- {
- if(f_ind(x)==f_ind(y))//已经在一个集合内
- {
- if(mod(d[x]-d[y])!=1)ans++;
- }
- else//不在一个集合
- {
- Union(x,y,1);
- }
- }
- }
- cout<<ans;
- return 0;
- }

---------------------------------------------------------------------------------------------------------------------------------
线段树与树状数组
线段树1(模板)(区间加法,区间乘法,区间求和)(也可实现单点修改,求单点值)
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- #define ll long long
- #define inf 0x3f3f3f3f
- ll a[111111],n,m,mod=inf;
- struct Tree
- {
- ll l,r,add,mul=1,sum;
- }t[444444];//线段树要开4倍空间
- inline void push_up(ll p)
- {
- t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
- }
- inline void push_down(ll p)
- {
- t[p*2].sum=(t[p].mul*t[p*2].sum+((t[p*2].r-t[p*2].l+1)*t[p].add)%mod)%mod;
- t[p*2+1].sum=(t[p].mul*t[p*2+1].sum+(t[p].add*(t[p*2+1].r-t[p*2+1].l+1))%mod)%mod;//add已经乘过mu啦
-
- t[p*2].add=(t[p*2].add*t[p].mul+t[p].add)%mod;//sum和add一样,都是先乘后加
- t[p*2+1].add=(t[p*2+1].add*t[p].mul+t[p].add)%mod;
-
- t[p*2].mul=(t[p*2].mul*t[p].mul)%mod;
- t[p*2+1].mul=(t[p*2+1].mul*t[p].mul)%mod;
-
-
- t[p].mul=1,t[p].add=0;
- }
- void build_tree(ll p,ll l,ll r)
- {
- t[p].l=l;
- t[p].r=r;
- t[p].mul=1;
- if(l==r)
- {
- t[p].sum=a[l]%mod;
- return;
- }
- else
- {
- ll mid=(l+r)>>1;//基本上是只有建树才会用到mid
- build_tree(p*2,l,mid);
- build_tree(p*2+1,mid+1,r);
- push_up(p);
- }
- }
- void add(ll p,ll l,ll r,ll k)
- {
- if(l<=t[p].l&&r>=t[p].r)
- {
- t[p].sum=((t[p].r-t[p].l+1)*k+t[p].sum)%mod;//这里偶尔会写错
- t[p].add=(t[p].add+k)%mod;
- }
- else if(t[p].l>r||t[p].r<l)return;
- else
- {
- push_down(p);
- add(p*2,l,r,k);
- add(p*2+1,l,r,k);
- push_up(p);
- }
- }
- void mul(ll p,ll l,ll r,ll k)
- {
- if(l<=t[p].l&&r>=t[p].r)
- {
- t[p].mul=(t[p].mul*k)%mod;
- t[p].add=(t[p].add*k)%mod;//直接乘,不能放后面乘
- t[p].sum=(t[p].sum*k)%mod;
- }
- else if(t[p].l>r||t[p].r<l)return;
- else
- {
- push_down(p);
- mul(p*2,l,r,k);
- mul(p*2+1,l,r,k);
- push_up(p);
- }
- }
- ll query(ll p,ll l,ll r)
- {
- if(l<=t[p].l&&r>=t[p].r)
- {
- return t[p].sum;
- }
- else if(t[p].l>r||t[p].r<l)return 0;
- else
- {
- push_down(p);
- ll val1=query(p*2,l,r)%mod;
- ll val2=query(p*2+1,l,r)%mod;
- return (val1+val2)%mod;
- }
- }
- int main()
- {
- cin>>n>>m>>mod;
- for(int i=1;i<=n;i++)cin>>a[i];
- build_tree(1,1,n);
- for(int i=1;i<=m;i++)
- {
- int num,x,y,k;
- cin>>num>>x>>y;
- if(num==1)
- {
- cin>>k;
- mul(1,x,y,k);
- }
- else if(num==2)
- {
- cin>>k;
- add(1,x,y,k);
- }
- else
- {
- cout<<query(1,x,y)%mod<<endl;
- }
- }
- return 0;
- }

线段树求区间最大值
(洛谷)I Hate It
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- #define ll long long
- #define inf 0x3f3f3f3f
- ll a[211111],n,m,mod=inf;
- struct Tree
- {
- ll l,r,add,sum,mx;
- }t[844444];//线段树要开4倍空间
- inline void push_up(ll p)
- {
- t[p].sum=(t[p*2].sum+t[p*2+1].sum);
- t[p].mx=max(t[p*2].mx,t[p*2+1].mx);//回溯
- }
- inline void push_down(ll p)
- {
- t[p*2].sum+=t[p].add*(t[p*2].r-t[p*2].l+1);
- t[p*2+1].sum+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
-
- t[p*2].add+=t[p].add;
- t[p*2+1].add+=t[p].add;
-
- t[p].add=0;
- }
- void build_tree(ll p,ll l,ll r)
- {
- t[p].l=l;
- t[p].r=r;
- if(l==r)
- {
- t[p].sum=a[l];
- t[p].mx=t[p].sum;//到一个点就取mx
- return;
- }
- else
- {
- ll mid=(l+r)>>1;
- build_tree(p*2,l,mid);
- build_tree(p*2+1,mid+1,r);
- push_up(p);
- }
- }
- ll querymax(ll p,ll l,ll r)
- {
- if(t[p].l>=l&&t[p].r<=r)
- {
- return t[p].mx;
- }
- else if(t[p].l>r||t[p].r<l)
- {
- return 0;
- }
- else
- {
- push_down(p);
- ll mx=max(querymax(p*2,l,r),querymax(p*2+1,l,r));
- push_up(p);
- return mx;
- }
- }
- void add(ll p,ll l,ll r,ll k)
- {
- if(t[p].l>=l&&t[p].r<=r)
- {
- t[p].sum+=k*(t[p].r-t[p].l+1);
- t[p].add+=k;
- if(l==r)t[p].mx=t[p].sum;//修改单点取mx
- }
- else if(t[p].l>r||t[p].r<l)
- {
- return;
- }
- else
- {
- push_down(p);
- add(p*2,l,r,k);
- add(p*2+1,l,r,k);
- push_up(p);
- }
- }
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)cin>>a[i];
- build_tree(1,1,n);
- for(int i=1;i<=m;i++)
- {
- char c;cin>>c;
- int x,y;cin>>x>>y;
- if(c=='Q')
- {
- cout<<querymax(1,x,y)<<endl;
- }
- else if(c=='U')//根据题目单点修改
- {
- if(a[x]<y)
- {
- add(1,x,x,y-a[x]);
- a[x]=y;
- }
- }
- }
- return 0;
- }

(牛客)魔法学院(easy version)(区间修改,lazy标记,思维)
(牛客提单:线段树)
[JSOI2008]最大数MAXNUMBER(线段树后插入元素)
数据结构(维护平方和)
区区区间(思维+特殊一点的lazy)
(acwing)区间最大子段和(线段树的区间最大子段和问题)(经典)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=555555;
- const ll M=55555;
- typedef pair<int,int> PII;
- int n,m,a[N];
- struct T
- {
- int l,r,sum,lmx,rmx,dat;
- }t[N*4];
- inline void push_up(T &u,T &l,T &r)
- {
- u.sum = l.sum + r.sum;
- u.lmx = max(l.lmx, l.sum + r.lmx);
- u.rmx = max(r.rmx, r.sum + l.rmx);
- u.dat = max(max(l.dat, r.dat), l.rmx + r.lmx);
- }
- inline void push_up(int p)
- {
- push_up(t[p],t[p*2],t[p*2+1]);
- }
- void build(int p,int l,int r)
- {
- t[p].l=l;
- t[p].r=r;
- if(l==r)
- {
- t[p]={l,r,a[l],a[l],a[l],a[l]};
- return;
- }
- else
- {
- int mid=(l+r)>>1;
- build(p*2,l,mid);
- build(p*2+1,mid+1,r);
- push_up(p);
- }
- }
- T query(int p,int l,int r)
- {
- if(t[p].l>=l&&t[p].r<=r)
- {
- return t[p];
- }
- else
- {
- int mid=(t[p].l+t[p].r)>>1;
- if(r<=mid) return query(p*2,l,r);//l,r完全在左边
- else if(l>mid) return query(p*2+1,l,r);//完全在右边
- else//横跨了中点,此时res= max(tl的最大子段和,tr的最大子段和,跨越区间中点的最大子段和)
- { //此时l,r所围成的区间大概率是原树没有的,所以递归不断分割这个区间,直到所有的子区间都能在树中找到,回溯时,因为返回的区间极大概率不是p的子节点
- //用L,R来记录他们的信息,通过建立虚拟父节点res并用push_up函数合并区间,更新答案,但push_up操作需要他们的除了l,r的信息,所以query要返回结构体,
- auto L=query(p*2,l,r);
- auto R=query(p*2+1,l,r);
- T res;
- push_up(res,L,R);
- return res;
- }
- }
- }
- void update(int p,int x,int y)
- {
- if(t[p].l==t[p].r&&t[p].r==x)
- {
- t[p]={x,x,y,y,y,y};//因为是单点修改,所以全都要改
- }
- else if(t[p].l>x||t[p].r<x)return;
- else
- {
- update(p*2,x,y);
- update(p*2+1,x,y);
- push_up(p);
- }
- }
- //考虑由左右两个区间子区间tl,tr,得到当前区间的最大子段和ans,则有ans=max(tl的最大子段和,tr的最大子段和,跨越区间中点的最大子段和)
- //而跨越区间中点的最大子段和可用tl的前缀和(rmx)以及tr的后缀和得来(lmx),将这两个信息加到线段树数组内,且动态维护(具体见push_up)
- //查询操作较为复杂,可仔细看看
- int main()
- {
- scanf("%d %d",&n,&m);
- for(int i=1;i<=n;i++)scanf("%d",a+i);
- build(1,1,n);
- while(m--)
- {
- int k,x,y;
- scanf("%d %d %d",&k,&x,&y);
-
- if(k==1)
- {
- if(x>y)swap(x,y);
- printf("%d\n",query(1,x,y).dat);
- }
- else
- {
- update(1,x,y);
- }
- }
- return 0;
- }

扫描线+线段树 求二维平面上的矩阵的总面积
基本思想:(33条消息) 线段树+扫描线(有关扫描线的理解)_sdau_blue的博客-CSDN博客_线段树扫描线
(acwing)亚特兰蒂斯(扫描线+线段树+离散化并去重)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=10100;
- const ll M=55555;
- typedef pair<int,int> PII;
- int T=1,n;
- vector<double>ys;//离散化的数组
- struct segment//存储线段信息
- {
- double x,y1,y2;
- int d;
- bool operator<(const segment&t)
- {
- return x<t.x;
- }
- }seg[N*2];//一个矩阵有两条线段
-
-
- //因为要动态维护线段信息,所以线段树的每个节点,保存的为线段,0号点保存的是ys[0]~ys[1],(离散化后的,即ys数组上的序号为0和序号为1的点)以此类推
- struct node
- {
- int l,r;//[l,r]不是线段的范围,是该节点的孩子的范围,建树中体现
- int cnt;//记录这段区间出现次数
- double len;//区间长度
- }t[N*2*4];//一个矩阵有两条线段,再*4
-
- //此题为经典题型:扫描线+线段树解决二维平面的矩形总面积
- //首先输入并存线段信息到seg数组,然后离散化并去重 y值,(不然有无穷多的点),得到y值范围后建树,将seg按x值排序,然后在线段树上用扫描线算法,并动态维护树,记录答案
-
- void build(int p,int l,int r)
- {
- t[p].l=l,t[p].r=r;
- if(t[p].l==t[p].r)return;//忘写这个就一直递归下去了
- int mid=(l+r)>>1;
- build(p*2,l,mid);
- build(p*2+1,mid+1,r);
-
- }
- int find(double x)
- {
- return lower_bound(ys.begin(),ys.end(),x)-ys.begin();//返回x在ys中的序号
- }
- void pushup(int p)
- {
- //全覆盖
- if(t[p].cnt)t[p].len=ys[t[p].r+1]-ys[t[p].l];//t[p].r为其最右边的孙子的序号,其代表ys[t[p].r]~ys[t[p].r+1],所以表示长度时,其要+1
-
- else if(t[p].l!=t[p].r)//不是叶子节点,len可由子节点更新
- {
- t[p].len=t[p*2].len+t[p*2+1].len;
- }
-
- else t[p].len=0;//没有被覆盖
- //补充:第一种情况,是被一次性完全覆盖,而第二种情况也有可能被完全覆盖,但是分次的,比如之前有线段覆盖其的子节点,然后这次通过update的else语句进入其剩下子节点
- //覆盖完其剩下子节点后回溯回来,进行pushup时,虽然cnt=0,但已经完全被覆盖了。
- }
- void update(int p,int l,int r,int d)
- {
- if(t[p].l>=l&&t[p].r<=r)
- {
- t[p].cnt+=d;
- pushup(p);//更新自己的len,否则不能更新父亲的len
- }
- else if(t[p].l>r||t[p].r<l)return;
- else
- {
- update(p*2,l,r,d);
- update(p*2+1,l,r,d);
- pushup(p);
- }
- }
- int main()
- {
- while(scanf("%d",&n),n)
- {
- ys.clear();
- int j=0;
- for(int i=0;i<n;i++)
- {
- double x1,y1,x2,y2;
- scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
- seg[j++]={x1,y1,y2,1};
- seg[j++]={x2,y1,y2,-1};
-
- ys.push_back(y1);ys.push_back(y2);
- }
- sort(seg,seg+j);//按x轴排序
-
- sort(ys.begin(),ys.end());//离散化并去重
- ys.erase(unique(ys.begin(),ys.end()),ys.end());
-
- build(1,0,ys.size()-2);//因为从0开始,所以-1,又因为线段树节点信息保存的是线段,即t[0]为ys[0]~ys[1]的线段信息,所以建树的范围再-1
- double res=0;
- for(int i=0;i<j;i++)
- {
- //根节点的长度即为此时有效线段长度 ,再 * x轴长度即为面积
- if(i>0)
- res+=t[1].len*(seg[i].x-seg[i-1].x);
-
- update(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].d);//update(p,l,r,d),其中l和r都是节点的编号,而find(seg[i].y2)-1为维护[ys[find(seg[i].y2)-1],ys[find(seg[i].y2)]]的线段的节点的编号
- }
- printf("Test case #%d\n",T++);
- printf("Total explored area: %.2lf\n\n",res);
- }
- return 0;
- }

树状数组
树状数组基本函数的原理:【算法讲堂】【电子科技大学】【ACM】树状数组与ST表_哔哩哔哩_bilibili
(acwing)楼兰图腾(单点修改+区间求和)(模板)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=30;
- const ll M=111111;
- typedef pair<int,int> PII;
- int n,a[N],t[N],Greater[N],Lower[N];
- ll res1,res2;
- int lowbit(int x)
- {
- return x & -x;
- }
- int sum(int x)
- {
- int res=0;
- for(int i=x;i;i-=lowbit(i))
- {
- res+=t[i];
- }
- return res;
- }
- void add(int x,int c)
- {
- for(int i=x;i<=n;i+=lowbit(i))
- {
- t[i]+=c;
- }
- }
-
- //思路:枚举每一个点作为中间点,求其左边和右边大于(小于)它的点的数量并相乘,将答案累加,即为第一问和第二问答案
- //以第一问为例,枚举点的时候维护其左边大于它的点的数量 可正向扫描,因为输入为1~n的排列,可用一个数组t[i]来维护值为i的点的数量,再求前缀和,则sum(n)则为此时统计的点的数量
- //sum(a[i])则为值为1~a[i]的点的数量,sum(n)-sum(a[i])则为左边大于它的点的数量(区间求和),因为同时要维护 t数组,要单点修改,,考虑到只是要实现区间求和和单点修改,可用树状数组
-
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)cin>>a[i];//数组为1~n的排序
-
- for(int i=1;i<=n;i++)
- {
- int y=a[i];
- Greater[i]=sum(n)-sum(y);
- Lower[i]=sum(y-1);//比y小的点的数量
- add(y,1);
- }
-
- memset(t,0,sizeof t);//清0
-
- for(int i=n;i>=1;i--)//反向扫描,维护右边比y大和右边比y小的点的数量
- {
- int y=a[i];
- res1+=Greater[i]*(ll)(sum(n)-sum(y));
- res2+=Lower[i]*(ll)(sum(y-1));
- add(y,1);
- }
-
- cout<<res1<<" "<<res2;
- return 0;
- }

(acwing)谜一样的牛(思维+求前缀和+单点修改)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=101000;
- const ll M=55555;
- typedef pair<int,int> PII;
- int n,a[N],t[N],ans[N];
- int lowbit(int x)
- {
- return x & -x;
- }
- void add(int x,int c)
- {
- for(int i=x;i<=n;i+=lowbit(i))
- {
- t[i]+=c;
- }
- }
- int sum(int x)
- {
- ll ans=0;
- for(int i=x;i;i-=lowbit(i))ans+=t[i];
- return ans;
- }
- //思路:
- //首先身高为1~n的排序
- //模拟一遍发现,反向扫描,发现ax的身高=前面未没有被选到的身高值(因为被选到的就是在x后面的,而ax表示x前比x身高矮的牛的个数)中排名第x的数字的后一位
- //x[i]表示身高为i的值的情况0表示被占用,1表示未被占用,可用数组S(假设)作x[i]的前缀和,则S[i]可表示前i位中,未被占用的身高值的个数,采用二分答案,找到未被占用的身高值的个数>=a[i]+1 的最小值
- //动态维护,选了这个数字就删掉这个数字(减去1)
- //维护前缀和(区间和),单点修改,可用树状数组
- int main()
- {
- memset(ans,0x3f,sizeof ans);
- scanf("%d",&n);
- for(int i=2;i<=n;i++)
- {
- scanf("%d",a+i);
- }
- for(int i=1;i<=n;i++)t[i]=lowbit(i);//初始化
- for(int i=n;i;i--)//反向扫描
- {
- int l=1,r=n;
- while(l<=r)
- {
- int mid=(l+r)/2;
- if(sum(mid)>=a[i]+1)//前缀和求前i位中,未被占用的身高值的个数>=a[i]+1的最小值
- {
- r=mid-1;
- ans[i]=min(ans[i],mid);
- }
- else l=mid+1;
- }
- add(ans[i],-1);//将这个身高值删除
- }
- for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
- return 0;
- }

树状数组2(模板)(差分数组)(求单点值、区间修改)
(acwing)一个简单的整数问题
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=111000;
- const ll M=111111;
- typedef pair<int,int> PII;
- int n,m;
- ll t[N],a[N];
- ll lowbit(int x)
- {
- return x&-x;
- }
- void add(int x,int c)
- {
- for(int i=x;i<=n;i+=lowbit(i))
- {
- t[i]+=c;
- }
- }
- ll sum(int x)
- {
- ll res=0;
- for(int i=x;i;i-=lowbit(i))
- {
- res+=t[i];
- }
- return res;
- }
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- add(i,a[i]-a[i-1]);//构建差分数组
- }
- while(m--)
- {
- char flag;
- cin>>flag;
- if(flag=='C')
- {
- int l,r,d;
- cin>>l>>r>>d;
- add(l,d);add(r+1,-d);//区间修改
- }
- else
- {
- int x;
- cin>>x;
- cout<<sum(x)<<endl;//查询单点,因为差分数组,所以单点值=其前缀和
- }
- }
- return 0;
- }

(acwing)一个简单的整数问题2(树状数组实现区间修改,区间求和)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=101000;
- const ll M=55555;
- typedef pair<int,int> PII;
- int n,m;
- ll a[N],t1[N],t2[N];
- int lowbit(int x)
- {
- return x&-x;
- }
- void add(ll t[],int x,ll c)
- {
- for(int i=x;i<=n;i+=lowbit(i))
- {
- t[i]+=c;
- }
- }
- ll sum(ll t[],int x)
- {
- ll ans=0;
- for(int i=x;i;i-=lowbit(i))
- {
- ans+=t[i];
- }
- return ans;
- }
- ll cal(ll x)
- {
- return sum(t1,x)*(x+1)-sum(t2,x);
- }
- //区间修改,则使用差分数组
- //求差分数组的前缀和
- //a1:b1
- //a2:b1 b2
- //a3:b1 b2 b3
- //a4:b1 b2 b3 b4
- //a5:b1 b2 b3 b4 b5
- //...
- //差分数组中单点值ax=b1+...+bx
- //a的前缀和=a1+...+ax = x*b1+(x-1)*b2+...+bx
- //为了更简洁 ,补齐图形
- // b1 b2 b3 b4 b5(另加的一行)
- //a1:b1 b2 b3 b4 b5
- //a2:b1 b2 b3 b4 b5
- //a3:b1 b2 b3 b4 b5
- //a4:b1 b2 b3 b4 b5
- //a5:b1 b2 b3 b4 b5
- //则ax的前缀和= (b1+b2+..bx)*(x+1) - (b1+2*b2+...+x*bx);(就是整个表的b加起来减掉补齐的那一部分)
- //根据上式,用t1维护bi前缀和,用t2维护i*bi前缀和
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)scanf("%lld",a+i);
- for(int i=1;i<=n;i++)
- {
- add(t1,i,a[i]-a[i-1]);//构建差分数组
- add(t2,i,(ll)i*(a[i]-a[i-1]));
- }
- while(m--)
- {
- char op[2];
- int l,r,d;
- scanf("%s",op);//不会接受到回车和空格
- if(op[0]=='C')
- {
- scanf("%d%d%d",&l,&r,&d);
- add(t1,l,d);add(t1,r+1,-d);
- add(t2,l,l*d);add(t2,r+1,(r+1)*(-d));
- }
- else
- {
- scanf("%d%d",&l,&r);
- printf("%lld\n",cal(r)-cal(l-1));
- }
- }
- return 0;
- }

线段树可实现树状数组所有功能(单点修改,区间修改,求单点值,求区间和)但线段树代码较长,空间较大,速度会比树状数组满一个常数
图论—————————————————————————————————————————
图论杂题:
(洛谷)信息传递(最小环)
拓扑排序 要求 1:有向无环图 2:每个点不重复
算法步骤:1.统计所有节点的入度,将入度为0的节点入队列 2.将这个节点指向的节点的入度减1若该点入度减为0,再入度,直到所有的节点都分离出来 3.统计已分离的节点个数,若==节点总数,则该排序正确,否则说明有环,无解
图例:
(洛谷)最大食物链计数(正常一点的拓扑)
- #include<iostream>
- #include<algorithm>
- #include <vector>
- #include <queue>
- using namespace std;
- #define mod 80112002
- int n,m,in[510000],out[510000],mar;
- long long num[510000],ans;
- vector<int>v[520000];
- void topo()
- {
- queue<int>q;
- for(int i=1;i<=n;i++)
- {
- if(in[i]==0)
- {
- q.push(i);
- num[i]=1;
- }
- }
- while(q.size())
- {
- int x=q.front();q.pop();
- for(int i=0;i<v[x].size();i++)
- {
- int y=v[x][i];
- num[y]=(num[y]+num[x])%mod;
- if(--in[y]==0)
- {
- if(out[y]==0)//最佳生产者不止一个
- ans=(num[y]+ans)%mod;
- q.push(y);
- }
- }
- }
- }
- int main()//题意:找到图中所有 左端点入度为0 且 右端点出度为0 的路径的数量
- {
- scanf("%d %d",&n,&m);
- for(int i=1;i<=m;i++)
- {
- int a,b;
- scanf("%d %d",&a,&b);
- v[a].push_back(b);
- in[b]++;
- out[a]++;//记录出度,出度为0即为最佳生产者
- }
- topo();
- cout<<ans%mod;
- return 0;
- }

(牛客)菜肴制作(反向建图,拓扑排序,反向输出)
如果用一个小根堆来维护拓扑的话显然是会不行的,因为这样求出来的是字典序最小的拓扑序,并不一定是1尽可能在前,因为字典序是贪心的,如果前面的一位能小就尽可能的小,并不保证1出现尽量靠前,,但是如果建一个反图,求一个反向字典序最大的拓扑序呢,那么就会有大的数尽量靠前的情况出现,于是交小的数尽量靠后,于是反过来就是小的数尽量靠前了,于是反着建图+一个大根堆维护就好了
- 因为1号菜肴在满足所有限制下要尽量优先制作,2,3号同理
- 需要反向建图,做字典序最大的拓扑排序,反向输出答案
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int in[100007],tt,n,m,x,y;
- vector<int>v[100007],ans;//用邻接矩阵存邻接点(topo就用这个)
- bool topo()
- {
- ans.clear();
- priority_queue<int>q;//大根堆,即堆顶为字典序最大的数
- for(int i=1;i<=n;i++)
- {
- if(in[i]==0)//将没有前驱即入度为0的点入队
- {
- q.push(i);
- }
- }
- while(q.size())
- {
- int t=q.top();q.pop();
- ans.push_back(t);
- for(int i=0;i<v[t].size();i++)//删除该点的所有邻接点和它们之间的弧
- {
- if(--in[v[t][i]]==0)//如果删了该弧,该邻接点入度为0
- q.push(v[t][i]);//将该邻接点入队,这里之前写错成q.push(i)
- }
- }
- if(ans.size()==n)return true;
- else return false;
- }
- int main()
- {
- cin>>tt;
- for(int i=0;i<tt;i++)
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- {
- v[i].clear();//初始化存放以该点为尾的弧的顶点//这里之前忘记写
- in[i]=0;//初始化该点入度为0
- }
- for(int i=1;i<=m;i++)
- {
- cin>>x>>y;
- swap(x,y);//反向建图(普通拓扑可忽略)
- v[x].push_back(y);//记录以该点为尾的弧的顶点
- in[y]++;//入度
- }
- if(topo())
- {
- for(int i=ans.size()-1;i>=0;i--)
- {
- cout<<ans[i]<<" ";
- }
- cout<<endl;
- }
- else cout<<"Impossible!"<<endl;
- }
- return 0;
- }
- 1,3 1,4
- 2,3,4

(洛谷)杂物(拓扑排序+dp)
(洛谷)神经网络(拓扑排序+dp)
spfa最短路(可求最短路,但容易tle,一般只用于存在负权边的最短路或最长路和判断是否存在正、负环)
(洛谷p3385)第一种方法o(n^2),相较于第二种方法,慢,但判断负环同时,能顺便求出s点的单源最短路径
- #include <bits/stdc++.h>
- using namespace std;
- #define inf 0x3f3f3f3f
- #define ll long long
- const ll mod =1e9+7;
- #define ull unsigned long long
- int n,t,m,head[2222],cnt,e[2222],dis[2222];
- bool vis[2222];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[6666];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool spfa()
- {
- memset(dis,0x3f,sizeof dis);
- dis[1]=0;
- queue<int>q;
- q.push(1);vis[1]=1;
- while(q.size())
- {
- int x=q.front();
- q.pop();vis[x]=0;//出队
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- int w=edge[i].w;
- if(dis[y]>dis[x]+w)
- {
- dis[y]=dis[x]+w;
- e[y]=e[x]+1;
- if(e[y]>n)return 1;
- if(!vis[y])//还没入队
- {
- q.push(y);
- vis[y]=1;//入队
- }
- }
- }
- }
- return 0;
- }
- int main()
- {
- scanf("%d",&t);
- while(t--)
- {
- memset(head,0,sizeof head);
- memset(e,0,sizeof e);
- memset(vis,0,sizeof vis);
- cnt=0;
- scanf("%d %d",&n,&m);
- for(int i=1;i<=m;i++)
- {
- int x,y,w;
- scanf("%d %d %d",&x,&y,&w);
- if(w>=0)
- {
- addedge(x,y,w);
- addedge(y,x,w);
- }
- else addedge(x,y,w);
- }
- if(spfa())printf("YES\n");
- else printf("NO\n");
- }
- return 0;
- }

(acwing)虫洞 (第二种方法o(n) ),只能判断是否存在负环,不能维护单源最短路
- #include <map>
- #include <set>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=600;
- const ll M=11111;
- int t,n,m1,m2,cnt,head[N];
- int e[N],dis[N];//e[]统计每个点的最短路径所包含边数,若>=n,即存在负环
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool spfa()
- {
- memset(vis,0,sizeof vis);
- memset(dis,0,sizeof dis);//初始距离设为0,其实没关系,因为只有负环会到达负无穷
- memset(e,0,sizeof e);
- queue<int>q;
- for(int i=1;i<=n;i++)//将所有点入队
- {
- q.push(i);
- vis[i]=1;
- }
- while(q.size())
- {
- int x=q.front();q.pop();vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]>dis[x]+edge[i].w)
- {
- dis[y]=dis[x]+edge[i].w;
- e[y]=e[x]+1;//更新该点的最短路所包含的边数
- if(!vis[y])
- {
- q.push(y);
- vis[y]=1;
- }
- if(e[y]>=n)return true;
-
- }
- }
- }
- return false;
- }
- //现在农夫约翰希望能够从农场中的某片田地出发,经过一些路径和虫洞回到过去,并在他的出发时刻之前赶到他的出发地。
- //存在负环即可,因为它可以从任意一片田地出发,可直接从负环出发
- int main()
- {
- cin>>t;
- while(t--)
- {
- cin>>n>>m1>>m2;
- memset(head,0,sizeof head);
- cnt=0;
- while(m1--)
- {
- int x,y,w;
- cin>>x>>y>>w;
- addedge(x,y,w);//按题意,双向边
- addedge(y,x,w);
- }
- while(m2--)
- {
- int x,y,w;
- cin>>x>>y>>w;//按题意,负边
- w*=-1;
- addedge(x,y,w);
- }
- if(spfa())puts("YES");
- else puts("NO");
- }
- return 0;
- }

(acwing)观光奶牛(01分数规划+判断正环)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=1100;
- const ll M=11111;
- int t,n,m,cnt,head[N];
- int e[N],W[N];//W为点权,e为统计该点的边的数量
- double dis[N];
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool check(double mid)
- {
- memset(vis,0,sizeof vis);
- memset(dis,0,sizeof dis);
- memset(e,0,sizeof e);
- queue<int>q;
- for(int i=1;i<=n;i++)
- {
- q.push(i);
- vis[i]=1;
- }
- while(q.size())
- {
- int x=q.front();q.pop();vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]<dis[x]+W[x]-mid*edge[i].w)//将点权带入边权计算,spfa常常可以这么用
- {
- dis[y]=dis[x]+W[x]-mid*edge[i].w;
- e[y]=e[x]+1;//更新边数
- if(e[y]>=n)return true;
- if(!vis[y])
- {
- q.push(y);
- vis[y]=1;
- }
-
- }
- }
- }
- return false;
- }
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)cin>>W[i];
- for(int i=1;i<=m;i++)
- {
- int x,y,w;
- cin>>x>>y>>w;
- addedge(x,y,w);
- }
- //因为求(和f/和i)最大值,为01分数规划 ,采用二分答案
- //则(和f/和t)>mid->和f-和t*mid>0->和(f-t*mid)>0,对于点权f[i],我们将它附在出边上,如果重新定义每个边的权值为f-t*mid,那么问题就转化为判断图中是否存在正环,spfa求正环可以对一个环求最长路,若某点最长路所含边数>=n即存在正环
- double l=0,r=1010;//上限为1000*1000/1000=1000
- while(r-l>1e-4)//一般保留n位小数,就是1e-(n+2)**
- {
- double mid=(l+r)/2;
- if(check(mid))l=mid;
- else r=mid;
- }
- printf("%.2lf",l);
- return 0;
- }

(acwing)单词环(01分数规划+思维+spfa判断正环+栈优化)
栈优化:若用队列,遇到正/负环则更新一次又将元素放到队尾,直到遍历完整个队列才去算他),用栈遇到正/负环,则在队尾反复更新,当e>n则返回
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=700;
- const ll M=111111;
- int t,n,m,cnt,head[N];
- int e[N],s[N],top;
- double dis[N];
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool check(double mid)
- {
- memset(vis,0,sizeof vis);
- memset(dis,0,sizeof dis);
- memset(e,0,sizeof e);
- top=0;
- for(int i=0;i<676;i++)//26*26,一共676个点
- {
- s[++top]=i;//stl的栈会被卡掉
- vis[i]=1;
- }
- int count=0;
- while(top>0)
- {
- int x=s[top--];vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]<dis[x]+edge[i].w-mid)
- {
- dis[y]=dis[x]+edge[i].w-mid;
- e[y]=e[x]+1;//更新边数
- // if(++count>=3*N)return true;//玄学,如果循环超过2*点的数量,一般返回正数
- if(e[y]>=N)return true;//题目中的n表示的不是点数
- if(!vis[y])
- {
- s[++top]=y;
- vis[y]=1;
- }
- }
- }
- }
- return false;
- }
- int main()
- {
- while(cin>>n)
- {
- if(n==0)return 0;
- memset(head,0,sizeof head);
- cnt=0;
- string str;
- for(int i=1;i<=n;i++)
- {
- cin>>str;
- if(str.size()<2)continue;
- int a=(str[0]-'a')*26+str[1]-'a';
- int b=(str[str.size()-2]-'a')*26+str[str.size()-1]-'a';
- addedge(a,b,str.size());//建图方法:将一个字符串看成字符串前两个数向字符串后两个数连一条长度为len的边 ,则图最多有26*26个点,n条边
- }
- //由题,求(和长度/和边数)最大值,为01分数规划,采用二分答案
- //(和长度/和边数)>mid,和长度-mid*和边数>0,和(长度-mid)>0,所以以长度-mid作为边权,求图是否存在正环,判断正环,用最长路
- if(!check(0))puts("No solution");
- else
- {
- double l=0,r=1000;//上限为1000*1000/1000
- while(r-l>1e-4)
- {
- double mid=(l+r)/2;
- if(check(mid))l=mid;
- else r=mid;
- }
- printf("%lf\n",r);
- }
- }
- return 0;
- }

迪杰斯特拉
时间复杂度:O((n+m)logn)
(洛谷)单源最短路径(弱化版)(迪杰斯特拉算法+堆优化+链式前向星)
单源最短路是指单个起点到所有点的最短距离,不是start到end的最短距离,参考(牛客)旅行
有关链式前向星
根据上图易知 链式前向星存边 的特性: 存边顺序和搜索出来的是反着的,比如存第i个结点存1 2 3序号的边,搜第i个结点的边时,搜出来的顺序是3 2 1
有关迪杰斯特拉 (该图和该模板题为有向图,若无向图要建两次边)
且迪杰斯特拉不允许有负权边,有负权边用spfa
链式前向星的插入不同于邻接表,插入从头插,H再重新指向新元素
- 链式前向星:本质上为邻接表,但是由于邻接表多用vector且vector过度封装,所以链式前向星会快,前向星用来存一个顶点的所有出度边的信息(edge)
- 迪杰斯特拉算法1.建图(前向星) 2.每次选择距离家最短的一个点并剔除该点(vis[u]=false),然后用这个点的距离更新其他相邻点到家的距离,
- 如果比当前的点小,则更新节点的值(优先队列)
- #include <iostream>
- #include <queue>
- using namespace std;
- #define ll long long
- #define maxn 0x7fffffff//最大的数
- int n,m,s,x,y,z,cnt,head[600000];//head[u]存放顶点u的出度边的最后一条的”边序号(cnt)”
- long long dis[600000];//存放到起点的暂时最短距离
- bool vis[600000];//该点是否访问过
- inline int read()//快读******
- {
- int a=0,b=1;
- char ch=getchar();
- while(ch<'0'||ch>'9')
- {
- if(ch=='-')b=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9')
- {
- a=(a<<3)+(a<<1)+(ch^48);//之前写成了+=,,而且三个位运算都要加括号,且>>是除,<<是乘
- ch=getchar();
- }
- return a*b;
- }
- struct Edge//前向星存边
- {
- int u,v,w,nexty;
- }edge[600000];
- struct node//该结构体仅仅用来维护优先队列
- //now记录顶点(弧尾),不然从优先队列里取出来后不知道是哪个顶点,存储weight的作用只在于优先队列的排序
- {
- int now,weight;
- inline bool operator<(const node &x)const
- {
- return weight>x.weight;
- }
- };
- inline void addedge(int x,int y,int z)//加边
- {
- edge[++cnt].u=x;
- edge[cnt].v=y;
- edge[cnt].w=z;
- edge[cnt].nexty=head[x];
- head[x]=cnt;
- return;
- }
- void dijkstra()
- {
- for(int i=1;i<=n;i++)
- {
- dis[i]=maxn;
- }
- dis[s]=0;//vis[s]=true;不能写这个
- priority_queue<node>q;
- q.push({s,0});
- while(!q.empty())
- {
- int u=q.top().now;q.pop();
- if(vis[u])continue;
- vis[u]=1;
- for(int i=head[u];i;i=edge[i].nexty)//更新所有以该点为尾的边的权值
- {
- int v=edge[i].v;
- if(dis[v]>dis[u]+edge[i].w)//注意这里是edge[i].w,不是dis[v]
- {
- dis[v]=dis[u]+edge[i].w;
- q.push({v,dis[v]});
- }
- }
- }
- }
- int main()
- {
- n=read(),m=read(),s=read();
- for(int i=1;i<=m;i++)//建图
- {
- x=read(),y=read(),z=read();
- addedge(x,y,z);
- }
- dijkstra();
- for(int i=1;i<=n;i++)
- printf("%lld ",dis[i]);
- return 0;
- }

若每条边权值相等,最短路径=从起点开始bfs广搜到某点的层数*边权值
eg.(洛谷)寻找道路 (前向星+反向建图+思维*)
(牛客)旅行(思维+维护最大和次大值+dj)
(洛谷)邮递员送信(有向图内,多个点到一个点的距离=反向建图+该点的单源最短路之和)
(天梯赛) L2-001 紧急救援 (对dj的理解:是从s->t一个一个点更新的,不会跳过某个点)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=1e6+10;
- const ll M=2e5 + 10;
- typedef pair<int,int> PII;
- ll head[N],cnt,num[N],pre[N],dp1[N],dp2[N];
- ll n,m,s,d,dis[N];
- bool vis[N];
- struct EDGE
- {
- ll x,y,w,neaxty;
- }edge[N];
- struct NODE
- {
- ll num,w;
- bool operator<(const NODE&x)const
- {
- return w>x.w;
- }
- };
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x = x;
- edge[cnt].y = y;
- edge[cnt].w = w;
- edge[cnt].neaxty = head[x];
- head[x] = cnt;
- }
- void dj()
- {
- memset(dis,0x3f,sizeof dis);
- priority_queue<NODE>q;
- q.push({s,0});
- dis[s]=0;
- dp1[s]=1; //记录每个点到起点的最短路径的条数
- dp2[s]=num[s]; //起点到每个点的救援队的数量
- while(q.size())
- {
- int x= q.top().num;
- q.pop();
- if(vis[x])
- continue;
- vis[x]=1;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y = edge[i].y;
- int tem = dp2[x] + num[y];
- if(dis[y]>dis[x]+edge[i].w)
- {
- dis[y] = dis[x] + edge[i].w;
- pre[y] = x;//记录前驱点,到时候便可以记录整条路径(之前想过会不会漏掉某个点,但是dj是一个一步脚印,不会跨过某个点)
- dp1[y] = dp1[x];
- dp2[y] = dp2[x] + num[y];
- q.push({y,dis[y]});
- }
- else if(dis[y] == dis[x]+edge[i].w)
- {
- dp1[y] = dp1[x]+dp1[y]; //多加一次dp1[x]
- if(tem>dp2[y])
- {
- dp2[y] = tem;
- pre[y] = x;
- }
- }
- }
- }
- }
- int main()
- {
- cin>>n>>m>>s>>d;
- for(int i=0;i<n;i++)cin>>num[i];//救援人数
- for(int i=1;i<=m;i++)
- {
- int x,y,w;
- cin>>x>>y>>w;
- addedge(x,y,w);//双向边
- addedge(y,x,w);
- }
- dj();
-
- ll ans1=dp1[d],ans2=dp2[d],las=d;
- int tmp[600],tmp_cnt=0;
- while(las!=s) //之前是to_string 然后reserve,个位数还行,但若有数>9 则个位和十位会反 ,eg 12 -> 21
- {
- tmp[++tmp_cnt] = las;
-
- las = pre[las];
-
- }
- //ans2 += num[s];
- cout<<ans1<<" "<<ans2<<endl;
-
- for(int i=tmp_cnt;i>=1;i--)
- {
- if(i!=tmp_cnt)
- cout<<" ";
- cout<<tmp[i];
- }
- return 0;
- }

分层图
(分层图)***(牛客)小雨坐地铁
图解:
---------------------------------------------------------------------------------------------------------------------------------
floyd算法(求每一对顶点间的最短路径)
- for(k=1;k<=n;k++)
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- if(e[i][j]>e[i][k]+e[k][j])
- e[i][j]=e[i][k]+e[k][j];
(洛谷)灾后重建
- floyd思想:最开始只允许经过1号顶点进行中转,接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转,
- 求任意两点之间的最短路程。用一句话概括就是:从i号顶点到j号顶点只经过前k号点的最短路程
-
- 题意:所有的边全部给出,按照时间顺序更新每一个可用的点(即修建好村庄),
- 对于每个时间点进行两点之间询问,求对于目前建设的所有村庄来说任意两点之间的最短路
- #include <iostream>
- #include <cstring>
- #include <stdlib.h>
- using namespace std;
- #define maxn 1e9//这里用0x7fffffff会爆负数
- int G[201][201],n,m,t[201],Q,now;
- inline void update(int x)
- {
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- if(G[i][j]>G[i][x]+G[x][j])
- G[i][j]=G[i][x]+G[x][j];
- }
- }
- return;
- }
- int main()
- {
- scanf("%d %d",&n,&m);
- for(int i=0;i<n;i++)//初始化
- {
- for(int j=0;j<n;j++)
- G[i][j]=maxn;
- }
- for(int i=0;i<n;i++)scanf("%d",&t[i]);
- for(int i=0;i<m;i++)
- {
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- G[x][y]=z;G[y][x]=z;
- }
- scanf("%d",&Q);
- for(int i=1;i<=Q;i++)
- {
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- while(z>=t[now]&&now<n)//如果z>=该村庄修复时间 ,则该村庄可作中转站
- {
- update(now++);//更新点
- }
- if(t[x]>z||t[y]>z||G[x][y]==maxn)printf("-1\n");
- else printf("%d\n",G[x][y]);
- }
- return 0;
- }

(洛谷)电车
最小生成树算法: 最小生成树是什么呢,实际上就是给您一个图,要求把图变成一个由n-1(n为点数)条边组成的图,使得总边权最小。
最小生成树算法( Kruskal )适用于稀疏图
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int n,m,fa[6000];
- long long sum;
- struct NODE
- {
- int x,y,w;//存储边消息,,不是前向星
- }edge[300000];
- bool cmp(NODE x,NODE y)
- {
- return x.w<y.w;
- }
- int f_ind(int x)
- { //注意别漏了第一个fa[x]
- return fa[x]=fa[x]==x?x:f_ind(fa[x]);//找父节点路径压缩
- }
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=m;i++)
- {
- int x,y,z;
- scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].w);
- }
- for(int i=1;i<=n;i++)fa[i]=i;
- sort(edge+1,edge+1+m,cmp);//把边权值从小到大
- for(int i=1;i<=m;i++)
- {
- int h=edge[i].x,t=edge[i].y;
- if(f_ind(h)!=f_ind(t))//判断是否在一个连通图里
- {
- sum+=edge[i].w;
- fa[f_ind(h)]=fa[f_ind(t)];//合并连通图
- }
- }
- int x=f_ind(1);
- for(int i=2;i<=n;i++)//判断是否能成连通图
- {
- if(f_ind(i)!=x)
- {
- cout<<"orz";return 0;
- }
- }
- cout<<sum;
- return 0;
- }

(牛客)Forsaken喜欢独一无二的树(似懂非懂)
(洛谷)修复公路
最小生成树( prime )适用于稠密图 (洛谷)公路修建
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <queue>
- #include <cstring>
- using namespace std;
- #define ll long long
- #define inf 0x7fffffff
- int n,m,x[6000],y[6000];
- bool vis[6000];
- double dis[6000],ans;
- double dist(int i,int j)
- {
- return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j]));
- }
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>x[i]>>y[i];//坐标
- dis[i]=inf;
- }
- dis[1]=0;//以1作为树的根
- int cnt=0,now;
- double minn;
- while(++cnt<=n)//循环n次
- {
- minn=inf;
- for(int i=1;i<=n;i++)
- {
- if(!vis[i]&&minn>dis[i])//找出距离该树最近的点,且这个点没用来更新过(类似迪杰斯特拉)
- {
- now=i,minn=dis[i];
- }
- }
- ans+=minn;//加边
- vis[now]=true;
- for(int i=1;i<=n;i++)//将该点加入到该树,更新该树到其他点的距离
- {
- double t = dist(i,now);//更新树到其他结点的距离,这题不能存边,用前向星和邻接矩阵都会MLE,只能用的时候算
- if(t<dis[i])
- dis[i]=t;
- }
- }
- printf("%.2f",ans);
- return 0;
- }

差分约束
补充:必须有一个绝对条件才能算出结果,eg: xi>=c ;差分约束难点主要在于想题目中隐含的不等式,不等式不能漏想
(acwing)糖果(直接给出不等式)(差分约数+spfa求最长路并判断正环+栈优化)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=111111;
- const ll M=311111;
- int n,m,cnt,head[N];
- int e[N];
- int dis[N];
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- //易得求最小值,所以求 【源点的单源最长路】
- //条件1:A==B -> A>=B,B>=A
- //条件2:A<B -> B>=A+1
- //条件3:A>=B
- //条件4:A>B -> A>=B+1
- //条件5:A<=B -> B>=A
- //以上全是相对的条件,必须找到绝对条件才能解题,题目中保证每个小朋友都有糖,即x>=1,即x>=x0+1
-
- //另外:A>=B+c 在求最长路中表示,B向A连一条长度为c的边
- bool spfa()//用第一种方法,判断负环同时维护 源点的单源最长路
- {
- memset(dis,-0x3f,sizeof dis);//最长路初始化为负无穷
- dis[0]=0;//源点到自己距离为0
- stack<int>s; //优化:用栈(若用队列,遇到正环则更新一次又将元素放到队尾,直到遍历完整个队列才去算他),用栈遇到正环,则在队尾反复更新,当nev>=n+1则返回
- s.push(0);vis[0]=1;
- int count=0;
- while(s.size())
- {
- int x=s.top();s.pop();vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]<dis[x]+edge[i].w)
- {
- dis[y]=dis[x]+edge[i].w;
- e[y]=e[x]+1;
- if(e[y]>n)return true;
- if(!vis[y])
- {
- s.push(y);
- vis[y]=1;
- }
- }
- }
- }
- return false;
- }
- int main()
- {
- cin>>n>>m;
- while(m--)
- {
- int x,a,b;
- cin>>x>>a>>b;
- if(x==1)addedge(a,b,0),addedge(b,a,0);
- else if(x==2)addedge(a,b,1);
- else if(x==3)addedge(b,a,0);
- else if(x==4)addedge(b,a,1);
- else if(x==5)addedge(a,b,0);
- }
- for(int i=1;i<=n;i++)addedge(0,i,1);//绝对条件
- //根据题意,可能无解,即最长路中存在正环,故用spfa
- if(spfa())
- {
- cout<<-1;
- return 0;
- }
- ll sum=0;
- for(int i=1;i<=n;i++)sum+=dis[i];
- cout<<sum;
- return 0;
- }

(acwing)区间(思维+差分约束+spfa求最长路)
- #include <map>
- #include <set>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=55555;
- const ll M=3*N;
- int head[N],cnt,n,dis[N];
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
-
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- //题意:给出n个a,b,c,对于每个i,找出c个x,使a<=x<=b,现在要使得找出的x的个数尽量少(就是让他们尽量重叠)
- //思路:因为ai <= x <= bi 的整数x不少于ci个,易知用前缀和(记得把数往后平移1,把0留出来),得出等式1
- //s[b]-s[a-1]>=c -> s[b]>=s[a-1]+c
- //再推等式2和3
- //s[i]>=s[i-1]
- //s[i]-s[i-1]<=1 -> s[i-1]>=s[i]-1
- //做法为差分约束求最小值,要求最长路,且满足从源点(0)出发,能走到所有的边 (因为s[i-1] 和 s[i]之间有边 0->1->2->3...)
- void spfa()
- {
- memset(dis,-0x3f,sizeof dis);//最长路,初始化为负无穷
- dis[0]=0;//源点到自己距离为0
- queue<int>q;//因为没有环,直接用队列更快
- q.push(0);vis[0]=1;
- while(q.size())
- {
- int x=q.front();q.pop();vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]<dis[x]+edge[i].w)
- {
- dis[y]=dis[x]+edge[i].w;
- if(!vis[y])
- {
- q.push(y);
- vis[y]=1;
- }
- }
- }
- }
- }
-
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=50001;i++)
- {
- addedge(i-1,i,0);
- addedge(i,i-1,-1);
- }
- for(int i=1;i<=n;i++)
- {
- int a,b,c;
- scanf("%d %d %d",&a,&b,&c);
- a++,b++;//平移,因为前缀和,把0留出来
- addedge(a-1,b,c);
- }
- spfa();//为什么不用dj?因为dj算法不允许有负权边
- cout<<dis[50001];//从源点到50001的最长路代表满足0->1->2->3....50001路径(条件)
- return 0;
- }

(acwing)排队布局 (判断负环+求最短路径+差分约束)
- #include <map>
- #include <set>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll mod =1e9+7;
- const ll N=1111;
- const ll M=33333;
- int head[N],cnt,n,m1,m2,dis[N],e[N];
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool spfa(int size)
- {
- memset(dis,0x3f,sizeof dis);
- memset(vis,0,sizeof vis);
- memset(e,0,sizeof e);
- dis[1]=0;
- stack<int>q;
- for(int i=1;i<=size;i++)
- {
- q.push(i);
- vis[i]=1;
- }
- while(q.size())
- {
- int x=q.top();q.pop();vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]>dis[x]+edge[i].w)
- {
- dis[y]=dis[x]+edge[i].w;
- e[y]=e[x]+1;
- if(e[y]>n)return true;
- if(!vis[y])
- {
- vis[y]=1;
- q.push(y);
- }
- }
- }
- }
- return false;
- }
- //思路:因为求最大值,所以求最短路,第一问要spfa判断负环,,然后再求一遍最短路,若dis[n]<INF,则输出dis[n],否则输出-2
- //x[i]表示i点到1号奶牛的距离
- //x[i]<=x[i+1]
- //条件1:x[a]-x[b]<=L,x[a]<=x[b]+L (a在b右侧)
- //条件2:x[a]-x[b]>=L,x[b]<=x[a]-L (a在b右侧)
- //因为以上全是相对条件,没有绝对条件,要补上一个x[1]=0,即x[1]>=x[1](本身自己就是源点)+0 x[1]<=x[1]+0,没有边,不用建边
- //且因为x[i]<=x[i+1],求最短路时,从1出发可以遍历所有点,从而遍历所有边,满足所有不等式,所以spfa时放1
- int main()
- {
- scanf("%d %d %d",&n,&m1,&m2);
- for(int i=1;i<n;i++)addedge(i+1,i,0);
- while(m1--)
- {
- int a,b,c;
- scanf("%d%d%d",&a,&b,&c);
- if(a<b)swap(a,b);//a在b右侧
- addedge(b,a,c);
- }
- while(m2--)
- {
- int a,b,c;
- scanf("%d%d%d",&a,&b,&c);
- if(a<b)swap(a,b);
- addedge(a,b,-c);
- }
- if(spfa(n))puts("-1");//判断负环
- else
- {
- spfa(1);//求最短路(带负边权)
- if(dis[n]!=INF)
- printf("%d",dis[n]);
- else
- puts("-2");
- }
- return 0;
- }

(acwing)雇佣收银员 (思维+前缀和+差分约束)
- #include <map>
- #include <set>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll mod =1e9+7;
- const ll N=30;
- const ll M=33333;
- int head[N],cnt,n,m1,m2,dis[N],e[N],r[N],num[N],s[N];//num为从t
- bool vis[N];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- //思路: 求最小值,最长路
- //设xi为第i时刻选的员工人数 则0<=xi<=num[i]
- //x[i-7]+x[i-6]+....x[i]>=r[i]
- //运用前缀和,空一个位置0出来
- //则上述可替代为 0<=s[i]-s[i-1]<=num[i] -> s[i]>=s[i-1] s[i-1]>=s[i]-num[i]
- //s[i]-s[i-8]>=r[i] -> s[i]>=s[i-8] + r[i] (i-8>=0)
- //s[i]+s[24]-s[i+16]>=r[i] -> s[i]>=s[i+16]-s[24]+r[i] (1<=i<=7)
- //s[24]即为答案,对s[24]进行二分答案
- //因为s[24]为定值,所以s[24]>=s[0]+s[24] s[24]<=s[0]+s[24]
- void build(int s24)
- {
- for(int i=1;i<=24;i++)//从源点(0)可以遍历到所有点从而遍历所有边
- {
- addedge(i-1,i,0);
- addedge(i,i-1,-num[i]);
- }
- for(int i=8;i<=24;i++)
- {
- addedge(i-8,i,r[i]);
- }
- for(int i=1;i<=7;i++)
- {
- addedge(i+16,i,-s24+r[i]);
- }
- addedge(0,24,s24);
- addedge(24,0,-s24);
- }
- bool spfa(int s24)
- {
- memset(dis,-0x3f,sizeof dis);
- memset(head,0,sizeof head);
- memset(e,0,sizeof e);
- memset(vis,0,sizeof vis);
- cnt=0;
- build(s24);
- stack<int>q;
- dis[0]=0;//从0可以遍历所有边(满足所有条件),所以放0,放1也可以(但建立规范吧,因为有些题不行)
- vis[0]=1;q.push(0);
- while(q.size())
- {
- int x=q.top();q.pop();vis[x]=0;
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(dis[y]<dis[x]+edge[i].w)
- {
- dis[y]=dis[x]+edge[i].w;
- e[y]=e[x]+1;
- if(e[y]>24)return false;//正环,无解
- if(!vis[y])
- {
- vis[y]=1;
- q.push(y);
- }
- }
- }
- }
- return true;
- }
- int main()
- {
- int T;cin>>T;
- while(T--)
- {
- for(int i=0;i<=23;i++)cin>>r[i+1];//将i往后平移一位,因为前缀和
- cin>>n;
- memset(num,0,sizeof num);
- for(int i=1;i<=n;i++)
- {
- int x;
- cin>>x;
- num[x+1]++;//统计该时刻员工总人数
- }
- int l=0,r=n,ans;//上限为最多能招的人数,为n
- bool flag=false;
- while(l<=r)
- {
- int mid=(l+r)/2;
- if(spfa(mid))r=mid-1,ans=mid,flag=true;
- else l=mid+1;
- }
- if(flag)cout<<ans<<endl;
- else puts("No Solution");
- }
- return 0;
- }

二分图判定(牛客)关押罪犯
- #include<iostream>
- #include <cstring>
- #include <queue>
- #include <algorithm>
- using namespace std;
- const int N=21000,M=110000;
- int head[N],cnt,n,m,color[N],ans;
- struct NODE
- {
- int x,y,w,neaxty;
- }edge[2*M];//注意无向边
- void addedge(int x,int y,int z)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=z;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool judge(int d)
- {
- memset(color,0,sizeof color);
- queue<int>q;
- for(int i=1;i<=n;i++)
- {
- if(color[i])continue;//已染过色
- q.push(i);
- color[i]=1;
- while(q.size())
- {
- int x=q.front();q.pop();
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(edge[i].w>=d)//满足要求且没染过色
- {
- if(!color[y])
- {
- q.push(y);//这里别漏了
- if(color[x]==1)color[y]=2;
- else color[y]=1;
- }
- else if(color[y]==color[x])return false;//不为二分图
- }
- }
- }
- }
- return true;
- }
- int main()//二分图:要将罪犯分到两个集合内且集合内没有连边(即无仇恨)
- {
- cin>>n>>m;
- int l=1,r=0;
- for(int i=1;i<=m;i++)
- {
- int a,b,c;
- cin>>a>>b>>c;
- r=max(r,c);
- addedge(a,b,c);
- addedge(b,a,c);
- }
- while(l<=r)//二分枚举一个最小值,使得罪犯刚好被分到两个集合且罪犯间无连边,因为为最小值,所以减一就是集合内罪犯的第一条连边(即最大影响力)
- {
- int mid=(l+r)>>1;
- if(judge(mid))
- {
- ans=mid;
- r=mid-1;
- }
- else l=mid+1;
- }
- cout<<ans-1;
- return 0;
- }

(洛谷)封锁阳光大学
二分图的最大匹配(洛谷p3386)
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- int head[600],n,m,e,cnt,biao[600],yuyue[600],ticheng;
- struct NODE
- {
- int x,y,neaxty;
- }edge[55555];
- void addedge(int x,int y)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool zhongjie(int x)
- {
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(biao[y])continue;//该房子已看过,防止递归时陷入死循环(房主愿意换房但换了序号在这之前的房子)
- biao[y]=1;
- if(!yuyue[y]||zhongjie(yuyue[y]))//该房子未被预约或房主愿意换房
- {
- yuyue[y]=x;//标记房子主任
- return true;
- }
- }
- return false;
- }
- int main()//将二分图的一边模拟成人,一边模拟房子,整个过程模拟人买房的数量达到最大值
- {
- scanf("%d %d %d",&n,&m,&e);
- for(int i=1;i<=e;i++)
- {
- int u,v;
- scanf("%d %d",&u,&v);
- addedge(u,v);//人和房子,单向关系
- }
- for(int i=1;i<=n;i++)
- {
- memset(biao,0,sizeof biao);
- if(zhongjie(i))ticheng++;
- }
- printf("%d",ticheng);
- return 0;
- }

(acwing)棋盘覆盖(思维+二分图匹配)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=200;
- const ll M=222222;
- typedef pair<int,int> PII;
- int n,m,d[5]={-1,0,1,0,-1};
- bool biao[N][N],g[N][N];
- PII yuyue[N][N];
- ll ans;
- bool inmap(int x,int y)
- {
- return x>=1&&x<=n&&y>=1&&y<=n;
- }
- bool zhongjie(PII u)
- {
- int x=u.first,y=u.second;
- for(int i=0;i<4;i++)//不用建边了,因为就是相邻点
- {
- int nx=x+d[i];
- int ny=y+d[i+1];
- if(!inmap(nx,ny)||g[nx][ny])continue;
- if(biao[nx][ny])continue;
- biao[nx][ny]=1;
- if(!yuyue[nx][ny].first||zhongjie(yuyue[nx][ny]))
- {
- yuyue[nx][ny]={x,y};
- return true;
- }
- }
- return false;
- }
- //思路;将格子看成一个点,则一个骨牌就是两点间的一条边,问题变成了用一个点匹配另外一个点,求最大匹配数
- //很容易联想到二分图最大匹配,用之前判断是否能看成二分图:用格子坐标x,y之和%2判断其奇偶性,易得同性之间是不相邻的(可看成没有边),相邻的异性可互相匹配
- //即为二分图,可使用匈牙利算法求最大匹配数
- int main()
- {
- int t;
- cin>>n>>t;
- while(t--)
- {
- int x,y;cin>>x>>y;
- g[x][y]=1;//标记坏掉的格子
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- memset(biao,0,sizeof biao);
- //将所有格子二分成奇数格子和偶数格子,用奇数格子匹配偶数格子
- if((i+j)%2&&!g[i][j]&&zhongjie({i,j}))ans++;
- }
- }
- cout<<ans;
- return 0;
- }

二分图的最小点覆盖(用最少的点覆盖最多的边)= 二分图的最大匹配
(acwing)机器任务
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=200;
- const ll M=1100;
- typedef pair<int,int> PII;
- int n,m,k,biao[N],yuyue[N],head[N],cnt,ans;
- struct EDGE
- {
- int x,y,neaxty;
- }edge[M];
- void addedge(int x,int y)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- bool zhongjie(int x)
- {
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(biao[y])continue;
- biao[y]=1;
- if(!yuyue[y]||zhongjie(yuyue[y]))
- {
- yuyue[y]=x;
- return true;
- }
- }
- return false;
- }
- //思路:每个任务可抽象成一条边,A[i]和B[i]为边上两点,要用最少的点覆盖每个边(任务),求的是最小点覆盖
- //又A和B连通,A[i]内部不连通,得该图为二分图
- //二分图的最小点覆盖==二分图的最大匹配
- int main()
- {
- while(cin>>n>>m>>k)
- {
- memset(yuyue,0,sizeof yuyue);
- memset(head,0,sizeof head);
- cnt=ans=0;
- while(k--)
- {
- int t,x,y;
- cin>>t>>x>>y;
- if(!x||!y)continue;
- addedge(x,y);
- }
- getchar();
- for(int i=0;i<n;i++)
- {
- memset(biao,0,sizeof biao);
- if(zhongjie(i))ans++;
- }
- cout<<ans<<endl;
- }
- return 0;
- }

二分图的最大独立集
(acwing)骑士放置
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=110;
- const ll M=55555;
- typedef pair<int,int> PII;
- int d[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{1,2},{2,1},{-1,2},{-2,1}};
- int n,m,ans;
- PII yuyue[N][N];
- bool g[N][N],biao[N][N];
- bool inmap(int x,int y)
- {
- return x>=1&&x<=n&&y>=1&&y<=m;
- }
- bool zhongjie(PII X)
- {
- int x=X.first,y=X.second;
- for(int i=0;i<8;i++)
- {
- int nx=x+d[i][0];
- int ny=y+d[i][1];
- // int nx=x,ny=y;
- if(!inmap(nx,ny)||g[nx][ny]||biao[nx][ny])continue;
- biao[nx][ny]=1;
- if(!yuyue[nx][ny].first||zhongjie(yuyue[nx][ny]))
- {
- yuyue[nx][ny]={x,y};
- return true;
- }
- }
- return false;
- }
- //最大独立集:选出最多的点,使得选出的点没有边,最大独立集(在二分图中)=总点数n-最大匹配数
- //在该题,将所有骑士能到达的点连一条边,则答案即为最大独立集
- //判断是否为二分图:将图按奇偶性染色,发现骑士能到达的地方与他所在的点奇偶性相反,是二分图
- //此题答案还要剪掉禁止放置的格子数
- int main()
- {
- int t;
- cin>>n>>m>>t;
- int tem=t;
- while(tem--)
- {
- int x,y;cin>>x>>y;
- g[x][y]=1;
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- if(g[i][j]||!((i+j)%2))continue;
- memset(biao,0,sizeof biao);
- if(zhongjie({i,j}))ans++;
- }
- }
- cout<<n*m-t-ans;
- return 0;
- }

LCA(求两点的最近公共祖先)
倍增法(nlogn)
(洛谷)【模板】最近公共祖先(LCA)
视频:【manim | 算法】7分钟学会倍增法求解LCA_哔哩哔哩_bilibili
- #include <bits/stdc++.h>
- using namespace std;
- #define inf 0x3f3f3f3f
- #define ll long long
- const ll mod =1e9+7;
- #define ull unsigned long long
- int n,m,head[555555],cnt,s,dep[555555],f[555555][100];//dep维护点的深度,f[i][j]维护从i点向上跳2^j到达的点
- struct EDGE
- {
- int x,y,neaxty;
- }edge[1111111];//树的边大概为2*N
- void addedge(int x,int y)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- void dfs(int x,int fa)//预处理,求f函数
- {
- dep[x]=dep[fa]+1;//维护点的深度
- for(int i=1;(1<<i)<=dep[x];i++)
- {
- f[x][i]=f[f[x][i-1]][i-1];//从x点向上跳2^i到达的点=从x点向上跳2^(i-1)到达的点再跳2^(i-1)到达的点
- }
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(fa==y)continue;
- f[y][0]=x;//向上走1步是父亲
- dfs(y,x);
- }
- }
- int LCA(int x,int y)
- {
- if(dep[x]<dep[y])swap(x,y);//保证x比y深
- for(int i=20;i>=0;i--)//倍增跳跃,维护x和y在同一深度
- {
- if(dep[f[x][i]]>=dep[y])
- x=f[x][i];
- if(x==y)return x;//深度到达同一水平,两点也刚好重合
- }
- for(int i=20;i>=0;i--)//两个点同时倍增跳跃,看能不能到达最近公共祖先
- {
- if(f[x][i]!=f[y][i])
- x=f[x][i],y=f[y][i];
- }
- return f[x][0];
- }
- int main()
- {
- cin>>n>>m>>s;
- for(int i=1;i<n;i++)
- {
- int x,y;
- cin>>x>>y;
- addedge(x,y);
- addedge(y,x);
- }
- dfs(s,0);
- while(m--)
- {
- int x,y;
- cin>>x>>y;
- cout<<LCA(x,y)<<endl;
- }
- return 0;
- }

离线求LCA(tarjan)(o(n+m))
(洛谷)【模板】最近公共祖先(LCA)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=555555;
- const ll M=555555;
- typedef pair<int,int> PII;
- int n,m,head[N],cnt,dis[N],p[N],ans[M],s;
- int vis[N];//注意vis为int类型
- vector<PII>q[M];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M*2];
- void addedge(int x,int y)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- int f_ind(int x)
- {
- return p[x]=x==p[x]?x:f_ind(p[x]);
- }
-
- void tarjan(int x)
- {
- vis[x]=1;//当前路径标记为1
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(!vis[y])
- {
- tarjan(y);
- p[y]=x;//将y合并到x的根节点(这里的根不一定是整个树的根,很大概率是那些还没完成回溯的,即其p[]没有被更新为其父节点
- }
- }
- for(auto i : q[x])
- {
- int y=i.first,id=i.second;
- if(vis[y]==1)//y在x前搜过并回溯了,y在x上面(即dfs序更小),其根节点即为最近公共祖先
- {
- int anc=f_ind(y);
- ans[id]=anc;//x->y的距离=x到根节点距离+y到根节点距离-2*两者最近公共祖先到根节点距离
- }
- }
- }
- int main()
- {
- cin>>n>>m>>s;
- for(int i=1;i<=n;i++)p[i]=i;//初始化
- for(int i=1;i<n;i++)
- {
- int x,y,c;
- cin>>x>>y;
- addedge(x,y);
- addedge(y,x);
- }
- for(int i=1;i<=m;i++)
- {
- int x,y;
- cin>>x>>y;
- q[x].push_back({y,i});//存储询问的另一个数和询问的序号
- q[y].push_back({x,i});
- }
- tarjan(s);
- for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
- return 0;
- }

(acwing)距离
- #include <map>
- #include <set>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=11000;
- const ll M=21111;
- typedef pair<int,int> PII;
- int n,m,head[N],cnt,dis[N],p[N],ans[M];
- int vis[N];//注意vis为int类型
- vector<PII>q[M];
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=head[x];
- head[x]=cnt;
- }
- int f_ind(int x)
- {
- return p[x]=x==p[x]?x:f_ind(p[x]);
- }
- void dfs(int x,int fa)
- {
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(y==fa)continue;
- dis[y]=dis[x]+edge[i].w;
- dfs(y,x);
- }
- }
- //0号点:未访问
- //1号点:正在访问,还没完成回溯(更新其子节点的p值和更新ans)
- //2号点:已经访问完并回溯
- void tarjan(int x)
- {
- vis[x]=1;//当前路径标记为1
- for(int i=head[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(!vis[y])
- {
- tarjan(y);
- p[y]=x;//将y合并到x的根节点(这里的根不一定是整个树的根,很大概率是那些还没完成回溯的,即其p[]没有被更新为其父节点
- }
- }
- for(auto i : q[x])
- {
- int y=i.first,id=i.second;
- if(vis[y]==2)//y在x前搜过并回溯了,y在x上面(即dfs序更小),其根节点即为最近公共祖先
- {
- int anc=f_ind(y);
- ans[id]=dis[x]+dis[y]-2*dis[anc];//x->y的距离=x到根节点距离+y到根节点距离-2*两者最近公共祖先到根节点距离
- }
- }
- vis[x]=2;
- }
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)p[i]=i;//初始化
- for(int i=1;i<n;i++)
- {
- int x,y,c;
- cin>>x>>y>>c;
- addedge(x,y,c);
- addedge(y,x,c);
- }
- for(int i=1;i<=m;i++)
- {
- int x,y;
- cin>>x>>y;
- q[x].push_back({y,i});//存储询问的另一个数和询问的序号
- q[y].push_back({x,i});
- }
- dfs(1,-1);//求出所有点到根节点(随便取)的距离
- tarjan(1);
- for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
- return 0;
- }

(牛客)Ancestor(离线tarjan求最近公共祖先+维护一堆点的最近公共祖先)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=101000;
- const ll M=211111;
- typedef pair<ll,ll> PII;
- ll n,k,cnt1,cnt2,nod[N],b[N],wa[N],wb[N],h1[N],h2[N];
- ll dep1[N],dep2[N],ans,idx1,idx2,time1,time2;
- vector<PII>q1[M],q2[M];
- bool vis1[N],vis2[N];
- ll ans1[N],ans2[N],p1[N],p2[N];
- struct NODE
- {
- ll x,dep;
- bool operator<(const NODE&t)const
- {
- return dep>t.dep;
- }
- };
- int f_ind1(int x)
- {
- return p1[x]=x==p1[x]?x:f_ind1(p1[x]);
- }
- int f_ind2(int x)
- {
- return p2[x]=x==p2[x]?x:f_ind2(p2[x]);
- }
- vector<NODE>v1,v2;
- struct EDGE
- {
- int x,y,neaxty;
- }ea[M],eb[M];
- void addedge1(int x,int y)
- {
- ea[++cnt1].x=x;
- ea[cnt1].y=y;
- ea[cnt1].neaxty=h1[x];
- h1[x]=cnt1;
- }
- void addedge2(int x,int y)
- {
- eb[++cnt2].x=x;
- eb[cnt2].y=y;
- eb[cnt2].neaxty=h2[x];
- h2[x]=cnt2;
- }
- void dfs1(int x,int fa)
- {
- dep1[x]=++time1;//dfs序不能写在循环里面,否则只有60分
- for(int i=h1[x];i;i=ea[i].neaxty)
- {
- int y=ea[i].y;
- if(y==fa)continue;
- dfs1(y,x);
- }
- }
- void dfs2(int x,int fa)
- {
- dep2[x]=++time2;
- for(int i=h2[x];i;i=eb[i].neaxty)
- {
- int y=eb[i].y;
- if(y==fa)continue;
- dfs2(y,x);
- }
- }
- void tarjan1(int x)
- {
- // cout<<x<<endl;
- vis1[x]=1;//当前路径标记为1
- for(int i=h1[x];i;i=ea[i].neaxty)
- {
- int y=ea[i].y;
- if(!vis1[y])
- {
- tarjan1(y);
- p1[y]=x;
- }
- }
- for(auto i : q1[x])
- {
- int y=i.first,id=i.second;
- if(!vis1[y])continue;
- ans1[id]=f_ind1(y);
- }
- }
- void tarjan2(int x)
- {
- vis2[x]=1;//当前路径标记为1
- for(int i=h2[x];i;i=eb[i].neaxty)
- {
- int y=eb[i].y;
- if(!vis2[y])
- {
- tarjan2(y);
- p2[y]=x;
- }
- }
- for(auto i : q2[x])
- {
- int y=i.first,id=i.second;
- // cout<<x<<" "<<y<<endl;
- if(!vis2[y])continue;
- ans2[id]=f_ind2(y);
- // cout<<f_ind2(y)<<"sdf"<<endl;
- }
- }
- //题意:先给出一行x1...xk,xi对应1~n中某个点,有两棵树,对于每棵树,给定n个点和他们的(父子)关系。
- //删掉xi,看A树和B树中由剩余的k-1个点的组成的最近公共祖先的权值谁大,A大答案就++
- //思路:
- //一堆点的最近公共祖先由dfs序最大和dfs序最小的点决定,判断删除的点是否是边界点,是的话就去第二大或第二小的点
- //否则即为处在最大值和最小值之间的点,删了不影响答案
- int main()
- {
- scanf("%lld%lld",&n,&k);
- for(int i=1;i<=k;i++)scanf("%lld",&nod[i]);
- for(int i=1;i<=n;i++)
- {
- scanf("%lld",&wa[i]);
- p1[i]=i;
- p2[i]=i;
- }
- for(int i=1;i<n;i++)
- {
- int y;
- scanf("%d",&y);
- // addedge1(i+1,y);
- addedge1(y,i+1);
- }
- for(int i=1;i<=n;i++)scanf("%lld",&wb[i]);
- for(int i=1;i<n;i++)
- {
- int y;
- scanf("%d",&y);
- // addedge2(i+1,y);
- addedge2(y,i+1);
- }
- dfs1(1,-1);//处理dfs序
- dfs2(1,-1);
- for(int i=1;i<=k;i++)
- {
- v1.push_back({nod[i],dep1[nod[i]]});
- v2.push_back({nod[i],dep2[nod[i]]});
- // cout<<nod[i]<<dep1[nod[i]]<<endl;
- // cout<<nod[i]<<dep2[nod[i]]<<endl;
- }
- sort(v1.begin(),v1.end());
- sort(v2.begin(),v2.end());
-
- for(int i=1;i<=k;i++)
- {
- if(nod[i]==v1.begin()->x)
- {
- q1[(v1.begin()+1)->x].push_back({(v1.end()-1)->x,++idx1});
- q1[(v1.end()-1)->x].push_back({(v1.begin()+1)->x,idx1});
- }
- else if(nod[i]==(v1.end()-1)->x)
- {
- q1[(v1.end()-2)->x].push_back({v1.begin()->x,++idx1});
- q1[v1.begin()->x].push_back({(v1.end()-2)->x,idx1});
- }
- else
- {
- q1[v1.begin()->x].push_back({(v1.end()-1)->x,++idx1});
- q1[(v1.end()-1)->x].push_back({v1.begin()->x,idx1});
- }
- if(nod[i]==v2.begin()->x)
- {
- q2[(v2.begin()+1)->x].push_back({(v2.end()-1)->x,++idx2});
- q2[(v2.end()-1)->x].push_back({(v2.begin()+1)->x,idx2});
- }
- else if(nod[i]==(v2.end()-1)->x)
- {
- q2[(v2.end()-2)->x].push_back({v2.begin()->x,++idx2});
- q2[v2.begin()->x].push_back({(v2.end()-2)->x,idx2});
- }
- else
- {
- q2[(v2.end()-1)->x].push_back({v2.begin()->x,++idx2});
- q2[v2.begin()->x].push_back({(v2.end()-1)->x,idx2});
- }
- }
- tarjan1(1);
- tarjan2(1);
- for(int i=1;i<=idx1;i++)
- {
- if(wa[ans1[i]]>wb[ans2[i]])ans++;
- }
- printf("%lld",ans);
- return 0;
- }

强连通分量
有向图 G中,如果两个顶点vi,vj间,有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点 强连通 。. 如果有向图G的每两个顶点都强连通,称G是一个 强连通图 。. 有向图的极大强连通 子图 ,称为强连通分量
(Tarjan算法)(复杂度o(n+m))
视频:341 强连通分量 Tarjan 算法_哔哩哔哩_bilibili
(洛谷)上白泽慧音(模板)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- int n,m,maxn;//maxn记录最大的组的大小
- int dfn[60005],low[60005],tot;//节点x第一次被访问的顺序, 和从节点x出发,所能访问到的最早时间戳
- int stk[60005],instk[60005],top;
- int scc[60005],siz[60005],cnt;//记录某个点属于哪一组,那一组的大小
- vector<int>e[50005];
- void tarjan(int x)
- {
- dfn[x]=low[x]=++tot;//一开始都是自己
- stk[++top]=x,instk[x]=1;//入栈
- for(int i=0;i<e[x].size();i++)//遍历所有连边的子节点
- {
- int y=e[x][i];
- if(!dfn[y])//没被访问
- {
- tarjan(y);
- low[x]=min(low[x],low[y]);//更新
- }
- else if(instk[y])//被访问过但还没出栈
- {
- low[x]=min(low[x],dfn[y]);//注意这里是dfn[y]而不是low[y]
- }//已出栈的就不用管
- }
- if(dfn[x]==low[x])
- {
- int y;
- ++cnt;
- do{
- y=stk[top--],instk[y]=0;//取栈顶,且出栈
- scc[y]=cnt,siz[cnt]++;//记录该点所属组,更新改组大小
- maxn=max(maxn,siz[cnt]);//题目:维护最大的组的大小
- }while(y!=x);
- }
-
- }
- int main()
- {
- cin>>n>>m;
- while(m--)
- {
- int a,b,t;
- cin>>a>>b>>t;
- if(t==1)
- {
- e[a].push_back(b);
- }
- else
- {
- e[a].push_back(b);
- e[b].push_back(a);
- }
- }
- for(int i=1;i<=n;i++)
- {
- if(!dfn[i])tarjan(i);
- }
- cout<<maxn<<endl;
- int mar=0;
- for(int i=1;i<=n;i++)//按编号小到大扫一遍取第一个所在的强连通分量中的点数==cnt的强连通分量(这个强连通分量一定是所求的,因为这个强连通分量最大且有最小的编号来使字典序最小)
- {
- if(siz[scc[i]]==maxn)
- {
- mar=scc[i];
- }
- if(mar&&scc[i]==mar)
- {
- cout<<i<<" ";
- }
- }
- return 0;
- }

Tarjan缩点
tarjan缩点后,组别序号逆序就直接满足拓扑序
(洛谷)校园网络
视频:342 Tarjan SCC 缩点_哔哩哔哩_bilibili
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- int n;
- int dfn[11111],low[11111],tot;
- int stk[11111],instk[11111],top;
- int scc[11111],siz[11111],cnt;
- int in[11111],oud[11111];
- vector<int>e[11111];
- void tarjan(int x)
- {
- dfn[x]=low[x]=++tot;
- stk[++top]=x,instk[x]=1;
- for(int i=0;i<e[x].size();i++)
- {
- int y=e[x][i];
- if(!dfn[y])
- {
- tarjan(y);
- low[x]=min(low[x],low[y]);
- }
- else if(instk[y])
- {
- low[x]=min(low[x],dfn[y]);//注意这里是dfn[y]而不是low[y]
- }
- }
- if(dfn[x]==low[x])
- {
- int y;
- ++cnt;
- do
- {
- y=stk[top--],instk[y]=0;
- scc[y]=cnt,siz[cnt]++;
- }while(y!=x);
- }
- }
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- int y;
- while(cin>>y)
- {
- if(y==0)break;
- e[i].push_back(y);
- }
- }
- for(int i=1;i<=n;i++)//tarjan强连通分量
- {
- if(!dfn[i])tarjan(i);
- }
- for(int i=1;i<=n;i++)//统计缩点后**入度为0和出度为0的点的个数 ,复杂度o(m)
- {
- for(int j=0;j<e[i].size();j++)
- {
- if(scc[i]!=scc[e[i][j]])//这里不止一次把e[i][j]写成j了
- {
- oud[scc[i]]++;//这里只用粗略统计
- in[scc[e[i][j]]]++;//这里不止一次把e[i][j]写成j了
- }
- }
- }
- int suma=0,sumb=0;
- for(int i=1;i<=cnt;i++)
- {
- if(!in[i])suma++;
- if(!oud[i])sumb++;
- }
- cout<<sumb<<endl;//按题意,为出度为0的点的个数
- if(cnt==1)cout<<0;
- else
- cout<<max(suma,sumb);//按题意,构成强连通分量所需加的边为出度为0和入度为0的点个数的max,只有一个强连通分量除外
- return 0;
- }

(洛谷)受欢迎的牛 G
(acwing)银河(思维+tarjan缩点+重建图+dp)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=111000;
- const ll M=633333;
- typedef pair<int,int> PII;
- int n,m,h[N],hs[N],cnt;
- ll dis[N];
- int dfn[N],low[N],tot;
- int stk[N],instk[N],top;
- int scc[N],siz[N],idx;
- struct EDGE
- {
- int x,y,w,neaxty;
- }edge[M];
- void addedge(int h[],int x,int y,int w)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].w=w;
- edge[cnt].neaxty=h[x];
- h[x]=cnt;
- }
- void tarjan(int x)
- {
- dfn[x]=low[x]=++tot;
- stk[++top]=x,instk[x]=1;
- for(int i=h[x];i;i=edge[i].neaxty)
- {
- int y=edge[i].y;
- if(!dfn[y])
- {
- tarjan(y);
- low[x]=min(low[x],low[y]);
- }
- else if(instk[y])
- {
- low[x]=min(low[x],dfn[y]);
- }
- }
- if(dfn[x]==low[x])
- {
- idx++;
- int y;
- do
- {
- y=stk[top--];instk[y]=0;
- scc[y]=idx,siz[idx]++;
-
- }while(y!=x);
- }
- }
- //条件1:a>=b,b>=a
- //条件2:a<b -> b>=a+1
- //条件3:a>=b
- //条件4:a>b -> a>=b+1
- //条件5:a<=b -> b>=a
- //条件6:x>=x0+1
- //易得知差分约束求最小值,用最长路,无解即存在正环,即环中有边权>0,又由题,边权无负值,所以当一个强连通分量(环)中边权全=0时有解
- //所以tarjan判断强连通分量,然后看每个强连通分量中是否有边权>0
- //若没有,则有解,缩点重建图,又tarjan处理后,每个点满足拓扑序,直接dp
- int main()
- {
- cin>>n>>m;
- while(m--)
- {
- int t,a,b;
- cin>>t>>a>>b;
- if(t==1)addedge(h,a,b,0),addedge(h,b,a,0);
-
- else if(t==2)addedge(h,a,b,1);
-
- else if(t==3)addedge(h,b,a,0);
-
- else if(t==4)addedge(h,b,a,1);
-
- else if(t==5)addedge(h,a,b,0);
- }
- for(int i=1;i<=n;i++)
- {
- addedge(h,0,i,1);
- }
- // for(int i=0;i<=n;i++)
- // {
- // if(!dfn[i])tarjan(i);
- // }
- tarjan(0);//因为0为超级源点,连向所有点和边,tarjan(0)就够了
- bool flag=true;//判断在强连通分量内是否存在正边权
- for(int i=0;i<=n;i++)
- {
- for(int j=h[i];j;j=edge[j].neaxty)
- {
- int y=edge[j].y;
- int a=scc[i],b=scc[y];
- if(a==b)//处在同个强连通分量
- {
- if(edge[j].w>0)
- {
- flag=false;//存在正边权,无解
- break;
- }
- }
- else
- {
- addedge(hs,a,b,edge[j].w);//不属于同个强连通分量,将这两个强连通分量连一条边
- }
- }
- }
- if(!flag)cout<<-1;
- else
- {
- ll ans=0;
- for(int i=idx;i;i--)//tarjan并逆序,则为 拓扑序
- {
- for(int j=hs[i];j;j=edge[j].neaxty)//直接dp
- {
- int y=edge[j].y;
- dis[y]=max(dis[y],dis[i]+edge[j].w);
- }
- }
- for(int i=1;i<=idx;i++)ans+=(ll)dis[i]*siz[i];
- cout<<ans;
- }
- return 0;
- }

(acwing)最大半连通子图(思维+tarjan缩点+重建图+边去重+dp)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll MOD =1e9+7;
- const ll N=100010;
- const ll M=4000010;
- typedef pair<int,int> PII;
- int n,m,h[N],hs[N],cnt,mod;
- int dfn[N],low[N],tot;
- int stk[N],instk[N],top;
- int scc[N],siz[N],idx;
- int f[N],g[N];//dp维护最长链和方案数
- struct EDGE
- {
- int x,y,neaxty;
- }edge[M];
- void addedge(int h[],int x,int y)
- {
- edge[++cnt].x=x;
- edge[cnt].y=y;
- edge[cnt].neaxty=h[x];
- h[x]=cnt;
- }
- void tarjan(int u)
- {
- dfn[u] = low[u] = ++ tot ;
- stk[++ top] = u,instk[u] =true;
- for(int i =h[u]; i;i = edge[i].neaxty)
- {
- int j = edge[i].y;
- if(!dfn[j])
- {
- tarjan(j);
- low[u] = min(low[u],low[j]);
- }
- else if(instk[j]) low[u] = min(low[u] , dfn[j]);
- }
-
- if(dfn[u] == low[u])
- {
- idx ++;
- int y;
- do{
- y = stk[top --];
- instk[y] = false;
- scc[y] = idx;
- siz[idx] ++;
- }while(y != u);
- }
- }
-
- int main()
- {
- cin>>n>>m>>mod;
- while(m--)
- {
- int a,b;
- cin>>a>>b;
- addedge(h,a,b);
- }
- for(int i=1;i<=n;i++)
- {
- if(!dfn[i])
- tarjan(i);
- }
- unordered_set<ll>ss;
- for(int i=1;i<=n;i++)
- {
- for(int j=h[i];j;j=edge[j].neaxty)
- {
- int y=edge[j].y;
- int a=scc[i],b=scc[y];//缩点
- if(a==b)continue;
- ll hash= a*1000000ll+b;//简易哈希
- if(!ss.count(hash))//判断重边
- {
- addedge(hs,a,b);
- ss.insert(hash);
- }
- }
- }
- for(int i = idx; i ;i --)
- //由于编号更大的点所在的强连通分量总是更先被找到,且这里要保证顺序,所以我们要逆着循环!
- {
- if(! f[i])
- {
- f[i] = siz[i];
- g[i] = 1;
- }
- for(int j = hs[i]; j ; j = edge[j].neaxty)
- {
- int k = edge[j].y;
- if(f[k] < f[i] + siz[k])
- {
- f[k] = f[i] + siz[k];
- g[k] = g[i];
- }
- else if(f[k] == f[i] + siz[k]) //如果以“点”的为终点的两条长链长度相同,那么将所得的的数目相加
- g[k] = (g[k] + g[i]) % mod;//数目很多,记得要%mod哦
- }
- }
- int maxn = 0 ,sum = 0;
- for(int i = 1;i <= idx;i ++)
- if(f[i] > maxn)
- {
- maxn = f[i];
- sum = g[i];
- }
- else if(f[i] == maxn) sum = (sum + g[i]) % mod;//将其他点所携带的最长链数目相加!
- cout<<maxn<<endl<<sum;
- return 0;
- }

Tarjan割点
(洛谷)【模板】割点(割顶)
tarjan部分与上面的模板有所不同,已标出
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- const int imax=1e9;
- const ll lmax=2e18;
- const ll mod =1e9+7;
- #define N 22222
- #define M 222222
- int n,m,sum;
- int dfn[N],low[N],tot;
- int stk[N],instk[N],top;
- int scc[N],siz[N],cnt,root;
- bool cut[N];
- vector<int>e[N];
- void tarjan(int x)
- {
- dfn[x]=low[x]=++tot;
- int child=0;
- for(int i=0;i<e[x].size();i++)
- {
- int y=e[x][i];
- if(!dfn[y])
- {
- tarjan(y);
- low[x]=min(low[x],low[y]);
- //1.割点为根节点,搜索树上存在两个子节点满足low[y]>=dfn[x] 2.割点不为根节点,只需一个就够
- if(low[y]>=dfn[x])
- {
- child++;
- if(x!=root||child>=2)
- {
- cut[x]=1;
- }
- }
- }
- else//1.不用特判是否在栈内
- {
- low[x]=min(low[x],dfn[y]);
- }
- }
- //这里不用记录分组
- }
- int main()
- {
- cin>>n>>m;
- while(m--)
- {
- int x,y;cin>>x>>y;
- e[x].push_back(y);
- e[y].push_back(x);
- }
- for(int i=1;i<=n;i++)
- {
- if(!dfn[i])
- {
- root=i;//没搜索过就以他为根节点搜索
- tarjan(i);
- }
- }
- for(int i=1;i<=n;i++)
- {
- if(cut[i])
- {
- sum++;
- }
- }
- cout<<sum<<endl;
- for(int i=1;i<=n;i++)
- {
- if(cut[i])cout<<i<<" ";
- }
- return 0;
- }

(洛谷)嗅探器(割点+思维)
欧拉路径
欧拉路径(欧拉通路):通过图中所有边的简单路。(换句话说,每条边都通过且仅通过一次)也叫”一笔画”问题。
欧拉回路:闭合的欧拉路径。(即一个环,保证每条边都通过且仅通过一次)
欧拉图:包含欧拉回路的图。
一、无向图
1 存在欧拉路径的充要条件 : 度数为奇数的点只能有0或2个
2 存在欧拉回路的充要条件 : 度数为奇数的点只能有0个 3.边连通,即cnt==m
二、有向图
1 存在欧拉路径的充要条件 : 要么所有点的出度均==入度;
要么除了两个点之外,其余所有点的出度==入度 剩余的两个点:一个满足出度-入度==1(起点) 一个满足入度-出度==1(终点)
2 存在欧拉回路的充要条件 : 所有点的出度均等于入度 3.边连通,即cnt==m
(acwing)欧拉回路(判断有向图和无向图中的欧拉回路并输出)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=110111;
- const ll M=444444;
- typedef pair<int,int> PII;
- int n,m,t,cnt;
- int idx,e[M],h[N],ne[M];
- int din[N],dou[N],ans[M],tot;
- bool used[M];
- void add(int x,int y)
- {
- e[idx]=y,ne[idx]=h[x],h[x]=idx++;
- }
- void dfs(int x)
- {
- for(int &i=h[x];~i;)
- {
- if(used[i])
- {
- i=ne[i];//删边,因为i用了引用,这里相当于h[x]=ne[i],i=h[x]
- continue;
- }
- used[i]=1;//这里写used[i]=1只是代码规范而已(因为边都删了),used真正作用是要标记的是无向边的另外一条边
-
- if(t==1)used[i^1]=1;//无向边,则要标记两条边 ,,边的组合(0,1) (2,3) (3,4)
- int c;//记录第几条边
- if(t==1)//无向图
- {
- c=i/2 + 1;//第几条边
- if(i&1)c*=-1;//返回的边(题目要求)
- }
- else c=i+1;
-
- int j=e[i];
- i=ne[i];//先删边,再遍历
- dfs(j);
-
- ans[++cnt]=c;//存欧拉路径解释:如果某点有多条边,且有环,则某条边可能会dfs直通终点,所以要遍历完该点所有邻边,回溯时再存入点(边),最后再逆序输出才能不漏
- }
- }
- //补充:每条边用过之后要删掉,不能只标记used[]。不然如果有m条自环,那么第一层走第一个自环,第二层走第二个自环,第三层走第三个自环,
- //依次类推,走第k个自环就要遍历k次,所以总共会遍历 O(m2)次(即使有continue)。但是删掉用过的边就不会重复遍历了,就是 O(m)了
- int main()
- {
- cin>>t;
- cin>>n>>m;
- memset(h,-1,sizeof h);
- for(int i=1;i<=m;i++)
- {
- int x,y;
- cin>>x>>y;
- add(x,y);
- if(t==1)add(y,x);
- din[y]++,dou[x]++;
- }
- if(t==1)//无向图
- {
- for(int i=1;i<=n;i++)
- {
- if((din[i]+dou[i])%2)//无向图含欧拉回路的条件是每个点的度数为偶数
- { //无向图中,每个点的度数=(入度+出度)/2,因为一条边就可以让该点出度+1,入度+1,这里没有/2是因为前面入度和出度加少了
- puts("NO");
- return 0;
- }
- }
- }
- else
- {
- for(int i=1;i<=n;i++)
- {
- if(din[i]!=dou[i])//有向图含欧拉回路的条件是每个点出度=入度
- {
- puts("NO");
- return 0;
- }
- }
- }
- for(int i=1;i<=n;i++)
- {
- if(~h[i])//防止有孤立点
- {
- dfs(i);
- break;
- }
- }
- if(cnt<m)//边不连通
- {
- puts("NO");
- return 0;
- }
-
- puts("YES");
- for(int i=cnt;i>=1;i--)cout<<ans[i]<<" ";
- return 0;
- }

(acwing)骑马修栅栏(欧拉路径)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=666;
- const ll M=2222;
- typedef pair<int,int> PII;
- int n,m,t,cnt;
- int g[N][N];//邻接矩阵
- int d[N],ans[M],tot;
- bool used[M];
- void dfs(int x)
- {
- for(int i=1;i<=n;i++)
- {
- if(!g[x][i])continue;
- g[x][i]--,g[i][x]--;//删边
- dfs(i);
- }
- ans[++cnt]=x;//存欧拉路径解释:如果某点有多条边,且有环,则某条边可能会dfs直通终点,所以要遍历完该点所有邻边,回溯时再存入点(边),最后再逆序输出才能不漏
- //这里的点则是要遍历完所有的邻点再存自己
- }
- //思路:欧拉路径问题,对于输出最小解,从序号最小的点开始dfs(若从x点开始,因为回溯才记录答案,x会被放到ans数组末尾,但输出时因为逆序又来到最前面)
- //然后对于一个点,若有多条边,优先选择出点序号小的(只能用邻接矩阵实现了)
- //对于此题,没给出起点和终点,找度数为奇数的点作为起点开始dfs就行,但有可能是欧拉回路,不存在奇数点,就选小的点作起点
- int main()
- {
- n=500;
- cin>>m;
- for(int i=1;i<=m;i++)
- {
- int x,y;
- cin>>x>>y;
- g[x][y]++,g[y][x]++;
- d[x]++,d[y]++;
-
- }
- int start = 1;
- while (!d[start]) ++start;
- for(int i=1;i<=n;i++)
- {
- if(d[i]%2)//找度数为奇数的点作为起点开始dfs
- {
- start=i;
- break;
- }
- }
- dfs(start);
- for(int i=cnt;i>=1;i--)cout<<ans[i]<<endl;
- return 0;
- }

(acwing)单词游戏(判断有向图的欧拉路径)
- #include <bits/stdc++.h>
- using namespace std;
- #define LL __int128
- #define ll long long
- #define ull unsigned long long
- #define INF 0x3f3f3f3f
- const ll lmax=2e18;
- const ll mod =1e9+7;
- const ll N=30;
- const ll M=111111;
- typedef pair<int,int> PII;
- int t,n;
- int e[M],ne[M],h[N],idx,used[M];
- int din[N],dou[N],ds,de,cnt;
- //思路:题意是将所有单词排成一整排,判断有向图的欧拉路径
- void add(int x,int y)
- {
- e[idx]=y,ne[idx]=h[x],h[x]=idx++;
- }
- void dfs(int x)
- {
- for(int &i=h[x];~i;)
- {
-
- int j=e[i];
- i=ne[i];
- dfs(j);
- cnt++;
- }
- }
- //题意: 能否依据条件(头尾相连),每个单词用一次,且用完所有单词
- //判断有向图 是否为欧拉路径
- int main()
- {
- cin>>t;
- while(t--)
- {
- memset(h,-1,sizeof h);
- memset(din,0,sizeof din);
- memset(dou,0,sizeof dou);
- ds=de=cnt=0;
- idx=0;
- cin>>n;
- string str;
- for(int i=1;i<=n;i++)
- {
- cin>>str;
- int a=str[0]-'a';
- int b=str[str.size()-1]-'a';
- // cout<<a<<" "<<b<<endl;
- add(a,b);
- dou[a]++,din[b]++;
- }
- bool flag=true;
- for(int i=0;i<26;i++)
- {
- if(din[i]!=dou[i])
- {
- if(din[i]-dou[i]==1)de++;//记录入度-出度=1的点的数量
- else if(dou[i]-din[i]==1)ds++;//记录出度-入度=1的点的数量
- else flag=false;
- }
- }
-
- if(!((!ds&&!de)||(ds==1 && de==1))) flag=false;//如果不是环同时起点和终点数量不为1
-
- int start=0;
- while(!dou[start]) ++start;//可能是环,没有起点(有点模板的意思了)
-
- for(int i=0;i<26;i++)
- {
- if(dou[i]-din[i]==1)//从起点开始dfs
- {
- start=i;
- break;
- }
- }
- dfs(start);
- if(cnt!=n)flag=false;
- if(flag) cout<<"Ordering is possible."<<endl;
- else cout<<"The door cannot be opened."<<endl;
- }
- return 0;
- }

——————————————————————————————————————————
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。