当前位置:   article > 正文

洛谷or牛客数据结构+算法_洛谷 牛客

洛谷 牛客

栈思想:先进后出

tips:栈里能放下标就放下标

(牛客)小c的计事本(直接用stack可以简化代码,且不会被自己绕晕,当时没意识到)

(牛客)吐泡泡(没意识到用栈),(牛客)好串

1.后缀表达式(栈)

  1. #include <stack>
  2. #include <cstring>
  3. 有关一些细节
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <stdlib.h>
  7. using namespace std;
  8. int main()
  9. {
  10. char a,b[100];
  11. stack<int> s;
  12. int q=0;
  13. while(1)
  14. {
  15. while((a=getchar())!='.'&&(a!='@'))
  16. {
  17. if(a>='0'&&a<='9') b[q++]=a;//临时字符串存数字
  18. else//运算符
  19. {
  20. int x1,x2;//x2为前一个数,x1为后一个数
  21. x1=s.top();s.pop();
  22. if(s.empty())x2=0;//特判,若取完x1后栈空,则再取一个数为0
  23. if(!s.empty()){x2=s.top();s.pop();}
  24. if(a=='+')s.push(x1+x2);
  25. else if(a=='-')s.push(x2-x1);//
  26. else if(a=='*')s.push(x1*x2);
  27. else if(a=='/')s.push(x2/x1); //容易整反
  28. }
  29. }
  30. if(a=='@')break;
  31. s.push(atoi(b));//将字符转化为数字
  32. q=0;//重置
  33. memset(b,0,sizeof(b));
  34. }
  35. printf("%d",s.top());
  36. return 0;
  37. }

单调栈 :求第一个大于或小于 x的数

1.(洛谷)单调栈(记住stack一般存放下标)

  1. 单调栈
  2. 求第一个大于的数模板
  3. 从右往左扫描
  4. #include <cstdio>
  5. #include <stack>
  6. using namespace std;
  7. int a[10000000],f[10000000];//a存放输入,f存放答案
  8. int main()
  9. {
  10. int n,i;
  11. stack<int> q; //
  12. scanf("%d",&n);
  13. for(i=1;i<=n;i++)
  14. {
  15. scanf("%d",&a[i]);
  16. }
  17. for(i=n;i>=1;i--)//倒叙录入
  18. {
  19. while(!q.empty()&&a[i]>=a[q.top()])q.pop();//若小于则pop出
  20. f[i]=q.empty()?0:q.top();//三目运算
  21. q.push(i);//存放数字下标 ****细节,省去了很多操作
  22. }
  23. for(i=1;i<=n;i++)
  24. {
  25. if(i>1)printf(" ");
  26. printf("%d",f[i]);
  27. }
  28. return 0;
  29. }

(牛客)小A的柱状图(单调栈总和应用)

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stack>
  4. using namespace std;
  5. const int maxn=1e6+7;
  6. int brr[maxn],sum1[maxn],sum2[maxn];
  7. long long ans,arr[maxn];
  8. pair<int,int>mark[maxn];//记录以该矩形为中心向两边扩散时的最小左坐标和最大右坐标
  9. inline long long get_s(int x,int y,int i)
  10. {
  11. return arr[i]*(sum1[x]-sum1[y+1]);
  12. }
  13. int main()
  14. {
  15. int n;scanf("%d",&n);
  16. stack<int>s;//存放数字下标而非数字,可以省很多操作
  17. for(int i=1;i<=n;i++)
  18. {
  19. scanf("%d",brr+i);//宽度
  20. sum2[i]=brr[i]+sum2[i-1];//记录从左到右的宽度前缀和
  21. }
  22. for(int i=1;i<=n;i++)
  23. {
  24. scanf("%lld",arr+i);//长度
  25. }
  26. //
  27. sum1[n+1]=0;
  28. for(int i=n;i>=1;i--)
  29. {
  30. sum1[i]=sum1[i+1]+brr[i];//记录从右到左的宽度前缀和
  31. }
  32. //从右-左遍历arr,查找从左-右第一个小于第i个元素的坐标
  33. arr[n+1]=-maxn;//将栈底设为最小值
  34. s.push(n+1);
  35. for(int i=n;i>=1;i--)
  36. {
  37. while(arr[i]<=arr[s.top()])s.pop();//栈顶如果比待处理值大,出栈
  38. mark[i].second=s.top()-1;//最大右坐标(即从左到右第一个小于arr[i]的值的坐标-1
  39. //ans=max(ans,get_s(i,s.top()-1));//此时栈顶比待处理值小
  40. s.push(i);
  41. }
  42. //从左-右遍历arr,查找从右-左第一个小于第i个元素的坐标
  43. stack<int>ss;ss.push(0);arr[0]=-maxn;
  44. for(int i=1;i<=n;i++)
  45. {
  46. while(arr[i]<=arr[ss.top()])ss.pop();
  47. mark[i].first=ss.top()+1;
  48. ans=max(ans,get_s(mark[i].first,mark[i].second,i));
  49. ss.push(i);
  50. }
  51. printf("%lld",ans);
  52. return 0;
  53. }

--------------------------------------------------------------------------------------------------------------------------------

队列*** 

队列思想:先进先出

(牛客)Keep In Line(很快做出来了)

(洛谷)约瑟夫问题(循环队列)

  1. 循环队列
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <queue>
  5. using namespace std;
  6. int main()
  7. {
  8. int n,m,i,k=0;
  9. queue<int> q;
  10. scanf("%d %d",&n,&m);
  11. for(i=1;i<=n;i++)
  12. q.push(i);
  13. while(!q.empty())
  14. {
  15. for(i=1;i<=m-1;i++)
  16. {
  17. q.push(q.front());//将队头元素放队尾
  18. q.pop();
  19. }
  20. if(k>0)printf(" ");
  21. printf("%d",q.front());
  22. k++;
  23. q.pop();
  24. }
  25. return 0;
  26. }

5.队列安排(list容器*****(唯一用处啊:迭代器数组和s.insert(pos,elem)返回值用处)

  1. 迭代器数组以及s.insert(pos,elem)返回值的用处
  2. #include <list>
  3. #include <algorithm>
  4. #include <iostream>
  5. #define maxn 100010
  6. using namespace std;
  7. list<int>s;
  8. int k=0;
  9. list<int>::iterator pos[maxn];//存放迭代器的数组
  10. bool erased[maxn];//判断是否重复删除(优化速度)//初始值为false***
  11. void print(int val)
  12. {
  13. if(k)cout<<" ";
  14. cout<<val;
  15. k++;
  16. }
  17. int main()
  18. {
  19. int k,p,n,m;
  20. s.insert(s.begin(),1);
  21. pos[1]=s.begin();
  22. cin>>n;
  23. for(int i=2;i<=n;i++)
  24. {
  25. cin>>k>>p;
  26. if(p==1)
  27. {
  28. list<int>::iterator nextpos=pos[k];
  29. nextpos++;
  30. pos[i]=s.insert(nextpos,i);//s.insert返回elem插入的位置(迭代器),用pos[i]来接收元素i的位置
  31. }
  32. else
  33. {
  34. pos[i]=s.insert(pos[k],i);
  35. }
  36. }
  37. cin>>m;
  38. for(int i=0;i<m;i++)
  39. {
  40. int x;
  41. cin>>x;
  42. if(!erased[x])//不重复删除(优化速度)
  43. {
  44. s.erase(pos[x]);
  45. erased[x]=true;
  46. }
  47. }
  48. for_each(s.begin(),s.end(),print);
  49. return 0;
  50. }

(牛客)滑动窗口(单调队列(不是用stl的队列))

  1. 单调队列
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn = 1e6+7;
  7. int arr[maxn],qu[maxn],pu[maxn];
  8. int main()
  9. {
  10. int n,k;scanf("%d%d",&n,&k);
  11. for(int i=1;i<=n;i++)
  12. {
  13. scanf("%d",arr+i);
  14. }
  15. //单调递增队列维护最小值
  16. int l=1,r=0;
  17. for(int i=1;i<=n;i++)
  18. {
  19. while(l<=r&&arr[i]<=qu[r])
  20. {
  21. r--;
  22. }
  23. qu[++r]=arr[i];//待处理值入队
  24. pu[r]=i;//记录编号
  25. if(i-pu[l]>=k)//队首元素过时,出队
  26. {
  27. l++;
  28. }
  29. if(i>=k)printf("%d ",qu[l]);//输出最小值,即队首元素
  30. }
  31. cout<<endl;
  32. //单调递减队列维护最大值
  33. l=1,r=0;memset(qu,0,sizeof qu);memset(pu,0,sizeof pu);
  34. for(int i=1;i<=n;i++)
  35. {
  36. while(l<=r&&arr[i]>=qu[r])
  37. {
  38. r--;
  39. }
  40. qu[++r]=arr[i];
  41. pu[r]=i;
  42. if(i-pu[l]>=k)
  43. {
  44. l++;
  45. }
  46. if(i>=k)printf("%d ",qu[l]);
  47. }
  48. return 0;
  49. }

--------------------------------------------------------------------------------------------------------------------------------

堆(**优先队列**):一个能够维护当前最大/最小值的队列

(牛客)优先队列,并查集题单:

合并果子,第k小,tokisukaze and soldier,建筑抢修,缓存交换(似懂非懂)(目前有点不理解什么题要用到堆)

对顶堆(洛谷:中位数)(用于*动态*维护第k大的数,,eg,中位数)

  1. 对顶堆,求解中位数
  2. #include <iostream>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7. priority_queue<int,vector<int>,greater<int>>last;//小根堆
  8. priority_queue<int,vector<int>>pre;//大根堆
  9. int main()
  10. {
  11. int n,ch;
  12. cin>>n;
  13. for(int i=1;i<=n;i++)
  14. {
  15. cin>>ch;
  16. if(!pre.size()||ch<pre.top())
  17. {
  18. pre.push(ch);
  19. }
  20. else if(ch>pre.top())
  21. {
  22. last.push(ch);
  23. }
  24. int u=pre.size(),v=last.size();
  25. while(abs(u-v)>1) //使大小根堆元素个数差值<=1直接abs(pre.size()...洛谷会报错dev不会
  26. {
  27. if(pre.size()>last.size())
  28. {
  29. last.push(pre.top());pre.pop();
  30. }
  31. else
  32. {
  33. pre.push(last.top());last.pop();
  34. }
  35. u=pre.size(),v=last.size();
  36. }
  37. if(i%2!=0)
  38. {
  39. if(pre.size()>last.size())cout<<pre.top()<<endl;
  40. else cout<<last.top()<<endl;
  41. }
  42. }
  43. return 0;
  44. }

对顶堆2(牛客:直播获奖)

  1. 直播获奖
  2. 用multiset来自动排序求第p大的数,复杂度o(n^2),tle了
  3. 而对顶堆可以动态维护第k大的值
  4. #include <queue>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <iostream>
  8. using namespace std;
  9. priority_queue<int>pre;
  10. priority_queue<int,vector<int>,greater<int>>last;
  11. int main()
  12. {
  13. int n,w,p;scanf("%d%d",&n,&w);
  14. for(int i=1;i<=n;i++)
  15. {
  16. int ch;
  17. scanf("%d",&ch);
  18. if(!last.size()||ch>last.top())
  19. {
  20. last.push(ch);
  21. }
  22. else
  23. {
  24. pre.push(ch);
  25. }
  26. p=max(1,(int)(i*w/100));
  27. while(last.size()!=p)//令大根堆的数量=p,则大根堆的top即是两个队列中排位第p的元素
  28. {
  29. if(last.size()<p)
  30. {
  31. last.push(pre.top());pre.pop();
  32. }
  33. else
  34. {
  35. pre.push(last.top());last.pop();
  36. }
  37. }
  38. printf("%d ",last.top());
  39. }
  40. return 0;
  41. }

对顶堆3 (牛客)第k小 

st表(o(logn)预处理,o(1)查找静态区间最大值)

(洛谷)【模板】ST 表

视频:STUACM-算法讲堂-ST表(区间最值问题)_哔哩哔哩_bilibili

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. #define ll long long
  6. #define ull unsigned long long
  7. int n,m,dp[111111][40];//定义dp[i][j]为从起点i开始长度为2的j次方(1<<j)的区间的最大值
  8. int main()
  9. {
  10. scanf("%d %d",&n,&m);
  11. for(int i=1;i<=n;i++)scanf("%d",&dp[i][0]);
  12. int lc=(int)(log(n)/log(2));//计算log2(n),即最大的 j
  13. for(int j=1;j<=lc;j++)//i和j不能换,从小区间推大区间
  14. {
  15. for(int i=1;i+(1<<j)-1<=n;i++)//RE的原因大概是循环条件写错了
  16. {
  17. dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);//区间对半分开
  18. }
  19. }
  20. while(m--)
  21. {
  22. int l,r;
  23. scanf("%d %d",&l,&r);
  24. int x=(int)(log(r-l+1)/log(2));//计算log2(len),为向下取整数
  25. printf("%d\n",max(dp[l][x],dp[r-(1<<x)+1][x]));//这里的区间大概率有重叠,但不影响答案
  26. }
  27. return 0;
  28. }

---------------------------------------------------------------------------------------------------------------------------------

1.***差分:(牛客)借教室  

题解:(25条消息) 【每日一题】7月1日题目精讲 借教室_Jozky86的博客-CSDN博客

二维差分+二维前缀和  (牛客)瓜瓜选妃 K-瓜瓜选妃_浙江农林大学第二十二届程序设计竞赛(同步) (nowcoder.com)

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. int n,m,k,x1[111111],y1[111111],x2[111111],y2[111111],sum[600][600],ans=-1;
  5. bool check(int x)
  6. {
  7. memset(sum,0,sizeof sum);
  8. for(int i=1;i<=x;i++)
  9. {
  10. sum[x1[i]][y1[i]]++;//二维差分
  11. sum[x1[i]][y2[i]+1]--;//哪些地方要加1?有2的地方
  12. sum[x2[i]+1][y1[i]]--;
  13. sum[x2[i]+1][y2[i]+1]++;
  14. }
  15. for(int i=1;i<=n;i++)
  16. {
  17. for(int j=1;j<=m;j++)
  18. {
  19. sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//二维前缀和
  20. if(!sum[i][j])return false; //注意一定是+=
  21. }
  22. }
  23. return true;
  24. }
  25. int main()
  26. {
  27. cin>>n>>m>>k;
  28. for(int i=1;i<=k;i++)
  29. {
  30. cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
  31. }
  32. int l=1,r=k;
  33. while(l<=r)
  34. {
  35. int mid=(l+r)>>1;
  36. if(check(mid))
  37. {
  38. r=mid-1;
  39. ans=mid;
  40. }
  41. else
  42. {
  43. l=mid+1;
  44. }
  45. }
  46. cout<<ans;
  47. return 0;
  48. }

(acwing 1761)二维前缀和+二维差分+(二维前缀和中对面积的特殊处理)

图解:

(牛客)货物种类 *

(map存点的前缀和,差分)acwing:4195(具有特殊性,一般差分题用不到,因为不能维护每个点的状态)

2.***前缀和(写之前记得数据上下界,让数据下界从1开始(因为sum[i]=sum[i-1])

若从0开始可能回忽略掉sum[0]的情况

异或前缀和:(牛客)Xorto

二维前缀和:(牛客)「土」秘法地震

图解 

(牛客)储物点的距离

(牛客)激光炸弹

(牛客)周周的泡泡(用前缀和+二分  枚举任意长的一段区间(符合题意的))

L-周周的泡泡_浙江农林大学第二十二届程序设计竞赛(同步) (nowcoder.com)

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. #define ll long long
  5. ll sum[222222],ans=-1;
  6. int n,h,arr[222222];
  7. int main()
  8. {
  9. scanf("%d %d",&n,&h);
  10. for(int i=1;i<=n;i++)//思路:用前缀和来表示中间x个连续的泡泡的高度和
  11. { //(考场上任意x个连续泡泡的高度和不会用nlgn枚举,虽然想到upper,但是不知道搜啥)
  12. scanf("%d",&arr[i]);
  13. sum[i]=sum[i-1]+arr[i];
  14. }
  15. if(sum[n]<h){cout<<h-sum[n];return 0;}//如果不用删
  16. for(int i=1;i<=n;i++)
  17. {
  18. int x=upper_bound(sum+1,sum+1+n,sum[n]+sum[i-1]-h)-sum;//二分查找
  19. if(i<=x&&x<=n)
  20. ans=max(ans,sum[n]-sum[x]+sum[i-1]);
  21. //x表示连续泡泡的右区间,用i来枚举左区间
  22. //sum[n]-(sum[x]-sum[i-1])<h
  23. //sum[n]+sum[i-1]-h<sum[x]
  24. }
  25. cout<<h-ans;
  26. return 0;
  27. }

3.***并查集

有时不开sz数组来比较,直接合并可能会爆内存

(牛客)经商   

(牛客)(类似二维并查集)小c的周末

(牛客)奶酪

(牛客)「Nhk R1 C」Zet'ubou Another(并查集解决联通块+思维)

(天梯赛)L2-013 红色警报 (动态判断割点)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. #define N 600
  10. #define M 5005*2
  11. int n,m,sum,cnt;
  12. int head[N],k,fa[N];
  13. int vis1[N],vis2[N];
  14. struct EDGE
  15. {
  16. int x,y;
  17. }edge[M];
  18. int f_ind(int x)
  19. {
  20. return fa[x]=fa[x]==x?x:f_ind(fa[x]);
  21. }
  22. int judge()
  23. {
  24. int sum=0;
  25. memset(vis2,0,sizeof vis2);
  26. for(int i=0;i<n;i++)fa[i]=i;
  27. for(int i=1;i<=cnt;i++)
  28. {
  29. int x =edge[i].x;
  30. int y =edge[i].y;
  31. if(vis1[x]||vis1[y])continue;//如果这个点被删了,这条边就不要了
  32. fa[f_ind(x)]=fa[f_ind(y)];
  33. }
  34. for(int i=0;i<n;i++)
  35. {
  36. if(vis1[i])continue;//该点已经被删掉
  37. int x = f_ind(i);
  38. if(!vis2[x])//这个集合被统计过了
  39. {
  40. sum++;
  41. vis2[x]=1;
  42. }
  43. }
  44. //cout<<sum<<endl;
  45. return sum;
  46. }
  47. int main()
  48. {
  49. cin>>n>>m;
  50. while(m--)
  51. {
  52. int x=0,y=0;
  53. cin>>x>>y;
  54. edge[++cnt].x=x;
  55. edge[cnt].y=y;
  56. }
  57. int las = 0;
  58. las = judge();//判断集合个数,用las记录上一次统计的集合数
  59. cin>>k;
  60. int tem = n;
  61. for(int i=1;i<=k;i++)
  62. {
  63. int x=0;
  64. cin>>x;
  65. vis1[x]=1;//删点
  66. int tmp = judge();
  67. //cout<<tmp<<endl;
  68. if(las<tmp)//如果删了这个点,集合数变多了,则该点是割点
  69. printf("Red Alert: City %d is lost!\n",x);
  70. else printf("City %d is lost.\n",x);
  71. tem--;
  72. if(tem<=0)cout<<"Game Over."<<endl;
  73. las = tmp;
  74. }
  75. return 0;
  76. }

种类并查集:

(牛客)食物链 讲解:并查集专题讲解 边带权+扩展域_哔哩哔哩_bilibili

(牛客)关押罪犯 

带权并查集

(牛客)食物链 图解:

 讲解:AcWing 240 食物链(并查集)_哔哩哔哩_bilibili

  1. #include <iostream>
  2. using namespace std;
  3. int n,k,fa[60000],d[60000];
  4. long long ans;
  5. int mod(int x)
  6. {
  7. return (x+3)%3;
  8. }
  9. int f_ind(int x)
  10. {
  11. if(fa[x]==x)return x;
  12. int root=f_ind(fa[x]);
  13. d[x]=mod(d[x]+d[fa[x]]);
  14. fa[x]=root;
  15. return fa[x];
  16. }
  17. void Union(int x,int y,int t)
  18. {
  19. int fx=f_ind(x),fy=f_ind(y);
  20. fa[fx]=fy;
  21. d[fx]=mod(t+d[y]-d[x]);
  22. return;
  23. }
  24. int main()
  25. {
  26. scanf("%d %d",&n,&k);
  27. for(int i=1;i<=n;i++)fa[i]=i;
  28. while(k--)
  29. {
  30. int t,x,y;
  31. scanf("%d %d %d",&t,&x,&y);
  32. if((x==y&&t==2)||x>n||y>n)ans++;
  33. else if(t==1)
  34. {
  35. if(f_ind(x)==f_ind(y))//在一个集合里
  36. {
  37. if(mod(d[x])!=mod(d[y]))ans++;
  38. }
  39. else//不在一个集合里
  40. {
  41. Union(x,y,0);//将x和y以同类形式合并
  42. }
  43. }
  44. else if(t==2)
  45. {
  46. if(f_ind(x)==f_ind(y))//已经在一个集合内
  47. {
  48. if(mod(d[x]-d[y])!=1)ans++;
  49. }
  50. else//不在一个集合
  51. {
  52. Union(x,y,1);
  53. }
  54. }
  55. }
  56. cout<<ans;
  57. return 0;
  58. }

---------------------------------------------------------------------------------------------------------------------------------

线段树与树状数组

线段树1(模板)(区间加法,区间乘法,区间求和)(也可实现单点修改,求单点值)

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. #define ll long long
  6. #define inf 0x3f3f3f3f
  7. ll a[111111],n,m,mod=inf;
  8. struct Tree
  9. {
  10. ll l,r,add,mul=1,sum;
  11. }t[444444];//线段树要开4倍空间
  12. inline void push_up(ll p)
  13. {
  14. t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
  15. }
  16. inline void push_down(ll p)
  17. {
  18. 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;
  19. 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啦
  20. t[p*2].add=(t[p*2].add*t[p].mul+t[p].add)%mod;//sumadd一样,都是先乘后加
  21. t[p*2+1].add=(t[p*2+1].add*t[p].mul+t[p].add)%mod;
  22. t[p*2].mul=(t[p*2].mul*t[p].mul)%mod;
  23. t[p*2+1].mul=(t[p*2+1].mul*t[p].mul)%mod;
  24. t[p].mul=1,t[p].add=0;
  25. }
  26. void build_tree(ll p,ll l,ll r)
  27. {
  28. t[p].l=l;
  29. t[p].r=r;
  30. t[p].mul=1;
  31. if(l==r)
  32. {
  33. t[p].sum=a[l]%mod;
  34. return;
  35. }
  36. else
  37. {
  38. ll mid=(l+r)>>1;//基本上是只有建树才会用到mid
  39. build_tree(p*2,l,mid);
  40. build_tree(p*2+1,mid+1,r);
  41. push_up(p);
  42. }
  43. }
  44. void add(ll p,ll l,ll r,ll k)
  45. {
  46. if(l<=t[p].l&&r>=t[p].r)
  47. {
  48. t[p].sum=((t[p].r-t[p].l+1)*k+t[p].sum)%mod;//这里偶尔会写错
  49. t[p].add=(t[p].add+k)%mod;
  50. }
  51. else if(t[p].l>r||t[p].r<l)return;
  52. else
  53. {
  54. push_down(p);
  55. add(p*2,l,r,k);
  56. add(p*2+1,l,r,k);
  57. push_up(p);
  58. }
  59. }
  60. void mul(ll p,ll l,ll r,ll k)
  61. {
  62. if(l<=t[p].l&&r>=t[p].r)
  63. {
  64. t[p].mul=(t[p].mul*k)%mod;
  65. t[p].add=(t[p].add*k)%mod;//直接乘,不能放后面乘
  66. t[p].sum=(t[p].sum*k)%mod;
  67. }
  68. else if(t[p].l>r||t[p].r<l)return;
  69. else
  70. {
  71. push_down(p);
  72. mul(p*2,l,r,k);
  73. mul(p*2+1,l,r,k);
  74. push_up(p);
  75. }
  76. }
  77. ll query(ll p,ll l,ll r)
  78. {
  79. if(l<=t[p].l&&r>=t[p].r)
  80. {
  81. return t[p].sum;
  82. }
  83. else if(t[p].l>r||t[p].r<l)return 0;
  84. else
  85. {
  86. push_down(p);
  87. ll val1=query(p*2,l,r)%mod;
  88. ll val2=query(p*2+1,l,r)%mod;
  89. return (val1+val2)%mod;
  90. }
  91. }
  92. int main()
  93. {
  94. cin>>n>>m>>mod;
  95. for(int i=1;i<=n;i++)cin>>a[i];
  96. build_tree(1,1,n);
  97. for(int i=1;i<=m;i++)
  98. {
  99. int num,x,y,k;
  100. cin>>num>>x>>y;
  101. if(num==1)
  102. {
  103. cin>>k;
  104. mul(1,x,y,k);
  105. }
  106. else if(num==2)
  107. {
  108. cin>>k;
  109. add(1,x,y,k);
  110. }
  111. else
  112. {
  113. cout<<query(1,x,y)%mod<<endl;
  114. }
  115. }
  116. return 0;
  117. }

线段树求区间最大值

(洛谷)I Hate It

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. #define ll long long
  6. #define inf 0x3f3f3f3f
  7. ll a[211111],n,m,mod=inf;
  8. struct Tree
  9. {
  10. ll l,r,add,sum,mx;
  11. }t[844444];//线段树要开4倍空间
  12. inline void push_up(ll p)
  13. {
  14. t[p].sum=(t[p*2].sum+t[p*2+1].sum);
  15. t[p].mx=max(t[p*2].mx,t[p*2+1].mx);//回溯
  16. }
  17. inline void push_down(ll p)
  18. {
  19. t[p*2].sum+=t[p].add*(t[p*2].r-t[p*2].l+1);
  20. t[p*2+1].sum+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
  21. t[p*2].add+=t[p].add;
  22. t[p*2+1].add+=t[p].add;
  23. t[p].add=0;
  24. }
  25. void build_tree(ll p,ll l,ll r)
  26. {
  27. t[p].l=l;
  28. t[p].r=r;
  29. if(l==r)
  30. {
  31. t[p].sum=a[l];
  32. t[p].mx=t[p].sum;//到一个点就取mx
  33. return;
  34. }
  35. else
  36. {
  37. ll mid=(l+r)>>1;
  38. build_tree(p*2,l,mid);
  39. build_tree(p*2+1,mid+1,r);
  40. push_up(p);
  41. }
  42. }
  43. ll querymax(ll p,ll l,ll r)
  44. {
  45. if(t[p].l>=l&&t[p].r<=r)
  46. {
  47. return t[p].mx;
  48. }
  49. else if(t[p].l>r||t[p].r<l)
  50. {
  51. return 0;
  52. }
  53. else
  54. {
  55. push_down(p);
  56. ll mx=max(querymax(p*2,l,r),querymax(p*2+1,l,r));
  57. push_up(p);
  58. return mx;
  59. }
  60. }
  61. void add(ll p,ll l,ll r,ll k)
  62. {
  63. if(t[p].l>=l&&t[p].r<=r)
  64. {
  65. t[p].sum+=k*(t[p].r-t[p].l+1);
  66. t[p].add+=k;
  67. if(l==r)t[p].mx=t[p].sum;//修改单点取mx
  68. }
  69. else if(t[p].l>r||t[p].r<l)
  70. {
  71. return;
  72. }
  73. else
  74. {
  75. push_down(p);
  76. add(p*2,l,r,k);
  77. add(p*2+1,l,r,k);
  78. push_up(p);
  79. }
  80. }
  81. int main()
  82. {
  83. cin>>n>>m;
  84. for(int i=1;i<=n;i++)cin>>a[i];
  85. build_tree(1,1,n);
  86. for(int i=1;i<=m;i++)
  87. {
  88. char c;cin>>c;
  89. int x,y;cin>>x>>y;
  90. if(c=='Q')
  91. {
  92. cout<<querymax(1,x,y)<<endl;
  93. }
  94. else if(c=='U')//根据题目单点修改
  95. {
  96. if(a[x]<y)
  97. {
  98. add(1,x,x,y-a[x]);
  99. a[x]=y;
  100. }
  101. }
  102. }
  103. return 0;
  104. }

(牛客)魔法学院(easy version)(区间修改,lazy标记,思维) 

(牛客提单:线段树)

[JSOI2008]最大数MAXNUMBER(线段树后插入元素)

数据结构(维护平方和)

区区区间(思维+特殊一点的lazy)

(acwing)区间最大子段和(线段树的区间最大子段和问题)(经典)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=555555;
  10. const ll M=55555;
  11. typedef pair<int,int> PII;
  12. int n,m,a[N];
  13. struct T
  14. {
  15. int l,r,sum,lmx,rmx,dat;
  16. }t[N*4];
  17. inline void push_up(T &u,T &l,T &r)
  18. {
  19. u.sum = l.sum + r.sum;
  20. u.lmx = max(l.lmx, l.sum + r.lmx);
  21. u.rmx = max(r.rmx, r.sum + l.rmx);
  22. u.dat = max(max(l.dat, r.dat), l.rmx + r.lmx);
  23. }
  24. inline void push_up(int p)
  25. {
  26. push_up(t[p],t[p*2],t[p*2+1]);
  27. }
  28. void build(int p,int l,int r)
  29. {
  30. t[p].l=l;
  31. t[p].r=r;
  32. if(l==r)
  33. {
  34. t[p]={l,r,a[l],a[l],a[l],a[l]};
  35. return;
  36. }
  37. else
  38. {
  39. int mid=(l+r)>>1;
  40. build(p*2,l,mid);
  41. build(p*2+1,mid+1,r);
  42. push_up(p);
  43. }
  44. }
  45. T query(int p,int l,int r)
  46. {
  47. if(t[p].l>=l&&t[p].r<=r)
  48. {
  49. return t[p];
  50. }
  51. else
  52. {
  53. int mid=(t[p].l+t[p].r)>>1;
  54. if(r<=mid) return query(p*2,l,r);//l,r完全在左边
  55. else if(l>mid) return query(p*2+1,l,r);//完全在右边
  56. else//横跨了中点,此时res= max(tl的最大子段和,tr的最大子段和,跨越区间中点的最大子段和)
  57. { //此时l,r所围成的区间大概率是原树没有的,所以递归不断分割这个区间,直到所有的子区间都能在树中找到,回溯时,因为返回的区间极大概率不是p的子节点
  58. //用L,R来记录他们的信息,通过建立虚拟父节点res并用push_up函数合并区间,更新答案,但push_up操作需要他们的除了l,r的信息,所以query要返回结构体,
  59. auto L=query(p*2,l,r);
  60. auto R=query(p*2+1,l,r);
  61. T res;
  62. push_up(res,L,R);
  63. return res;
  64. }
  65. }
  66. }
  67. void update(int p,int x,int y)
  68. {
  69. if(t[p].l==t[p].r&&t[p].r==x)
  70. {
  71. t[p]={x,x,y,y,y,y};//因为是单点修改,所以全都要改
  72. }
  73. else if(t[p].l>x||t[p].r<x)return;
  74. else
  75. {
  76. update(p*2,x,y);
  77. update(p*2+1,x,y);
  78. push_up(p);
  79. }
  80. }
  81. //考虑由左右两个区间子区间tl,tr,得到当前区间的最大子段和ans,则有ans=max(tl的最大子段和,tr的最大子段和,跨越区间中点的最大子段和)
  82. //而跨越区间中点的最大子段和可用tl的前缀和(rmx)以及tr的后缀和得来(lmx),将这两个信息加到线段树数组内,且动态维护(具体见push_up)
  83. //查询操作较为复杂,可仔细看看
  84. int main()
  85. {
  86. scanf("%d %d",&n,&m);
  87. for(int i=1;i<=n;i++)scanf("%d",a+i);
  88. build(1,1,n);
  89. while(m--)
  90. {
  91. int k,x,y;
  92. scanf("%d %d %d",&k,&x,&y);
  93. if(k==1)
  94. {
  95. if(x>y)swap(x,y);
  96. printf("%d\n",query(1,x,y).dat);
  97. }
  98. else
  99. {
  100. update(1,x,y);
  101. }
  102. }
  103. return 0;
  104. }

扫描线+线段树 求二维平面上的矩阵的总面积

基本思想:(33条消息) 线段树+扫描线(有关扫描线的理解)_sdau_blue的博客-CSDN博客_线段树扫描线

(acwing)亚特兰蒂斯(扫描线+线段树+离散化并去重)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=10100;
  10. const ll M=55555;
  11. typedef pair<int,int> PII;
  12. int T=1,n;
  13. vector<double>ys;//离散化的数组
  14. struct segment//存储线段信息
  15. {
  16. double x,y1,y2;
  17. int d;
  18. bool operator<(const segment&t)
  19. {
  20. return x<t.x;
  21. }
  22. }seg[N*2];//一个矩阵有两条线段
  23. //因为要动态维护线段信息,所以线段树的每个节点,保存的为线段,0号点保存的是ys[0]~ys[1],(离散化后的,即ys数组上的序号为0和序号为1的点)以此类推
  24. struct node
  25. {
  26. int l,r;//[l,r]不是线段的范围,是该节点的孩子的范围,建树中体现
  27. int cnt;//记录这段区间出现次数
  28. double len;//区间长度
  29. }t[N*2*4];//一个矩阵有两条线段,再*4
  30. //此题为经典题型:扫描线+线段树解决二维平面的矩形总面积
  31. //首先输入并存线段信息到seg数组,然后离散化并去重 y值,(不然有无穷多的点),得到y值范围后建树,将seg按x值排序,然后在线段树上用扫描线算法,并动态维护树,记录答案
  32. void build(int p,int l,int r)
  33. {
  34. t[p].l=l,t[p].r=r;
  35. if(t[p].l==t[p].r)return;//忘写这个就一直递归下去了
  36. int mid=(l+r)>>1;
  37. build(p*2,l,mid);
  38. build(p*2+1,mid+1,r);
  39. }
  40. int find(double x)
  41. {
  42. return lower_bound(ys.begin(),ys.end(),x)-ys.begin();//返回x在ys中的序号
  43. }
  44. void pushup(int p)
  45. {
  46. //全覆盖
  47. 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
  48. else if(t[p].l!=t[p].r)//不是叶子节点,len可由子节点更新
  49. {
  50. t[p].len=t[p*2].len+t[p*2+1].len;
  51. }
  52. else t[p].len=0;//没有被覆盖
  53. //补充:第一种情况,是被一次性完全覆盖,而第二种情况也有可能被完全覆盖,但是分次的,比如之前有线段覆盖其的子节点,然后这次通过update的else语句进入其剩下子节点
  54. //覆盖完其剩下子节点后回溯回来,进行pushup时,虽然cnt=0,但已经完全被覆盖了。
  55. }
  56. void update(int p,int l,int r,int d)
  57. {
  58. if(t[p].l>=l&&t[p].r<=r)
  59. {
  60. t[p].cnt+=d;
  61. pushup(p);//更新自己的len,否则不能更新父亲的len
  62. }
  63. else if(t[p].l>r||t[p].r<l)return;
  64. else
  65. {
  66. update(p*2,l,r,d);
  67. update(p*2+1,l,r,d);
  68. pushup(p);
  69. }
  70. }
  71. int main()
  72. {
  73. while(scanf("%d",&n),n)
  74. {
  75. ys.clear();
  76. int j=0;
  77. for(int i=0;i<n;i++)
  78. {
  79. double x1,y1,x2,y2;
  80. scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
  81. seg[j++]={x1,y1,y2,1};
  82. seg[j++]={x2,y1,y2,-1};
  83. ys.push_back(y1);ys.push_back(y2);
  84. }
  85. sort(seg,seg+j);//按x轴排序
  86. sort(ys.begin(),ys.end());//离散化并去重
  87. ys.erase(unique(ys.begin(),ys.end()),ys.end());
  88. build(1,0,ys.size()-2);//因为从0开始,所以-1,又因为线段树节点信息保存的是线段,即t[0]为ys[0]~ys[1]的线段信息,所以建树的范围再-1
  89. double res=0;
  90. for(int i=0;i<j;i++)
  91. {
  92. //根节点的长度即为此时有效线段长度 ,再 * x轴长度即为面积
  93. if(i>0)
  94. res+=t[1].len*(seg[i].x-seg[i-1].x);
  95. 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)]]的线段的节点的编号
  96. }
  97. printf("Test case #%d\n",T++);
  98. printf("Total explored area: %.2lf\n\n",res);
  99. }
  100. return 0;
  101. }

树状数组

树状数组基本函数的原理:【算法讲堂】【电子科技大学】【ACM】树状数组与ST表_哔哩哔哩_bilibili

(acwing)楼兰图腾(单点修改+区间求和)(模板)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=30;
  10. const ll M=111111;
  11. typedef pair<int,int> PII;
  12. int n,a[N],t[N],Greater[N],Lower[N];
  13. ll res1,res2;
  14. int lowbit(int x)
  15. {
  16. return x & -x;
  17. }
  18. int sum(int x)
  19. {
  20. int res=0;
  21. for(int i=x;i;i-=lowbit(i))
  22. {
  23. res+=t[i];
  24. }
  25. return res;
  26. }
  27. void add(int x,int c)
  28. {
  29. for(int i=x;i<=n;i+=lowbit(i))
  30. {
  31. t[i]+=c;
  32. }
  33. }
  34. //思路:枚举每一个点作为中间点,求其左边和右边大于(小于)它的点的数量并相乘,将答案累加,即为第一问和第二问答案
  35. //以第一问为例,枚举点的时候维护其左边大于它的点的数量 可正向扫描,因为输入为1~n的排列,可用一个数组t[i]来维护值为i的点的数量,再求前缀和,则sum(n)则为此时统计的点的数量
  36. //sum(a[i])则为值为1~a[i]的点的数量,sum(n)-sum(a[i])则为左边大于它的点的数量(区间求和),因为同时要维护 t数组,要单点修改,,考虑到只是要实现区间求和和单点修改,可用树状数组
  37. int main()
  38. {
  39. cin>>n;
  40. for(int i=1;i<=n;i++)cin>>a[i];//数组为1~n的排序
  41. for(int i=1;i<=n;i++)
  42. {
  43. int y=a[i];
  44. Greater[i]=sum(n)-sum(y);
  45. Lower[i]=sum(y-1);//比y小的点的数量
  46. add(y,1);
  47. }
  48. memset(t,0,sizeof t);//0
  49. for(int i=n;i>=1;i--)//反向扫描,维护右边比y大和右边比y小的点的数量
  50. {
  51. int y=a[i];
  52. res1+=Greater[i]*(ll)(sum(n)-sum(y));
  53. res2+=Lower[i]*(ll)(sum(y-1));
  54. add(y,1);
  55. }
  56. cout<<res1<<" "<<res2;
  57. return 0;
  58. }

(acwing)谜一样的牛(思维+求前缀和+单点修改)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=101000;
  10. const ll M=55555;
  11. typedef pair<int,int> PII;
  12. int n,a[N],t[N],ans[N];
  13. int lowbit(int x)
  14. {
  15. return x & -x;
  16. }
  17. void add(int x,int c)
  18. {
  19. for(int i=x;i<=n;i+=lowbit(i))
  20. {
  21. t[i]+=c;
  22. }
  23. }
  24. int sum(int x)
  25. {
  26. ll ans=0;
  27. for(int i=x;i;i-=lowbit(i))ans+=t[i];
  28. return ans;
  29. }
  30. //思路:
  31. //首先身高为1~n的排序
  32. //模拟一遍发现,反向扫描,发现ax的身高=前面未没有被选到的身高值(因为被选到的就是在x后面的,而ax表示x前比x身高矮的牛的个数)中排名第x的数字的后一位
  33. //x[i]表示身高为i的值的情况0表示被占用,1表示未被占用,可用数组S(假设)作x[i]的前缀和,则S[i]可表示前i位中,未被占用的身高值的个数,采用二分答案,找到未被占用的身高值的个数>=a[i]+1 的最小值
  34. //动态维护,选了这个数字就删掉这个数字(减去1
  35. //维护前缀和(区间和),单点修改,可用树状数组
  36. int main()
  37. {
  38. memset(ans,0x3f,sizeof ans);
  39. scanf("%d",&n);
  40. for(int i=2;i<=n;i++)
  41. {
  42. scanf("%d",a+i);
  43. }
  44. for(int i=1;i<=n;i++)t[i]=lowbit(i);//初始化
  45. for(int i=n;i;i--)//反向扫描
  46. {
  47. int l=1,r=n;
  48. while(l<=r)
  49. {
  50. int mid=(l+r)/2;
  51. if(sum(mid)>=a[i]+1)//前缀和求前i位中,未被占用的身高值的个数>=a[i]+1的最小值
  52. {
  53. r=mid-1;
  54. ans[i]=min(ans[i],mid);
  55. }
  56. else l=mid+1;
  57. }
  58. add(ans[i],-1);//将这个身高值删除
  59. }
  60. for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
  61. return 0;
  62. }

树状数组2(模板)(差分数组)(求单点值、区间修改)

(acwing)一个简单的整数问题

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=111000;
  10. const ll M=111111;
  11. typedef pair<int,int> PII;
  12. int n,m;
  13. ll t[N],a[N];
  14. ll lowbit(int x)
  15. {
  16. return x&-x;
  17. }
  18. void add(int x,int c)
  19. {
  20. for(int i=x;i<=n;i+=lowbit(i))
  21. {
  22. t[i]+=c;
  23. }
  24. }
  25. ll sum(int x)
  26. {
  27. ll res=0;
  28. for(int i=x;i;i-=lowbit(i))
  29. {
  30. res+=t[i];
  31. }
  32. return res;
  33. }
  34. int main()
  35. {
  36. cin>>n>>m;
  37. for(int i=1;i<=n;i++)
  38. {
  39. cin>>a[i];
  40. add(i,a[i]-a[i-1]);//构建差分数组
  41. }
  42. while(m--)
  43. {
  44. char flag;
  45. cin>>flag;
  46. if(flag=='C')
  47. {
  48. int l,r,d;
  49. cin>>l>>r>>d;
  50. add(l,d);add(r+1,-d);//区间修改
  51. }
  52. else
  53. {
  54. int x;
  55. cin>>x;
  56. cout<<sum(x)<<endl;//查询单点,因为差分数组,所以单点值=其前缀和
  57. }
  58. }
  59. return 0;
  60. }

(acwing)一个简单的整数问题2(树状数组实现区间修改,区间求和)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=101000;
  10. const ll M=55555;
  11. typedef pair<int,int> PII;
  12. int n,m;
  13. ll a[N],t1[N],t2[N];
  14. int lowbit(int x)
  15. {
  16. return x&-x;
  17. }
  18. void add(ll t[],int x,ll c)
  19. {
  20. for(int i=x;i<=n;i+=lowbit(i))
  21. {
  22. t[i]+=c;
  23. }
  24. }
  25. ll sum(ll t[],int x)
  26. {
  27. ll ans=0;
  28. for(int i=x;i;i-=lowbit(i))
  29. {
  30. ans+=t[i];
  31. }
  32. return ans;
  33. }
  34. ll cal(ll x)
  35. {
  36. return sum(t1,x)*(x+1)-sum(t2,x);
  37. }
  38. //区间修改,则使用差分数组
  39. //求差分数组的前缀和
  40. //a1:b1
  41. //a2:b1 b2
  42. //a3:b1 b2 b3
  43. //a4:b1 b2 b3 b4
  44. //a5:b1 b2 b3 b4 b5
  45. //...
  46. //差分数组中单点值ax=b1+...+bx
  47. //a的前缀和=a1+...+ax = x*b1+(x-1)*b2+...+bx
  48. //为了更简洁 ,补齐图形
  49. // b1 b2 b3 b4 b5(另加的一行)
  50. //a1:b1 b2 b3 b4 b5
  51. //a2:b1 b2 b3 b4 b5
  52. //a3:b1 b2 b3 b4 b5
  53. //a4:b1 b2 b3 b4 b5
  54. //a5:b1 b2 b3 b4 b5
  55. //则ax的前缀和= (b1+b2+..bx)*(x+1) - (b1+2*b2+...+x*bx);(就是整个表的b加起来减掉补齐的那一部分)
  56. //根据上式,用t1维护bi前缀和,用t2维护i*bi前缀和
  57. int main()
  58. {
  59. scanf("%d%d",&n,&m);
  60. for(int i=1;i<=n;i++)scanf("%lld",a+i);
  61. for(int i=1;i<=n;i++)
  62. {
  63. add(t1,i,a[i]-a[i-1]);//构建差分数组
  64. add(t2,i,(ll)i*(a[i]-a[i-1]));
  65. }
  66. while(m--)
  67. {
  68. char op[2];
  69. int l,r,d;
  70. scanf("%s",op);//不会接受到回车和空格
  71. if(op[0]=='C')
  72. {
  73. scanf("%d%d%d",&l,&r,&d);
  74. add(t1,l,d);add(t1,r+1,-d);
  75. add(t2,l,l*d);add(t2,r+1,(r+1)*(-d));
  76. }
  77. else
  78. {
  79. scanf("%d%d",&l,&r);
  80. printf("%lld\n",cal(r)-cal(l-1));
  81. }
  82. }
  83. return 0;
  84. }

线段树可实现树状数组所有功能(单点修改,区间修改,求单点值,求区间和)但线段树代码较长,空间较大,速度会比树状数组满一个常数

图论—————————————————————————————————————————

图论杂题:

(洛谷)信息传递(最小环)

拓扑排序 要求 1:有向无环图 2:每个点不重复 

算法步骤:1.统计所有节点的入度,将入度为0的节点入队列 2.将这个节点指向的节点的入度减1若该点入度减为0,再入度,直到所有的节点都分离出来 3.统计已分离的节点个数,若==节点总数,则该排序正确,否则说明有环,无解

图例:

(洛谷)最大食物链计数(正常一点的拓扑)

  1. #include<iostream>
  2. #include<algorithm>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. #define mod 80112002
  7. int n,m,in[510000],out[510000],mar;
  8. long long num[510000],ans;
  9. vector<int>v[520000];
  10. void topo()
  11. {
  12. queue<int>q;
  13. for(int i=1;i<=n;i++)
  14. {
  15. if(in[i]==0)
  16. {
  17. q.push(i);
  18. num[i]=1;
  19. }
  20. }
  21. while(q.size())
  22. {
  23. int x=q.front();q.pop();
  24. for(int i=0;i<v[x].size();i++)
  25. {
  26. int y=v[x][i];
  27. num[y]=(num[y]+num[x])%mod;
  28. if(--in[y]==0)
  29. {
  30. if(out[y]==0)//最佳生产者不止一个
  31. ans=(num[y]+ans)%mod;
  32. q.push(y);
  33. }
  34. }
  35. }
  36. }
  37. int main()//题意:找到图中所有 左端点入度为0 且 右端点出度为0 的路径的数量
  38. {
  39. scanf("%d %d",&n,&m);
  40. for(int i=1;i<=m;i++)
  41. {
  42. int a,b;
  43. scanf("%d %d",&a,&b);
  44. v[a].push_back(b);
  45. in[b]++;
  46. out[a]++;//记录出度,出度为0即为最佳生产者
  47. }
  48. topo();
  49. cout<<ans%mod;
  50. return 0;
  51. }

(牛客)菜肴制作(反向建图,拓扑排序,反向输出)

如果用一个小根堆来维护拓扑的话显然是会不行的,因为这样求出来的是字典序最小的拓扑序,并不一定是1尽可能在前,因为字典序是贪心的,如果前面的一位能小就尽可能的小,并不保证1出现尽量靠前,,但是如果建一个反图,求一个反向字典序最大的拓扑序呢,那么就会有大的数尽量靠前的情况出现,于是交小的数尽量靠后,于是反过来就是小的数尽量靠前了,于是反着建图+一个大根堆维护就好了

  1. 因为1号菜肴在满足所有限制下要尽量优先制作,23号同理
  2. 需要反向建图,做字典序最大的拓扑排序,反向输出答案
  3. #include <iostream>
  4. #include <queue>
  5. #include <vector>
  6. #include <algorithm>
  7. using namespace std;
  8. int in[100007],tt,n,m,x,y;
  9. vector<int>v[100007],ans;//用邻接矩阵存邻接点(topo就用这个)
  10. bool topo()
  11. {
  12. ans.clear();
  13. priority_queue<int>q;//大根堆,即堆顶为字典序最大的数
  14. for(int i=1;i<=n;i++)
  15. {
  16. if(in[i]==0)//将没有前驱即入度为0的点入队
  17. {
  18. q.push(i);
  19. }
  20. }
  21. while(q.size())
  22. {
  23. int t=q.top();q.pop();
  24. ans.push_back(t);
  25. for(int i=0;i<v[t].size();i++)//删除该点的所有邻接点和它们之间的弧
  26. {
  27. if(--in[v[t][i]]==0)//如果删了该弧,该邻接点入度为0
  28. q.push(v[t][i]);//将该邻接点入队,这里之前写错成q.push(i)
  29. }
  30. }
  31. if(ans.size()==n)return true;
  32. else return false;
  33. }
  34. int main()
  35. {
  36. cin>>tt;
  37. for(int i=0;i<tt;i++)
  38. {
  39. cin>>n>>m;
  40. for(int i=1;i<=n;i++)
  41. {
  42. v[i].clear();//初始化存放以该点为尾的弧的顶点//这里之前忘记写
  43. in[i]=0;//初始化该点入度为0
  44. }
  45. for(int i=1;i<=m;i++)
  46. {
  47. cin>>x>>y;
  48. swap(x,y);//反向建图(普通拓扑可忽略)
  49. v[x].push_back(y);//记录以该点为尾的弧的顶点
  50. in[y]++;//入度
  51. }
  52. if(topo())
  53. {
  54. for(int i=ans.size()-1;i>=0;i--)
  55. {
  56. cout<<ans[i]<<" ";
  57. }
  58. cout<<endl;
  59. }
  60. else cout<<"Impossible!"<<endl;
  61. }
  62. return 0;
  63. }
  64. 1,3 1,4
  65. 2,3,4

(洛谷)杂物(拓扑排序+dp)

(洛谷)神经网络(拓扑排序+dp)

spfa最短路(可求最短路,但容易tle,一般只用于存在负权边的最短路或最长路和判断是否存在正、负环) 

(洛谷p3385)第一种方法o(n^2),相较于第二种方法,慢,但判断负环同时,能顺便求出s点的单源最短路径

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define inf 0x3f3f3f3f
  4. #define ll long long
  5. const ll mod =1e9+7;
  6. #define ull unsigned long long
  7. int n,t,m,head[2222],cnt,e[2222],dis[2222];
  8. bool vis[2222];
  9. struct EDGE
  10. {
  11. int x,y,w,neaxty;
  12. }edge[6666];
  13. void addedge(int x,int y,int w)
  14. {
  15. edge[++cnt].x=x;
  16. edge[cnt].y=y;
  17. edge[cnt].w=w;
  18. edge[cnt].neaxty=head[x];
  19. head[x]=cnt;
  20. }
  21. bool spfa()
  22. {
  23. memset(dis,0x3f,sizeof dis);
  24. dis[1]=0;
  25. queue<int>q;
  26. q.push(1);vis[1]=1;
  27. while(q.size())
  28. {
  29. int x=q.front();
  30. q.pop();vis[x]=0;//出队
  31. for(int i=head[x];i;i=edge[i].neaxty)
  32. {
  33. int y=edge[i].y;
  34. int w=edge[i].w;
  35. if(dis[y]>dis[x]+w)
  36. {
  37. dis[y]=dis[x]+w;
  38. e[y]=e[x]+1;
  39. if(e[y]>n)return 1;
  40. if(!vis[y])//还没入队
  41. {
  42. q.push(y);
  43. vis[y]=1;//入队
  44. }
  45. }
  46. }
  47. }
  48. return 0;
  49. }
  50. int main()
  51. {
  52. scanf("%d",&t);
  53. while(t--)
  54. {
  55. memset(head,0,sizeof head);
  56. memset(e,0,sizeof e);
  57. memset(vis,0,sizeof vis);
  58. cnt=0;
  59. scanf("%d %d",&n,&m);
  60. for(int i=1;i<=m;i++)
  61. {
  62. int x,y,w;
  63. scanf("%d %d %d",&x,&y,&w);
  64. if(w>=0)
  65. {
  66. addedge(x,y,w);
  67. addedge(y,x,w);
  68. }
  69. else addedge(x,y,w);
  70. }
  71. if(spfa())printf("YES\n");
  72. else printf("NO\n");
  73. }
  74. return 0;
  75. }

(acwing)虫洞 (第二种方法o(n) ),只能判断是否存在负环,不能维护单源最短路

  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <queue>
  5. #include <stack>
  6. #include <vector>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. using namespace std;
  14. #define LL __int128
  15. #define ll long long
  16. #define ull unsigned long long
  17. const int imax=1e9;
  18. const ll lmax=2e18;
  19. const ll mod =1e9+7;
  20. const ll N=600;
  21. const ll M=11111;
  22. int t,n,m1,m2,cnt,head[N];
  23. int e[N],dis[N];//e[]统计每个点的最短路径所包含边数,若>=n,即存在负环
  24. bool vis[N];
  25. struct EDGE
  26. {
  27. int x,y,w,neaxty;
  28. }edge[M];
  29. void addedge(int x,int y,int w)
  30. {
  31. edge[++cnt].x=x;
  32. edge[cnt].y=y;
  33. edge[cnt].w=w;
  34. edge[cnt].neaxty=head[x];
  35. head[x]=cnt;
  36. }
  37. bool spfa()
  38. {
  39. memset(vis,0,sizeof vis);
  40. memset(dis,0,sizeof dis);//初始距离设为0,其实没关系,因为只有负环会到达负无穷
  41. memset(e,0,sizeof e);
  42. queue<int>q;
  43. for(int i=1;i<=n;i++)//将所有点入队
  44. {
  45. q.push(i);
  46. vis[i]=1;
  47. }
  48. while(q.size())
  49. {
  50. int x=q.front();q.pop();vis[x]=0;
  51. for(int i=head[x];i;i=edge[i].neaxty)
  52. {
  53. int y=edge[i].y;
  54. if(dis[y]>dis[x]+edge[i].w)
  55. {
  56. dis[y]=dis[x]+edge[i].w;
  57. e[y]=e[x]+1;//更新该点的最短路所包含的边数
  58. if(!vis[y])
  59. {
  60. q.push(y);
  61. vis[y]=1;
  62. }
  63. if(e[y]>=n)return true;
  64. }
  65. }
  66. }
  67. return false;
  68. }
  69. //现在农夫约翰希望能够从农场中的某片田地出发,经过一些路径和虫洞回到过去,并在他的出发时刻之前赶到他的出发地。
  70. //存在负环即可,因为它可以从任意一片田地出发,可直接从负环出发
  71. int main()
  72. {
  73. cin>>t;
  74. while(t--)
  75. {
  76. cin>>n>>m1>>m2;
  77. memset(head,0,sizeof head);
  78. cnt=0;
  79. while(m1--)
  80. {
  81. int x,y,w;
  82. cin>>x>>y>>w;
  83. addedge(x,y,w);//按题意,双向边
  84. addedge(y,x,w);
  85. }
  86. while(m2--)
  87. {
  88. int x,y,w;
  89. cin>>x>>y>>w;//按题意,负边
  90. w*=-1;
  91. addedge(x,y,w);
  92. }
  93. if(spfa())puts("YES");
  94. else puts("NO");
  95. }
  96. return 0;
  97. }

(acwing)观光奶牛(01分数规划+判断正环)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=1100;
  10. const ll M=11111;
  11. int t,n,m,cnt,head[N];
  12. int e[N],W[N];//W为点权,e为统计该点的边的数量
  13. double dis[N];
  14. bool vis[N];
  15. struct EDGE
  16. {
  17. int x,y,w,neaxty;
  18. }edge[M];
  19. void addedge(int x,int y,int w)
  20. {
  21. edge[++cnt].x=x;
  22. edge[cnt].y=y;
  23. edge[cnt].w=w;
  24. edge[cnt].neaxty=head[x];
  25. head[x]=cnt;
  26. }
  27. bool check(double mid)
  28. {
  29. memset(vis,0,sizeof vis);
  30. memset(dis,0,sizeof dis);
  31. memset(e,0,sizeof e);
  32. queue<int>q;
  33. for(int i=1;i<=n;i++)
  34. {
  35. q.push(i);
  36. vis[i]=1;
  37. }
  38. while(q.size())
  39. {
  40. int x=q.front();q.pop();vis[x]=0;
  41. for(int i=head[x];i;i=edge[i].neaxty)
  42. {
  43. int y=edge[i].y;
  44. if(dis[y]<dis[x]+W[x]-mid*edge[i].w)//将点权带入边权计算,spfa常常可以这么用
  45. {
  46. dis[y]=dis[x]+W[x]-mid*edge[i].w;
  47. e[y]=e[x]+1;//更新边数
  48. if(e[y]>=n)return true;
  49. if(!vis[y])
  50. {
  51. q.push(y);
  52. vis[y]=1;
  53. }
  54. }
  55. }
  56. }
  57. return false;
  58. }
  59. int main()
  60. {
  61. cin>>n>>m;
  62. for(int i=1;i<=n;i++)cin>>W[i];
  63. for(int i=1;i<=m;i++)
  64. {
  65. int x,y,w;
  66. cin>>x>>y>>w;
  67. addedge(x,y,w);
  68. }
  69. //因为求(和f/和i)最大值,为01分数规划 ,采用二分答案
  70. //则(和f/和t)>mid->和f-和t*mid>0->和(f-t*mid)>0,对于点权f[i],我们将它附在出边上,如果重新定义每个边的权值为f-t*mid,那么问题就转化为判断图中是否存在正环,spfa求正环可以对一个环求最长路,若某点最长路所含边数>=n即存在正环
  71. double l=0,r=1010;//上限为1000*1000/1000=1000
  72. while(r-l>1e-4)//一般保留n位小数,就是1e-(n+2)**
  73. {
  74. double mid=(l+r)/2;
  75. if(check(mid))l=mid;
  76. else r=mid;
  77. }
  78. printf("%.2lf",l);
  79. return 0;
  80. }

(acwing)单词环(01分数规划+思维+spfa判断正环+栈优化)

栈优化:若用队列,遇到正/负环则更新一次又将元素放到队尾,直到遍历完整个队列才去算他),用栈遇到正/负环,则在队尾反复更新,当e>n则返回 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=700;
  10. const ll M=111111;
  11. int t,n,m,cnt,head[N];
  12. int e[N],s[N],top;
  13. double dis[N];
  14. bool vis[N];
  15. struct EDGE
  16. {
  17. int x,y,w,neaxty;
  18. }edge[M];
  19. void addedge(int x,int y,int w)
  20. {
  21. edge[++cnt].x=x;
  22. edge[cnt].y=y;
  23. edge[cnt].w=w;
  24. edge[cnt].neaxty=head[x];
  25. head[x]=cnt;
  26. }
  27. bool check(double mid)
  28. {
  29. memset(vis,0,sizeof vis);
  30. memset(dis,0,sizeof dis);
  31. memset(e,0,sizeof e);
  32. top=0;
  33. for(int i=0;i<676;i++)//26*26,一共676个点
  34. {
  35. s[++top]=i;//stl的栈会被卡掉
  36. vis[i]=1;
  37. }
  38. int count=0;
  39. while(top>0)
  40. {
  41. int x=s[top--];vis[x]=0;
  42. for(int i=head[x];i;i=edge[i].neaxty)
  43. {
  44. int y=edge[i].y;
  45. if(dis[y]<dis[x]+edge[i].w-mid)
  46. {
  47. dis[y]=dis[x]+edge[i].w-mid;
  48. e[y]=e[x]+1;//更新边数
  49. // if(++count>=3*N)return true;//玄学,如果循环超过2*点的数量,一般返回正数
  50. if(e[y]>=N)return true;//题目中的n表示的不是点数
  51. if(!vis[y])
  52. {
  53. s[++top]=y;
  54. vis[y]=1;
  55. }
  56. }
  57. }
  58. }
  59. return false;
  60. }
  61. int main()
  62. {
  63. while(cin>>n)
  64. {
  65. if(n==0)return 0;
  66. memset(head,0,sizeof head);
  67. cnt=0;
  68. string str;
  69. for(int i=1;i<=n;i++)
  70. {
  71. cin>>str;
  72. if(str.size()<2)continue;
  73. int a=(str[0]-'a')*26+str[1]-'a';
  74. int b=(str[str.size()-2]-'a')*26+str[str.size()-1]-'a';
  75. addedge(a,b,str.size());//建图方法:将一个字符串看成字符串前两个数向字符串后两个数连一条长度为len的边 ,则图最多有26*26个点,n条边
  76. }
  77. //由题,求(和长度/和边数)最大值,为01分数规划,采用二分答案
  78. //(和长度/和边数)>mid,和长度-mid*和边数>0,和(长度-mid)>0,所以以长度-mid作为边权,求图是否存在正环,判断正环,用最长路
  79. if(!check(0))puts("No solution");
  80. else
  81. {
  82. double l=0,r=1000;//上限为1000*1000/1000
  83. while(r-l>1e-4)
  84. {
  85. double mid=(l+r)/2;
  86. if(check(mid))l=mid;
  87. else r=mid;
  88. }
  89. printf("%lf\n",r);
  90. }
  91. }
  92. return 0;
  93. }

迪杰斯特拉

时间复杂度:O((n+m)logn)

(洛谷)单源最短路径(弱化版)(迪杰斯特拉算法+堆优化+链式前向星)

单源最短路是指单个起点到所有点的最短距离,不是start到end的最短距离,参考(牛客)旅行

有关链式前向星 

根据上图易知 链式前向星存边 的特性: 存边顺序和搜索出来的是反着的,比如存第i个结点存1 2 3序号的边,搜第i个结点的边时,搜出来的顺序是3 2 1

 有关迪杰斯特拉 (该图和该模板题为有向图,若无向图要建两次边)

且迪杰斯特拉不允许有负权边,有负权边用spfa

链式前向星的插入不同于邻接表,插入从头插,H再重新指向新元素 

  1. 链式前向星:本质上为邻接表,但是由于邻接表多用vector且vector过度封装,所以链式前向星会快,前向星用来存一个顶点的所有出度边的信息(edge)
  2. 迪杰斯特拉算法1.建图(前向星) 2.每次选择距离家最短的一个点并剔除该点(vis[u]=false),然后用这个点的距离更新其他相邻点到家的距离,
  3. 如果比当前的点小,则更新节点的值(优先队列)
  4. #include <iostream>
  5. #include <queue>
  6. using namespace std;
  7. #define ll long long
  8. #define maxn 0x7fffffff//最大的数
  9. int n,m,s,x,y,z,cnt,head[600000];//head[u]存放顶点u的出度边的最后一条的”边序号(cnt)”
  10. long long dis[600000];//存放到起点的暂时最短距离
  11. bool vis[600000];//该点是否访问过
  12. inline int read()//快读******
  13. {
  14. int a=0,b=1;
  15. char ch=getchar();
  16. while(ch<'0'||ch>'9')
  17. {
  18. if(ch=='-')b=-1;
  19. ch=getchar();
  20. }
  21. while(ch>='0'&&ch<='9')
  22. {
  23. a=(a<<3)+(a<<1)+(ch^48);//之前写成了+=,,而且三个位运算都要加括号,且>>是除,<<是乘
  24. ch=getchar();
  25. }
  26. return a*b;
  27. }
  28. struct Edge//前向星存边
  29. {
  30. int u,v,w,nexty;
  31. }edge[600000];
  32. struct node//该结构体仅仅用来维护优先队列
  33. //now记录顶点(弧尾),不然从优先队列里取出来后不知道是哪个顶点,存储weight的作用只在于优先队列的排序
  34. {
  35. int now,weight;
  36. inline bool operator<(const node &x)const
  37. {
  38. return weight>x.weight;
  39. }
  40. };
  41. inline void addedge(int x,int y,int z)//加边
  42. {
  43. edge[++cnt].u=x;
  44. edge[cnt].v=y;
  45. edge[cnt].w=z;
  46. edge[cnt].nexty=head[x];
  47. head[x]=cnt;
  48. return;
  49. }
  50. void dijkstra()
  51. {
  52. for(int i=1;i<=n;i++)
  53. {
  54. dis[i]=maxn;
  55. }
  56. dis[s]=0;//vis[s]=true;不能写这个
  57. priority_queue<node>q;
  58. q.push({s,0});
  59. while(!q.empty())
  60. {
  61. int u=q.top().now;q.pop();
  62. if(vis[u])continue;
  63. vis[u]=1;
  64. for(int i=head[u];i;i=edge[i].nexty)//更新所有以该点为尾的边的权值
  65. {
  66. int v=edge[i].v;
  67. if(dis[v]>dis[u]+edge[i].w)//注意这里是edge[i].w,不是dis[v]
  68. {
  69. dis[v]=dis[u]+edge[i].w;
  70. q.push({v,dis[v]});
  71. }
  72. }
  73. }
  74. }
  75. int main()
  76. {
  77. n=read(),m=read(),s=read();
  78. for(int i=1;i<=m;i++)//建图
  79. {
  80. x=read(),y=read(),z=read();
  81. addedge(x,y,z);
  82. }
  83. dijkstra();
  84. for(int i=1;i<=n;i++)
  85. printf("%lld ",dis[i]);
  86. return 0;
  87. }

若每条边权值相等,最短路径=从起点开始bfs广搜到某点的层数*边权值 

eg.(洛谷)寻找道路 (前向星+反向建图+思维*)

(牛客)旅行(思维+维护最大和次大值+dj)   

(洛谷)邮递员送信(有向图内,多个点到一个点的距离=反向建图+该点的单源最短路之和)

(天梯赛) L2-001 紧急救援 (对dj的理解:是从s->t一个一个点更新的,不会跳过某个点)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=1e6+10;
  10. const ll M=2e5 + 10;
  11. typedef pair<int,int> PII;
  12. ll head[N],cnt,num[N],pre[N],dp1[N],dp2[N];
  13. ll n,m,s,d,dis[N];
  14. bool vis[N];
  15. struct EDGE
  16. {
  17. ll x,y,w,neaxty;
  18. }edge[N];
  19. struct NODE
  20. {
  21. ll num,w;
  22. bool operator<(const NODE&x)const
  23. {
  24. return w>x.w;
  25. }
  26. };
  27. void addedge(int x,int y,int w)
  28. {
  29. edge[++cnt].x = x;
  30. edge[cnt].y = y;
  31. edge[cnt].w = w;
  32. edge[cnt].neaxty = head[x];
  33. head[x] = cnt;
  34. }
  35. void dj()
  36. {
  37. memset(dis,0x3f,sizeof dis);
  38. priority_queue<NODE>q;
  39. q.push({s,0});
  40. dis[s]=0;
  41. dp1[s]=1; //记录每个点到起点的最短路径的条数
  42. dp2[s]=num[s]; //起点到每个点的救援队的数量
  43. while(q.size())
  44. {
  45. int x= q.top().num;
  46. q.pop();
  47. if(vis[x])
  48. continue;
  49. vis[x]=1;
  50. for(int i=head[x];i;i=edge[i].neaxty)
  51. {
  52. int y = edge[i].y;
  53. int tem = dp2[x] + num[y];
  54. if(dis[y]>dis[x]+edge[i].w)
  55. {
  56. dis[y] = dis[x] + edge[i].w;
  57. pre[y] = x;//记录前驱点,到时候便可以记录整条路径(之前想过会不会漏掉某个点,但是dj是一个一步脚印,不会跨过某个点)
  58. dp1[y] = dp1[x];
  59. dp2[y] = dp2[x] + num[y];
  60. q.push({y,dis[y]});
  61. }
  62. else if(dis[y] == dis[x]+edge[i].w)
  63. {
  64. dp1[y] = dp1[x]+dp1[y]; //多加一次dp1[x]
  65. if(tem>dp2[y])
  66. {
  67. dp2[y] = tem;
  68. pre[y] = x;
  69. }
  70. }
  71. }
  72. }
  73. }
  74. int main()
  75. {
  76. cin>>n>>m>>s>>d;
  77. for(int i=0;i<n;i++)cin>>num[i];//救援人数
  78. for(int i=1;i<=m;i++)
  79. {
  80. int x,y,w;
  81. cin>>x>>y>>w;
  82. addedge(x,y,w);//双向边
  83. addedge(y,x,w);
  84. }
  85. dj();
  86. ll ans1=dp1[d],ans2=dp2[d],las=d;
  87. int tmp[600],tmp_cnt=0;
  88. while(las!=s) //之前是to_string 然后reserve,个位数还行,但若有数>9 则个位和十位会反 ,eg 12 -> 21
  89. {
  90. tmp[++tmp_cnt] = las;
  91. las = pre[las];
  92. }
  93. //ans2 += num[s];
  94. cout<<ans1<<" "<<ans2<<endl;
  95. for(int i=tmp_cnt;i>=1;i--)
  96. {
  97. if(i!=tmp_cnt)
  98. cout<<" ";
  99. cout<<tmp[i];
  100. }
  101. return 0;
  102. }

分层图

(分层图)***(牛客)小雨坐地铁

图解:

---------------------------------------------------------------------------------------------------------------------------------

floyd算法(求每一对顶点间的最短路径)

  1. for(k=1;k<=n;k++)
  2. for(i=1;i<=n;i++)
  3. for(j=1;j<=n;j++)
  4. if(e[i][j]>e[i][k]+e[k][j])
  5. e[i][j]=e[i][k]+e[k][j];

(洛谷)灾后重建

  1. floyd思想:最开始只允许经过1号顶点进行中转,接下来只允许经过12号顶点进行中转……允许经过1~n号所有顶点进行中转,
  2. 求任意两点之间的最短路程。用一句话概括就是:从i号顶点到j号顶点只经过前k号点的最短路程
  3. 题意:所有的边全部给出,按照时间顺序更新每一个可用的点(即修建好村庄),
  4. 对于每个时间点进行两点之间询问,求对于目前建设的所有村庄来说任意两点之间的最短路
  5. #include <iostream>
  6. #include <cstring>
  7. #include <stdlib.h>
  8. using namespace std;
  9. #define maxn 1e9//这里用0x7fffffff会爆负数
  10. int G[201][201],n,m,t[201],Q,now;
  11. inline void update(int x)
  12. {
  13. for(int i=0;i<n;i++)
  14. {
  15. for(int j=0;j<n;j++)
  16. {
  17. if(G[i][j]>G[i][x]+G[x][j])
  18. G[i][j]=G[i][x]+G[x][j];
  19. }
  20. }
  21. return;
  22. }
  23. int main()
  24. {
  25. scanf("%d %d",&n,&m);
  26. for(int i=0;i<n;i++)//初始化
  27. {
  28. for(int j=0;j<n;j++)
  29. G[i][j]=maxn;
  30. }
  31. for(int i=0;i<n;i++)scanf("%d",&t[i]);
  32. for(int i=0;i<m;i++)
  33. {
  34. int x,y,z;
  35. scanf("%d%d%d",&x,&y,&z);
  36. G[x][y]=z;G[y][x]=z;
  37. }
  38. scanf("%d",&Q);
  39. for(int i=1;i<=Q;i++)
  40. {
  41. int x,y,z;
  42. scanf("%d%d%d",&x,&y,&z);
  43. while(z>=t[now]&&now<n)//如果z>=该村庄修复时间 ,则该村庄可作中转站
  44. {
  45. update(now++);//更新点
  46. }
  47. if(t[x]>z||t[y]>z||G[x][y]==maxn)printf("-1\n");
  48. else printf("%d\n",G[x][y]);
  49. }
  50. return 0;
  51. }

(洛谷)电车

最小生成树算法:  最小生成树是什么呢,实际上就是给您一个图,要求把图变成一个由n-1(n为点数)条边组成的图,使得总边权最小。

最小生成树算法( Kruskal )适用于稀疏图

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n,m,fa[6000];
  5. long long sum;
  6. struct NODE
  7. {
  8. int x,y,w;//存储边消息,,不是前向星
  9. }edge[300000];
  10. bool cmp(NODE x,NODE y)
  11. {
  12. return x.w<y.w;
  13. }
  14. int f_ind(int x)
  15. { //注意别漏了第一个fa[x]
  16. return fa[x]=fa[x]==x?x:f_ind(fa[x]);//找父节点路径压缩
  17. }
  18. int main()
  19. {
  20. cin>>n>>m;
  21. for(int i=1;i<=m;i++)
  22. {
  23. int x,y,z;
  24. scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].w);
  25. }
  26. for(int i=1;i<=n;i++)fa[i]=i;
  27. sort(edge+1,edge+1+m,cmp);//把边权值从小到大
  28. for(int i=1;i<=m;i++)
  29. {
  30. int h=edge[i].x,t=edge[i].y;
  31. if(f_ind(h)!=f_ind(t))//判断是否在一个连通图里
  32. {
  33. sum+=edge[i].w;
  34. fa[f_ind(h)]=fa[f_ind(t)];//合并连通图
  35. }
  36. }
  37. int x=f_ind(1);
  38. for(int i=2;i<=n;i++)//判断是否能成连通图
  39. {
  40. if(f_ind(i)!=x)
  41. {
  42. cout<<"orz";return 0;
  43. }
  44. }
  45. cout<<sum;
  46. return 0;
  47. }

 (牛客)Forsaken喜欢独一无二的树(似懂非懂)

(洛谷)修复公路

最小生成树( prime )适用于稠密图  (洛谷)公路修建

  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <cstring>
  6. using namespace std;
  7. #define ll long long
  8. #define inf 0x7fffffff
  9. int n,m,x[6000],y[6000];
  10. bool vis[6000];
  11. double dis[6000],ans;
  12. double dist(int i,int j)
  13. {
  14. return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j]));
  15. }
  16. int main()
  17. {
  18. cin>>n;
  19. for(int i=1;i<=n;i++)
  20. {
  21. cin>>x[i]>>y[i];//坐标
  22. dis[i]=inf;
  23. }
  24. dis[1]=0;//1作为树的根
  25. int cnt=0,now;
  26. double minn;
  27. while(++cnt<=n)//循环n次
  28. {
  29. minn=inf;
  30. for(int i=1;i<=n;i++)
  31. {
  32. if(!vis[i]&&minn>dis[i])//找出距离该树最近的点,且这个点没用来更新过(类似迪杰斯特拉)
  33. {
  34. now=i,minn=dis[i];
  35. }
  36. }
  37. ans+=minn;//加边
  38. vis[now]=true;
  39. for(int i=1;i<=n;i++)//将该点加入到该树,更新该树到其他点的距离
  40. {
  41. double t = dist(i,now);//更新树到其他结点的距离,这题不能存边,用前向星和邻接矩阵都会MLE,只能用的时候算
  42. if(t<dis[i])
  43. dis[i]=t;
  44. }
  45. }
  46. printf("%.2f",ans);
  47. return 0;
  48. }

差分约束

补充:必须有一个绝对条件才能算出结果,eg:  xi>=c ;差分约束难点主要在于想题目中隐含的不等式,不等式不能漏想

(acwing)糖果(直接给出不等式)(差分约数+spfa求最长路并判断正环+栈优化)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=111111;
  10. const ll M=311111;
  11. int n,m,cnt,head[N];
  12. int e[N];
  13. int dis[N];
  14. bool vis[N];
  15. struct EDGE
  16. {
  17. int x,y,w,neaxty;
  18. }edge[M];
  19. void addedge(int x,int y,int w)
  20. {
  21. edge[++cnt].x=x;
  22. edge[cnt].y=y;
  23. edge[cnt].w=w;
  24. edge[cnt].neaxty=head[x];
  25. head[x]=cnt;
  26. }
  27. //易得求最小值,所以求 【源点的单源最长路】
  28. //条件1:A==B -> A>=B,B>=A
  29. //条件2:A<B -> B>=A+1
  30. //条件3:A>=B
  31. //条件4:A>B -> A>=B+1
  32. //条件5:A<=B -> B>=A
  33. //以上全是相对的条件,必须找到绝对条件才能解题,题目中保证每个小朋友都有糖,即x>=1,即x>=x0+1
  34. //另外:A>=B+c 在求最长路中表示,B向A连一条长度为c的边
  35. bool spfa()//用第一种方法,判断负环同时维护 源点的单源最长路
  36. {
  37. memset(dis,-0x3f,sizeof dis);//最长路初始化为负无穷
  38. dis[0]=0;//源点到自己距离为0
  39. stack<int>s; //优化:用栈(若用队列,遇到正环则更新一次又将元素放到队尾,直到遍历完整个队列才去算他),用栈遇到正环,则在队尾反复更新,当nev>=n+1则返回
  40. s.push(0);vis[0]=1;
  41. int count=0;
  42. while(s.size())
  43. {
  44. int x=s.top();s.pop();vis[x]=0;
  45. for(int i=head[x];i;i=edge[i].neaxty)
  46. {
  47. int y=edge[i].y;
  48. if(dis[y]<dis[x]+edge[i].w)
  49. {
  50. dis[y]=dis[x]+edge[i].w;
  51. e[y]=e[x]+1;
  52. if(e[y]>n)return true;
  53. if(!vis[y])
  54. {
  55. s.push(y);
  56. vis[y]=1;
  57. }
  58. }
  59. }
  60. }
  61. return false;
  62. }
  63. int main()
  64. {
  65. cin>>n>>m;
  66. while(m--)
  67. {
  68. int x,a,b;
  69. cin>>x>>a>>b;
  70. if(x==1)addedge(a,b,0),addedge(b,a,0);
  71. else if(x==2)addedge(a,b,1);
  72. else if(x==3)addedge(b,a,0);
  73. else if(x==4)addedge(b,a,1);
  74. else if(x==5)addedge(a,b,0);
  75. }
  76. for(int i=1;i<=n;i++)addedge(0,i,1);//绝对条件
  77. //根据题意,可能无解,即最长路中存在正环,故用spfa
  78. if(spfa())
  79. {
  80. cout<<-1;
  81. return 0;
  82. }
  83. ll sum=0;
  84. for(int i=1;i<=n;i++)sum+=dis[i];
  85. cout<<sum;
  86. return 0;
  87. }

(acwing)区间(思维+差分约束+spfa求最长路)

  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <queue>
  5. #include <stack>
  6. #include <vector>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. using namespace std;
  14. #define LL __int128
  15. #define ll long long
  16. #define ull unsigned long long
  17. const int imax=1e9;
  18. const ll lmax=2e18;
  19. const ll mod =1e9+7;
  20. const ll N=55555;
  21. const ll M=3*N;
  22. int head[N],cnt,n,dis[N];
  23. bool vis[N];
  24. struct EDGE
  25. {
  26. int x,y,w,neaxty;
  27. }edge[M];
  28. void addedge(int x,int y,int w)
  29. {
  30. edge[++cnt].x=x;
  31. edge[cnt].y=y;
  32. edge[cnt].w=w;
  33. edge[cnt].neaxty=head[x];
  34. head[x]=cnt;
  35. }
  36. //题意:给出n个a,b,c,对于每个i,找出c个x,使a<=x<=b,现在要使得找出的x的个数尽量少(就是让他们尽量重叠)
  37. //思路:因为ai <= x <= bi 的整数x不少于ci个,易知用前缀和(记得把数往后平移1,把0留出来),得出等式1
  38. //s[b]-s[a-1]>=c -> s[b]>=s[a-1]+c
  39. //再推等式23
  40. //s[i]>=s[i-1]
  41. //s[i]-s[i-1]<=1 -> s[i-1]>=s[i]-1
  42. //做法为差分约束求最小值,要求最长路,且满足从源点(0)出发,能走到所有的边 (因为s[i-1] 和 s[i]之间有边 0->1->2->3...)
  43. void spfa()
  44. {
  45. memset(dis,-0x3f,sizeof dis);//最长路,初始化为负无穷
  46. dis[0]=0;//源点到自己距离为0
  47. queue<int>q;//因为没有环,直接用队列更快
  48. q.push(0);vis[0]=1;
  49. while(q.size())
  50. {
  51. int x=q.front();q.pop();vis[x]=0;
  52. for(int i=head[x];i;i=edge[i].neaxty)
  53. {
  54. int y=edge[i].y;
  55. if(dis[y]<dis[x]+edge[i].w)
  56. {
  57. dis[y]=dis[x]+edge[i].w;
  58. if(!vis[y])
  59. {
  60. q.push(y);
  61. vis[y]=1;
  62. }
  63. }
  64. }
  65. }
  66. }
  67. int main()
  68. {
  69. scanf("%d",&n);
  70. for(int i=1;i<=50001;i++)
  71. {
  72. addedge(i-1,i,0);
  73. addedge(i,i-1,-1);
  74. }
  75. for(int i=1;i<=n;i++)
  76. {
  77. int a,b,c;
  78. scanf("%d %d %d",&a,&b,&c);
  79. a++,b++;//平移,因为前缀和,把0留出来
  80. addedge(a-1,b,c);
  81. }
  82. spfa();//为什么不用dj?因为dj算法不允许有负权边
  83. cout<<dis[50001];//从源点到50001的最长路代表满足0->1->2->3....50001路径(条件)
  84. return 0;
  85. }

(acwing)排队布局 (判断负环+求最短路径+差分约束)

  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <queue>
  5. #include <stack>
  6. #include <vector>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. using namespace std;
  14. #define LL __int128
  15. #define ll long long
  16. #define ull unsigned long long
  17. #define INF 0x3f3f3f3f
  18. const ll mod =1e9+7;
  19. const ll N=1111;
  20. const ll M=33333;
  21. int head[N],cnt,n,m1,m2,dis[N],e[N];
  22. bool vis[N];
  23. struct EDGE
  24. {
  25. int x,y,w,neaxty;
  26. }edge[M];
  27. void addedge(int x,int y,int w)
  28. {
  29. edge[++cnt].x=x;
  30. edge[cnt].y=y;
  31. edge[cnt].w=w;
  32. edge[cnt].neaxty=head[x];
  33. head[x]=cnt;
  34. }
  35. bool spfa(int size)
  36. {
  37. memset(dis,0x3f,sizeof dis);
  38. memset(vis,0,sizeof vis);
  39. memset(e,0,sizeof e);
  40. dis[1]=0;
  41. stack<int>q;
  42. for(int i=1;i<=size;i++)
  43. {
  44. q.push(i);
  45. vis[i]=1;
  46. }
  47. while(q.size())
  48. {
  49. int x=q.top();q.pop();vis[x]=0;
  50. for(int i=head[x];i;i=edge[i].neaxty)
  51. {
  52. int y=edge[i].y;
  53. if(dis[y]>dis[x]+edge[i].w)
  54. {
  55. dis[y]=dis[x]+edge[i].w;
  56. e[y]=e[x]+1;
  57. if(e[y]>n)return true;
  58. if(!vis[y])
  59. {
  60. vis[y]=1;
  61. q.push(y);
  62. }
  63. }
  64. }
  65. }
  66. return false;
  67. }
  68. //思路:因为求最大值,所以求最短路,第一问要spfa判断负环,,然后再求一遍最短路,若dis[n]<INF,则输出dis[n],否则输出-2
  69. //x[i]表示i点到1号奶牛的距离
  70. //x[i]<=x[i+1]
  71. //条件1:x[a]-x[b]<=L,x[a]<=x[b]+L (a在b右侧)
  72. //条件2:x[a]-x[b]>=L,x[b]<=x[a]-L (a在b右侧)
  73. //因为以上全是相对条件,没有绝对条件,要补上一个x[1]=0,即x[1]>=x[1](本身自己就是源点)+0 x[1]<=x[1]+0,没有边,不用建边
  74. //且因为x[i]<=x[i+1],求最短路时,从1出发可以遍历所有点,从而遍历所有边,满足所有不等式,所以spfa时放1
  75. int main()
  76. {
  77. scanf("%d %d %d",&n,&m1,&m2);
  78. for(int i=1;i<n;i++)addedge(i+1,i,0);
  79. while(m1--)
  80. {
  81. int a,b,c;
  82. scanf("%d%d%d",&a,&b,&c);
  83. if(a<b)swap(a,b);//a在b右侧
  84. addedge(b,a,c);
  85. }
  86. while(m2--)
  87. {
  88. int a,b,c;
  89. scanf("%d%d%d",&a,&b,&c);
  90. if(a<b)swap(a,b);
  91. addedge(a,b,-c);
  92. }
  93. if(spfa(n))puts("-1");//判断负环
  94. else
  95. {
  96. spfa(1);//求最短路(带负边权)
  97. if(dis[n]!=INF)
  98. printf("%d",dis[n]);
  99. else
  100. puts("-2");
  101. }
  102. return 0;
  103. }

(acwing)雇佣收银员 (思维+前缀和+差分约束)

  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <queue>
  5. #include <stack>
  6. #include <vector>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. using namespace std;
  14. #define LL __int128
  15. #define ll long long
  16. #define ull unsigned long long
  17. #define INF 0x3f3f3f3f
  18. const ll mod =1e9+7;
  19. const ll N=30;
  20. const ll M=33333;
  21. int head[N],cnt,n,m1,m2,dis[N],e[N],r[N],num[N],s[N];//num为从t
  22. bool vis[N];
  23. struct EDGE
  24. {
  25. int x,y,w,neaxty;
  26. }edge[M];
  27. void addedge(int x,int y,int w)
  28. {
  29. edge[++cnt].x=x;
  30. edge[cnt].y=y;
  31. edge[cnt].w=w;
  32. edge[cnt].neaxty=head[x];
  33. head[x]=cnt;
  34. }
  35. //思路: 求最小值,最长路
  36. //设xi为第i时刻选的员工人数 则0<=xi<=num[i]
  37. //x[i-7]+x[i-6]+....x[i]>=r[i]
  38. //运用前缀和,空一个位置0出来
  39. //则上述可替代为 0<=s[i]-s[i-1]<=num[i] -> s[i]>=s[i-1] s[i-1]>=s[i]-num[i]
  40. //s[i]-s[i-8]>=r[i] -> s[i]>=s[i-8] + r[i] (i-8>=0)
  41. //s[i]+s[24]-s[i+16]>=r[i] -> s[i]>=s[i+16]-s[24]+r[i] (1<=i<=7)
  42. //s[24]即为答案,对s[24]进行二分答案
  43. //因为s[24]为定值,所以s[24]>=s[0]+s[24] s[24]<=s[0]+s[24]
  44. void build(int s24)
  45. {
  46. for(int i=1;i<=24;i++)//从源点(0)可以遍历到所有点从而遍历所有边
  47. {
  48. addedge(i-1,i,0);
  49. addedge(i,i-1,-num[i]);
  50. }
  51. for(int i=8;i<=24;i++)
  52. {
  53. addedge(i-8,i,r[i]);
  54. }
  55. for(int i=1;i<=7;i++)
  56. {
  57. addedge(i+16,i,-s24+r[i]);
  58. }
  59. addedge(0,24,s24);
  60. addedge(24,0,-s24);
  61. }
  62. bool spfa(int s24)
  63. {
  64. memset(dis,-0x3f,sizeof dis);
  65. memset(head,0,sizeof head);
  66. memset(e,0,sizeof e);
  67. memset(vis,0,sizeof vis);
  68. cnt=0;
  69. build(s24);
  70. stack<int>q;
  71. dis[0]=0;//0可以遍历所有边(满足所有条件),所以放0,放1也可以(但建立规范吧,因为有些题不行)
  72. vis[0]=1;q.push(0);
  73. while(q.size())
  74. {
  75. int x=q.top();q.pop();vis[x]=0;
  76. for(int i=head[x];i;i=edge[i].neaxty)
  77. {
  78. int y=edge[i].y;
  79. if(dis[y]<dis[x]+edge[i].w)
  80. {
  81. dis[y]=dis[x]+edge[i].w;
  82. e[y]=e[x]+1;
  83. if(e[y]>24)return false;//正环,无解
  84. if(!vis[y])
  85. {
  86. vis[y]=1;
  87. q.push(y);
  88. }
  89. }
  90. }
  91. }
  92. return true;
  93. }
  94. int main()
  95. {
  96. int T;cin>>T;
  97. while(T--)
  98. {
  99. for(int i=0;i<=23;i++)cin>>r[i+1];//将i往后平移一位,因为前缀和
  100. cin>>n;
  101. memset(num,0,sizeof num);
  102. for(int i=1;i<=n;i++)
  103. {
  104. int x;
  105. cin>>x;
  106. num[x+1]++;//统计该时刻员工总人数
  107. }
  108. int l=0,r=n,ans;//上限为最多能招的人数,为n
  109. bool flag=false;
  110. while(l<=r)
  111. {
  112. int mid=(l+r)/2;
  113. if(spfa(mid))r=mid-1,ans=mid,flag=true;
  114. else l=mid+1;
  115. }
  116. if(flag)cout<<ans<<endl;
  117. else puts("No Solution");
  118. }
  119. return 0;
  120. }

二分图判定(牛客)关押罪犯

  1. #include<iostream>
  2. #include <cstring>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N=21000,M=110000;
  7. int head[N],cnt,n,m,color[N],ans;
  8. struct NODE
  9. {
  10. int x,y,w,neaxty;
  11. }edge[2*M];//注意无向边
  12. void addedge(int x,int y,int z)
  13. {
  14. edge[++cnt].x=x;
  15. edge[cnt].y=y;
  16. edge[cnt].w=z;
  17. edge[cnt].neaxty=head[x];
  18. head[x]=cnt;
  19. }
  20. bool judge(int d)
  21. {
  22. memset(color,0,sizeof color);
  23. queue<int>q;
  24. for(int i=1;i<=n;i++)
  25. {
  26. if(color[i])continue;//已染过色
  27. q.push(i);
  28. color[i]=1;
  29. while(q.size())
  30. {
  31. int x=q.front();q.pop();
  32. for(int i=head[x];i;i=edge[i].neaxty)
  33. {
  34. int y=edge[i].y;
  35. if(edge[i].w>=d)//满足要求且没染过色
  36. {
  37. if(!color[y])
  38. {
  39. q.push(y);//这里别漏了
  40. if(color[x]==1)color[y]=2;
  41. else color[y]=1;
  42. }
  43. else if(color[y]==color[x])return false;//不为二分图
  44. }
  45. }
  46. }
  47. }
  48. return true;
  49. }
  50. int main()//二分图:要将罪犯分到两个集合内且集合内没有连边(即无仇恨)
  51. {
  52. cin>>n>>m;
  53. int l=1,r=0;
  54. for(int i=1;i<=m;i++)
  55. {
  56. int a,b,c;
  57. cin>>a>>b>>c;
  58. r=max(r,c);
  59. addedge(a,b,c);
  60. addedge(b,a,c);
  61. }
  62. while(l<=r)//二分枚举一个最小值,使得罪犯刚好被分到两个集合且罪犯间无连边,因为为最小值,所以减一就是集合内罪犯的第一条连边(即最大影响力)
  63. {
  64. int mid=(l+r)>>1;
  65. if(judge(mid))
  66. {
  67. ans=mid;
  68. r=mid-1;
  69. }
  70. else l=mid+1;
  71. }
  72. cout<<ans-1;
  73. return 0;
  74. }

(洛谷)封锁阳光大学

二分图的最大匹配(洛谷p3386) 

二分图匈牙利算法的理解和代码_哔哩哔哩_bilibili

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. int head[600],n,m,e,cnt,biao[600],yuyue[600],ticheng;
  6. struct NODE
  7. {
  8. int x,y,neaxty;
  9. }edge[55555];
  10. void addedge(int x,int y)
  11. {
  12. edge[++cnt].x=x;
  13. edge[cnt].y=y;
  14. edge[cnt].neaxty=head[x];
  15. head[x]=cnt;
  16. }
  17. bool zhongjie(int x)
  18. {
  19. for(int i=head[x];i;i=edge[i].neaxty)
  20. {
  21. int y=edge[i].y;
  22. if(biao[y])continue;//该房子已看过,防止递归时陷入死循环(房主愿意换房但换了序号在这之前的房子)
  23. biao[y]=1;
  24. if(!yuyue[y]||zhongjie(yuyue[y]))//该房子未被预约或房主愿意换房
  25. {
  26. yuyue[y]=x;//标记房子主任
  27. return true;
  28. }
  29. }
  30. return false;
  31. }
  32. int main()//将二分图的一边模拟成人,一边模拟房子,整个过程模拟人买房的数量达到最大值
  33. {
  34. scanf("%d %d %d",&n,&m,&e);
  35. for(int i=1;i<=e;i++)
  36. {
  37. int u,v;
  38. scanf("%d %d",&u,&v);
  39. addedge(u,v);//人和房子,单向关系
  40. }
  41. for(int i=1;i<=n;i++)
  42. {
  43. memset(biao,0,sizeof biao);
  44. if(zhongjie(i))ticheng++;
  45. }
  46. printf("%d",ticheng);
  47. return 0;
  48. }

 (acwing)棋盘覆盖(思维+二分图匹配)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=200;
  10. const ll M=222222;
  11. typedef pair<int,int> PII;
  12. int n,m,d[5]={-1,0,1,0,-1};
  13. bool biao[N][N],g[N][N];
  14. PII yuyue[N][N];
  15. ll ans;
  16. bool inmap(int x,int y)
  17. {
  18. return x>=1&&x<=n&&y>=1&&y<=n;
  19. }
  20. bool zhongjie(PII u)
  21. {
  22. int x=u.first,y=u.second;
  23. for(int i=0;i<4;i++)//不用建边了,因为就是相邻点
  24. {
  25. int nx=x+d[i];
  26. int ny=y+d[i+1];
  27. if(!inmap(nx,ny)||g[nx][ny])continue;
  28. if(biao[nx][ny])continue;
  29. biao[nx][ny]=1;
  30. if(!yuyue[nx][ny].first||zhongjie(yuyue[nx][ny]))
  31. {
  32. yuyue[nx][ny]={x,y};
  33. return true;
  34. }
  35. }
  36. return false;
  37. }
  38. //思路;将格子看成一个点,则一个骨牌就是两点间的一条边,问题变成了用一个点匹配另外一个点,求最大匹配数
  39. //很容易联想到二分图最大匹配,用之前判断是否能看成二分图:用格子坐标x,y之和%2判断其奇偶性,易得同性之间是不相邻的(可看成没有边),相邻的异性可互相匹配
  40. //即为二分图,可使用匈牙利算法求最大匹配数
  41. int main()
  42. {
  43. int t;
  44. cin>>n>>t;
  45. while(t--)
  46. {
  47. int x,y;cin>>x>>y;
  48. g[x][y]=1;//标记坏掉的格子
  49. }
  50. for(int i=1;i<=n;i++)
  51. {
  52. for(int j=1;j<=n;j++)
  53. {
  54. memset(biao,0,sizeof biao);
  55. //将所有格子二分成奇数格子和偶数格子,用奇数格子匹配偶数格子
  56. if((i+j)%2&&!g[i][j]&&zhongjie({i,j}))ans++;
  57. }
  58. }
  59. cout<<ans;
  60. return 0;
  61. }

二分图的最小点覆盖(用最少的点覆盖最多的边)= 二分图的最大匹配

(acwing)机器任务

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=200;
  10. const ll M=1100;
  11. typedef pair<int,int> PII;
  12. int n,m,k,biao[N],yuyue[N],head[N],cnt,ans;
  13. struct EDGE
  14. {
  15. int x,y,neaxty;
  16. }edge[M];
  17. void addedge(int x,int y)
  18. {
  19. edge[++cnt].x=x;
  20. edge[cnt].y=y;
  21. edge[cnt].neaxty=head[x];
  22. head[x]=cnt;
  23. }
  24. bool zhongjie(int x)
  25. {
  26. for(int i=head[x];i;i=edge[i].neaxty)
  27. {
  28. int y=edge[i].y;
  29. if(biao[y])continue;
  30. biao[y]=1;
  31. if(!yuyue[y]||zhongjie(yuyue[y]))
  32. {
  33. yuyue[y]=x;
  34. return true;
  35. }
  36. }
  37. return false;
  38. }
  39. //思路:每个任务可抽象成一条边,A[i]和B[i]为边上两点,要用最少的点覆盖每个边(任务),求的是最小点覆盖
  40. //又A和B连通,A[i]内部不连通,得该图为二分图
  41. //二分图的最小点覆盖==二分图的最大匹配
  42. int main()
  43. {
  44. while(cin>>n>>m>>k)
  45. {
  46. memset(yuyue,0,sizeof yuyue);
  47. memset(head,0,sizeof head);
  48. cnt=ans=0;
  49. while(k--)
  50. {
  51. int t,x,y;
  52. cin>>t>>x>>y;
  53. if(!x||!y)continue;
  54. addedge(x,y);
  55. }
  56. getchar();
  57. for(int i=0;i<n;i++)
  58. {
  59. memset(biao,0,sizeof biao);
  60. if(zhongjie(i))ans++;
  61. }
  62. cout<<ans<<endl;
  63. }
  64. return 0;
  65. }

二分图的最大独立集

(acwing)骑士放置

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=110;
  10. const ll M=55555;
  11. typedef pair<int,int> PII;
  12. int d[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{1,2},{2,1},{-1,2},{-2,1}};
  13. int n,m,ans;
  14. PII yuyue[N][N];
  15. bool g[N][N],biao[N][N];
  16. bool inmap(int x,int y)
  17. {
  18. return x>=1&&x<=n&&y>=1&&y<=m;
  19. }
  20. bool zhongjie(PII X)
  21. {
  22. int x=X.first,y=X.second;
  23. for(int i=0;i<8;i++)
  24. {
  25. int nx=x+d[i][0];
  26. int ny=y+d[i][1];
  27. // int nx=x,ny=y;
  28. if(!inmap(nx,ny)||g[nx][ny]||biao[nx][ny])continue;
  29. biao[nx][ny]=1;
  30. if(!yuyue[nx][ny].first||zhongjie(yuyue[nx][ny]))
  31. {
  32. yuyue[nx][ny]={x,y};
  33. return true;
  34. }
  35. }
  36. return false;
  37. }
  38. //最大独立集:选出最多的点,使得选出的点没有边,最大独立集(在二分图中)=总点数n-最大匹配数
  39. //在该题,将所有骑士能到达的点连一条边,则答案即为最大独立集
  40. //判断是否为二分图:将图按奇偶性染色,发现骑士能到达的地方与他所在的点奇偶性相反,是二分图
  41. //此题答案还要剪掉禁止放置的格子数
  42. int main()
  43. {
  44. int t;
  45. cin>>n>>m>>t;
  46. int tem=t;
  47. while(tem--)
  48. {
  49. int x,y;cin>>x>>y;
  50. g[x][y]=1;
  51. }
  52. for(int i=1;i<=n;i++)
  53. {
  54. for(int j=1;j<=m;j++)
  55. {
  56. if(g[i][j]||!((i+j)%2))continue;
  57. memset(biao,0,sizeof biao);
  58. if(zhongjie({i,j}))ans++;
  59. }
  60. }
  61. cout<<n*m-t-ans;
  62. return 0;
  63. }

LCA(求两点的最近公共祖先)

倍增法(nlogn)

(洛谷)【模板】最近公共祖先(LCA)

视频:【manim | 算法】7分钟学会倍增法求解LCA_哔哩哔哩_bilibili

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define inf 0x3f3f3f3f
  4. #define ll long long
  5. const ll mod =1e9+7;
  6. #define ull unsigned long long
  7. int n,m,head[555555],cnt,s,dep[555555],f[555555][100];//dep维护点的深度,f[i][j]维护从i点向上跳2^j到达的点
  8. struct EDGE
  9. {
  10. int x,y,neaxty;
  11. }edge[1111111];//树的边大概为2*N
  12. void addedge(int x,int y)
  13. {
  14. edge[++cnt].x=x;
  15. edge[cnt].y=y;
  16. edge[cnt].neaxty=head[x];
  17. head[x]=cnt;
  18. }
  19. void dfs(int x,int fa)//预处理,求f函数
  20. {
  21. dep[x]=dep[fa]+1;//维护点的深度
  22. for(int i=1;(1<<i)<=dep[x];i++)
  23. {
  24. f[x][i]=f[f[x][i-1]][i-1];//从x点向上跳2^i到达的点=从x点向上跳2^(i-1)到达的点再跳2^(i-1)到达的点
  25. }
  26. for(int i=head[x];i;i=edge[i].neaxty)
  27. {
  28. int y=edge[i].y;
  29. if(fa==y)continue;
  30. f[y][0]=x;//向上走1步是父亲
  31. dfs(y,x);
  32. }
  33. }
  34. int LCA(int x,int y)
  35. {
  36. if(dep[x]<dep[y])swap(x,y);//保证x比y深
  37. for(int i=20;i>=0;i--)//倍增跳跃,维护x和y在同一深度
  38. {
  39. if(dep[f[x][i]]>=dep[y])
  40. x=f[x][i];
  41. if(x==y)return x;//深度到达同一水平,两点也刚好重合
  42. }
  43. for(int i=20;i>=0;i--)//两个点同时倍增跳跃,看能不能到达最近公共祖先
  44. {
  45. if(f[x][i]!=f[y][i])
  46. x=f[x][i],y=f[y][i];
  47. }
  48. return f[x][0];
  49. }
  50. int main()
  51. {
  52. cin>>n>>m>>s;
  53. for(int i=1;i<n;i++)
  54. {
  55. int x,y;
  56. cin>>x>>y;
  57. addedge(x,y);
  58. addedge(y,x);
  59. }
  60. dfs(s,0);
  61. while(m--)
  62. {
  63. int x,y;
  64. cin>>x>>y;
  65. cout<<LCA(x,y)<<endl;
  66. }
  67. return 0;
  68. }

 离线求LCA(tarjan)(o(n+m))

(洛谷)【模板】最近公共祖先(LCA)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=555555;
  10. const ll M=555555;
  11. typedef pair<int,int> PII;
  12. int n,m,head[N],cnt,dis[N],p[N],ans[M],s;
  13. int vis[N];//注意vis为int类型
  14. vector<PII>q[M];
  15. struct EDGE
  16. {
  17. int x,y,w,neaxty;
  18. }edge[M*2];
  19. void addedge(int x,int y)
  20. {
  21. edge[++cnt].x=x;
  22. edge[cnt].y=y;
  23. edge[cnt].neaxty=head[x];
  24. head[x]=cnt;
  25. }
  26. int f_ind(int x)
  27. {
  28. return p[x]=x==p[x]?x:f_ind(p[x]);
  29. }
  30. void tarjan(int x)
  31. {
  32. vis[x]=1;//当前路径标记为1
  33. for(int i=head[x];i;i=edge[i].neaxty)
  34. {
  35. int y=edge[i].y;
  36. if(!vis[y])
  37. {
  38. tarjan(y);
  39. p[y]=x;//将y合并到x的根节点(这里的根不一定是整个树的根,很大概率是那些还没完成回溯的,即其p[]没有被更新为其父节点
  40. }
  41. }
  42. for(auto i : q[x])
  43. {
  44. int y=i.first,id=i.second;
  45. if(vis[y]==1)//y在x前搜过并回溯了,y在x上面(即dfs序更小),其根节点即为最近公共祖先
  46. {
  47. int anc=f_ind(y);
  48. ans[id]=anc;//x->y的距离=x到根节点距离+y到根节点距离-2*两者最近公共祖先到根节点距离
  49. }
  50. }
  51. }
  52. int main()
  53. {
  54. cin>>n>>m>>s;
  55. for(int i=1;i<=n;i++)p[i]=i;//初始化
  56. for(int i=1;i<n;i++)
  57. {
  58. int x,y,c;
  59. cin>>x>>y;
  60. addedge(x,y);
  61. addedge(y,x);
  62. }
  63. for(int i=1;i<=m;i++)
  64. {
  65. int x,y;
  66. cin>>x>>y;
  67. q[x].push_back({y,i});//存储询问的另一个数和询问的序号
  68. q[y].push_back({x,i});
  69. }
  70. tarjan(s);
  71. for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
  72. return 0;
  73. }

(acwing)距离

  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <queue>
  5. #include <stack>
  6. #include <vector>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. using namespace std;
  14. #define LL __int128
  15. #define ll long long
  16. #define ull unsigned long long
  17. #define INF 0x3f3f3f3f
  18. const ll lmax=2e18;
  19. const ll mod =1e9+7;
  20. const ll N=11000;
  21. const ll M=21111;
  22. typedef pair<int,int> PII;
  23. int n,m,head[N],cnt,dis[N],p[N],ans[M];
  24. int vis[N];//注意vis为int类型
  25. vector<PII>q[M];
  26. struct EDGE
  27. {
  28. int x,y,w,neaxty;
  29. }edge[M];
  30. void addedge(int x,int y,int w)
  31. {
  32. edge[++cnt].x=x;
  33. edge[cnt].y=y;
  34. edge[cnt].w=w;
  35. edge[cnt].neaxty=head[x];
  36. head[x]=cnt;
  37. }
  38. int f_ind(int x)
  39. {
  40. return p[x]=x==p[x]?x:f_ind(p[x]);
  41. }
  42. void dfs(int x,int fa)
  43. {
  44. for(int i=head[x];i;i=edge[i].neaxty)
  45. {
  46. int y=edge[i].y;
  47. if(y==fa)continue;
  48. dis[y]=dis[x]+edge[i].w;
  49. dfs(y,x);
  50. }
  51. }
  52. //0号点:未访问
  53. //1号点:正在访问,还没完成回溯(更新其子节点的p值和更新ans)
  54. //2号点:已经访问完并回溯
  55. void tarjan(int x)
  56. {
  57. vis[x]=1;//当前路径标记为1
  58. for(int i=head[x];i;i=edge[i].neaxty)
  59. {
  60. int y=edge[i].y;
  61. if(!vis[y])
  62. {
  63. tarjan(y);
  64. p[y]=x;//将y合并到x的根节点(这里的根不一定是整个树的根,很大概率是那些还没完成回溯的,即其p[]没有被更新为其父节点
  65. }
  66. }
  67. for(auto i : q[x])
  68. {
  69. int y=i.first,id=i.second;
  70. if(vis[y]==2)//y在x前搜过并回溯了,y在x上面(即dfs序更小),其根节点即为最近公共祖先
  71. {
  72. int anc=f_ind(y);
  73. ans[id]=dis[x]+dis[y]-2*dis[anc];//x->y的距离=x到根节点距离+y到根节点距离-2*两者最近公共祖先到根节点距离
  74. }
  75. }
  76. vis[x]=2;
  77. }
  78. int main()
  79. {
  80. cin>>n>>m;
  81. for(int i=1;i<=n;i++)p[i]=i;//初始化
  82. for(int i=1;i<n;i++)
  83. {
  84. int x,y,c;
  85. cin>>x>>y>>c;
  86. addedge(x,y,c);
  87. addedge(y,x,c);
  88. }
  89. for(int i=1;i<=m;i++)
  90. {
  91. int x,y;
  92. cin>>x>>y;
  93. q[x].push_back({y,i});//存储询问的另一个数和询问的序号
  94. q[y].push_back({x,i});
  95. }
  96. dfs(1,-1);//求出所有点到根节点(随便取)的距离
  97. tarjan(1);
  98. for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
  99. return 0;
  100. }

(牛客)Ancestor(离线tarjan求最近公共祖先+维护一堆点的最近公共祖先)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=101000;
  10. const ll M=211111;
  11. typedef pair<ll,ll> PII;
  12. ll n,k,cnt1,cnt2,nod[N],b[N],wa[N],wb[N],h1[N],h2[N];
  13. ll dep1[N],dep2[N],ans,idx1,idx2,time1,time2;
  14. vector<PII>q1[M],q2[M];
  15. bool vis1[N],vis2[N];
  16. ll ans1[N],ans2[N],p1[N],p2[N];
  17. struct NODE
  18. {
  19. ll x,dep;
  20. bool operator<(const NODE&t)const
  21. {
  22. return dep>t.dep;
  23. }
  24. };
  25. int f_ind1(int x)
  26. {
  27. return p1[x]=x==p1[x]?x:f_ind1(p1[x]);
  28. }
  29. int f_ind2(int x)
  30. {
  31. return p2[x]=x==p2[x]?x:f_ind2(p2[x]);
  32. }
  33. vector<NODE>v1,v2;
  34. struct EDGE
  35. {
  36. int x,y,neaxty;
  37. }ea[M],eb[M];
  38. void addedge1(int x,int y)
  39. {
  40. ea[++cnt1].x=x;
  41. ea[cnt1].y=y;
  42. ea[cnt1].neaxty=h1[x];
  43. h1[x]=cnt1;
  44. }
  45. void addedge2(int x,int y)
  46. {
  47. eb[++cnt2].x=x;
  48. eb[cnt2].y=y;
  49. eb[cnt2].neaxty=h2[x];
  50. h2[x]=cnt2;
  51. }
  52. void dfs1(int x,int fa)
  53. {
  54. dep1[x]=++time1;//dfs序不能写在循环里面,否则只有60
  55. for(int i=h1[x];i;i=ea[i].neaxty)
  56. {
  57. int y=ea[i].y;
  58. if(y==fa)continue;
  59. dfs1(y,x);
  60. }
  61. }
  62. void dfs2(int x,int fa)
  63. {
  64. dep2[x]=++time2;
  65. for(int i=h2[x];i;i=eb[i].neaxty)
  66. {
  67. int y=eb[i].y;
  68. if(y==fa)continue;
  69. dfs2(y,x);
  70. }
  71. }
  72. void tarjan1(int x)
  73. {
  74. // cout<<x<<endl;
  75. vis1[x]=1;//当前路径标记为1
  76. for(int i=h1[x];i;i=ea[i].neaxty)
  77. {
  78. int y=ea[i].y;
  79. if(!vis1[y])
  80. {
  81. tarjan1(y);
  82. p1[y]=x;
  83. }
  84. }
  85. for(auto i : q1[x])
  86. {
  87. int y=i.first,id=i.second;
  88. if(!vis1[y])continue;
  89. ans1[id]=f_ind1(y);
  90. }
  91. }
  92. void tarjan2(int x)
  93. {
  94. vis2[x]=1;//当前路径标记为1
  95. for(int i=h2[x];i;i=eb[i].neaxty)
  96. {
  97. int y=eb[i].y;
  98. if(!vis2[y])
  99. {
  100. tarjan2(y);
  101. p2[y]=x;
  102. }
  103. }
  104. for(auto i : q2[x])
  105. {
  106. int y=i.first,id=i.second;
  107. // cout<<x<<" "<<y<<endl;
  108. if(!vis2[y])continue;
  109. ans2[id]=f_ind2(y);
  110. // cout<<f_ind2(y)<<"sdf"<<endl;
  111. }
  112. }
  113. //题意:先给出一行x1...xk,xi对应1~n中某个点,有两棵树,对于每棵树,给定n个点和他们的(父子)关系。
  114. //删掉xi,看A树和B树中由剩余的k-1个点的组成的最近公共祖先的权值谁大,A大答案就++
  115. //思路:
  116. //一堆点的最近公共祖先由dfs序最大和dfs序最小的点决定,判断删除的点是否是边界点,是的话就去第二大或第二小的点
  117. //否则即为处在最大值和最小值之间的点,删了不影响答案
  118. int main()
  119. {
  120. scanf("%lld%lld",&n,&k);
  121. for(int i=1;i<=k;i++)scanf("%lld",&nod[i]);
  122. for(int i=1;i<=n;i++)
  123. {
  124. scanf("%lld",&wa[i]);
  125. p1[i]=i;
  126. p2[i]=i;
  127. }
  128. for(int i=1;i<n;i++)
  129. {
  130. int y;
  131. scanf("%d",&y);
  132. // addedge1(i+1,y);
  133. addedge1(y,i+1);
  134. }
  135. for(int i=1;i<=n;i++)scanf("%lld",&wb[i]);
  136. for(int i=1;i<n;i++)
  137. {
  138. int y;
  139. scanf("%d",&y);
  140. // addedge2(i+1,y);
  141. addedge2(y,i+1);
  142. }
  143. dfs1(1,-1);//处理dfs序
  144. dfs2(1,-1);
  145. for(int i=1;i<=k;i++)
  146. {
  147. v1.push_back({nod[i],dep1[nod[i]]});
  148. v2.push_back({nod[i],dep2[nod[i]]});
  149. // cout<<nod[i]<<dep1[nod[i]]<<endl;
  150. // cout<<nod[i]<<dep2[nod[i]]<<endl;
  151. }
  152. sort(v1.begin(),v1.end());
  153. sort(v2.begin(),v2.end());
  154. for(int i=1;i<=k;i++)
  155. {
  156. if(nod[i]==v1.begin()->x)
  157. {
  158. q1[(v1.begin()+1)->x].push_back({(v1.end()-1)->x,++idx1});
  159. q1[(v1.end()-1)->x].push_back({(v1.begin()+1)->x,idx1});
  160. }
  161. else if(nod[i]==(v1.end()-1)->x)
  162. {
  163. q1[(v1.end()-2)->x].push_back({v1.begin()->x,++idx1});
  164. q1[v1.begin()->x].push_back({(v1.end()-2)->x,idx1});
  165. }
  166. else
  167. {
  168. q1[v1.begin()->x].push_back({(v1.end()-1)->x,++idx1});
  169. q1[(v1.end()-1)->x].push_back({v1.begin()->x,idx1});
  170. }
  171. if(nod[i]==v2.begin()->x)
  172. {
  173. q2[(v2.begin()+1)->x].push_back({(v2.end()-1)->x,++idx2});
  174. q2[(v2.end()-1)->x].push_back({(v2.begin()+1)->x,idx2});
  175. }
  176. else if(nod[i]==(v2.end()-1)->x)
  177. {
  178. q2[(v2.end()-2)->x].push_back({v2.begin()->x,++idx2});
  179. q2[v2.begin()->x].push_back({(v2.end()-2)->x,idx2});
  180. }
  181. else
  182. {
  183. q2[(v2.end()-1)->x].push_back({v2.begin()->x,++idx2});
  184. q2[v2.begin()->x].push_back({(v2.end()-1)->x,idx2});
  185. }
  186. }
  187. tarjan1(1);
  188. tarjan2(1);
  189. for(int i=1;i<=idx1;i++)
  190. {
  191. if(wa[ans1[i]]>wb[ans2[i]])ans++;
  192. }
  193. printf("%lld",ans);
  194. return 0;
  195. }

强连通分量

有向图 G中,如果两个顶点vi,vj间,有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点 强连通 。. 如果有向图G的每两个顶点都强连通,称G是一个 强连通图 。. 有向图的极大强连通 子图 ,称为强连通分量

(Tarjan算法)(复杂度o(n+m))

视频:341 强连通分量 Tarjan 算法_哔哩哔哩_bilibili

(洛谷)上白泽慧音(模板)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. int n,m,maxn;//maxn记录最大的组的大小
  10. int dfn[60005],low[60005],tot;//节点x第一次被访问的顺序, 和从节点x出发,所能访问到的最早时间戳
  11. int stk[60005],instk[60005],top;
  12. int scc[60005],siz[60005],cnt;//记录某个点属于哪一组,那一组的大小
  13. vector<int>e[50005];
  14. void tarjan(int x)
  15. {
  16. dfn[x]=low[x]=++tot;//一开始都是自己
  17. stk[++top]=x,instk[x]=1;//入栈
  18. for(int i=0;i<e[x].size();i++)//遍历所有连边的子节点
  19. {
  20. int y=e[x][i];
  21. if(!dfn[y])//没被访问
  22. {
  23. tarjan(y);
  24. low[x]=min(low[x],low[y]);//更新
  25. }
  26. else if(instk[y])//被访问过但还没出栈
  27. {
  28. low[x]=min(low[x],dfn[y]);//注意这里是dfn[y]而不是low[y]
  29. }//已出栈的就不用管
  30. }
  31. if(dfn[x]==low[x])
  32. {
  33. int y;
  34. ++cnt;
  35. do{
  36. y=stk[top--],instk[y]=0;//取栈顶,且出栈
  37. scc[y]=cnt,siz[cnt]++;//记录该点所属组,更新改组大小
  38. maxn=max(maxn,siz[cnt]);//题目:维护最大的组的大小
  39. }while(y!=x);
  40. }
  41. }
  42. int main()
  43. {
  44. cin>>n>>m;
  45. while(m--)
  46. {
  47. int a,b,t;
  48. cin>>a>>b>>t;
  49. if(t==1)
  50. {
  51. e[a].push_back(b);
  52. }
  53. else
  54. {
  55. e[a].push_back(b);
  56. e[b].push_back(a);
  57. }
  58. }
  59. for(int i=1;i<=n;i++)
  60. {
  61. if(!dfn[i])tarjan(i);
  62. }
  63. cout<<maxn<<endl;
  64. int mar=0;
  65. for(int i=1;i<=n;i++)//按编号小到大扫一遍取第一个所在的强连通分量中的点数==cnt的强连通分量(这个强连通分量一定是所求的,因为这个强连通分量最大且有最小的编号来使字典序最小)
  66. {
  67. if(siz[scc[i]]==maxn)
  68. {
  69. mar=scc[i];
  70. }
  71. if(mar&&scc[i]==mar)
  72. {
  73. cout<<i<<" ";
  74. }
  75. }
  76. return 0;
  77. }

Tarjan缩点

tarjan缩点后,组别序号逆序就直接满足拓扑序

(洛谷)校园网络

视频:342 Tarjan SCC 缩点_哔哩哔哩_bilibili

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. int n;
  10. int dfn[11111],low[11111],tot;
  11. int stk[11111],instk[11111],top;
  12. int scc[11111],siz[11111],cnt;
  13. int in[11111],oud[11111];
  14. vector<int>e[11111];
  15. void tarjan(int x)
  16. {
  17. dfn[x]=low[x]=++tot;
  18. stk[++top]=x,instk[x]=1;
  19. for(int i=0;i<e[x].size();i++)
  20. {
  21. int y=e[x][i];
  22. if(!dfn[y])
  23. {
  24. tarjan(y);
  25. low[x]=min(low[x],low[y]);
  26. }
  27. else if(instk[y])
  28. {
  29. low[x]=min(low[x],dfn[y]);//注意这里是dfn[y]而不是low[y]
  30. }
  31. }
  32. if(dfn[x]==low[x])
  33. {
  34. int y;
  35. ++cnt;
  36. do
  37. {
  38. y=stk[top--],instk[y]=0;
  39. scc[y]=cnt,siz[cnt]++;
  40. }while(y!=x);
  41. }
  42. }
  43. int main()
  44. {
  45. cin>>n;
  46. for(int i=1;i<=n;i++)
  47. {
  48. int y;
  49. while(cin>>y)
  50. {
  51. if(y==0)break;
  52. e[i].push_back(y);
  53. }
  54. }
  55. for(int i=1;i<=n;i++)//tarjan强连通分量
  56. {
  57. if(!dfn[i])tarjan(i);
  58. }
  59. for(int i=1;i<=n;i++)//统计缩点后**入度为0和出度为0的点的个数 ,复杂度o(m)
  60. {
  61. for(int j=0;j<e[i].size();j++)
  62. {
  63. if(scc[i]!=scc[e[i][j]])//这里不止一次把e[i][j]写成j了
  64. {
  65. oud[scc[i]]++;//这里只用粗略统计
  66. in[scc[e[i][j]]]++;//这里不止一次把e[i][j]写成j了
  67. }
  68. }
  69. }
  70. int suma=0,sumb=0;
  71. for(int i=1;i<=cnt;i++)
  72. {
  73. if(!in[i])suma++;
  74. if(!oud[i])sumb++;
  75. }
  76. cout<<sumb<<endl;//按题意,为出度为0的点的个数
  77. if(cnt==1)cout<<0;
  78. else
  79. cout<<max(suma,sumb);//按题意,构成强连通分量所需加的边为出度为0和入度为0的点个数的max,只有一个强连通分量除外
  80. return 0;
  81. }

(洛谷)受欢迎的牛 G

(acwing)银河(思维+tarjan缩点+重建图+dp)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=111000;
  10. const ll M=633333;
  11. typedef pair<int,int> PII;
  12. int n,m,h[N],hs[N],cnt;
  13. ll dis[N];
  14. int dfn[N],low[N],tot;
  15. int stk[N],instk[N],top;
  16. int scc[N],siz[N],idx;
  17. struct EDGE
  18. {
  19. int x,y,w,neaxty;
  20. }edge[M];
  21. void addedge(int h[],int x,int y,int w)
  22. {
  23. edge[++cnt].x=x;
  24. edge[cnt].y=y;
  25. edge[cnt].w=w;
  26. edge[cnt].neaxty=h[x];
  27. h[x]=cnt;
  28. }
  29. void tarjan(int x)
  30. {
  31. dfn[x]=low[x]=++tot;
  32. stk[++top]=x,instk[x]=1;
  33. for(int i=h[x];i;i=edge[i].neaxty)
  34. {
  35. int y=edge[i].y;
  36. if(!dfn[y])
  37. {
  38. tarjan(y);
  39. low[x]=min(low[x],low[y]);
  40. }
  41. else if(instk[y])
  42. {
  43. low[x]=min(low[x],dfn[y]);
  44. }
  45. }
  46. if(dfn[x]==low[x])
  47. {
  48. idx++;
  49. int y;
  50. do
  51. {
  52. y=stk[top--];instk[y]=0;
  53. scc[y]=idx,siz[idx]++;
  54. }while(y!=x);
  55. }
  56. }
  57. //条件1:a>=b,b>=a
  58. //条件2:a<b -> b>=a+1
  59. //条件3:a>=b
  60. //条件4:a>b -> a>=b+1
  61. //条件5:a<=b -> b>=a
  62. //条件6:x>=x0+1
  63. //易得知差分约束求最小值,用最长路,无解即存在正环,即环中有边权>0,又由题,边权无负值,所以当一个强连通分量(环)中边权全=0时有解
  64. //所以tarjan判断强连通分量,然后看每个强连通分量中是否有边权>0
  65. //若没有,则有解,缩点重建图,又tarjan处理后,每个点满足拓扑序,直接dp
  66. int main()
  67. {
  68. cin>>n>>m;
  69. while(m--)
  70. {
  71. int t,a,b;
  72. cin>>t>>a>>b;
  73. if(t==1)addedge(h,a,b,0),addedge(h,b,a,0);
  74. else if(t==2)addedge(h,a,b,1);
  75. else if(t==3)addedge(h,b,a,0);
  76. else if(t==4)addedge(h,b,a,1);
  77. else if(t==5)addedge(h,a,b,0);
  78. }
  79. for(int i=1;i<=n;i++)
  80. {
  81. addedge(h,0,i,1);
  82. }
  83. // for(int i=0;i<=n;i++)
  84. // {
  85. // if(!dfn[i])tarjan(i);
  86. // }
  87. tarjan(0);//因为0为超级源点,连向所有点和边,tarjan(0)就够了
  88. bool flag=true;//判断在强连通分量内是否存在正边权
  89. for(int i=0;i<=n;i++)
  90. {
  91. for(int j=h[i];j;j=edge[j].neaxty)
  92. {
  93. int y=edge[j].y;
  94. int a=scc[i],b=scc[y];
  95. if(a==b)//处在同个强连通分量
  96. {
  97. if(edge[j].w>0)
  98. {
  99. flag=false;//存在正边权,无解
  100. break;
  101. }
  102. }
  103. else
  104. {
  105. addedge(hs,a,b,edge[j].w);//不属于同个强连通分量,将这两个强连通分量连一条边
  106. }
  107. }
  108. }
  109. if(!flag)cout<<-1;
  110. else
  111. {
  112. ll ans=0;
  113. for(int i=idx;i;i--)//tarjan并逆序,则为 拓扑序
  114. {
  115. for(int j=hs[i];j;j=edge[j].neaxty)//直接dp
  116. {
  117. int y=edge[j].y;
  118. dis[y]=max(dis[y],dis[i]+edge[j].w);
  119. }
  120. }
  121. for(int i=1;i<=idx;i++)ans+=(ll)dis[i]*siz[i];
  122. cout<<ans;
  123. }
  124. return 0;
  125. }

(acwing)最大半连通子图(思维+tarjan缩点+重建图+边去重+dp)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll MOD =1e9+7;
  9. const ll N=100010;
  10. const ll M=4000010;
  11. typedef pair<int,int> PII;
  12. int n,m,h[N],hs[N],cnt,mod;
  13. int dfn[N],low[N],tot;
  14. int stk[N],instk[N],top;
  15. int scc[N],siz[N],idx;
  16. int f[N],g[N];//dp维护最长链和方案数
  17. struct EDGE
  18. {
  19. int x,y,neaxty;
  20. }edge[M];
  21. void addedge(int h[],int x,int y)
  22. {
  23. edge[++cnt].x=x;
  24. edge[cnt].y=y;
  25. edge[cnt].neaxty=h[x];
  26. h[x]=cnt;
  27. }
  28. void tarjan(int u)
  29. {
  30. dfn[u] = low[u] = ++ tot ;
  31. stk[++ top] = u,instk[u] =true;
  32. for(int i =h[u]; i;i = edge[i].neaxty)
  33. {
  34. int j = edge[i].y;
  35. if(!dfn[j])
  36. {
  37. tarjan(j);
  38. low[u] = min(low[u],low[j]);
  39. }
  40. else if(instk[j]) low[u] = min(low[u] , dfn[j]);
  41. }
  42. if(dfn[u] == low[u])
  43. {
  44. idx ++;
  45. int y;
  46. do{
  47. y = stk[top --];
  48. instk[y] = false;
  49. scc[y] = idx;
  50. siz[idx] ++;
  51. }while(y != u);
  52. }
  53. }
  54. int main()
  55. {
  56. cin>>n>>m>>mod;
  57. while(m--)
  58. {
  59. int a,b;
  60. cin>>a>>b;
  61. addedge(h,a,b);
  62. }
  63. for(int i=1;i<=n;i++)
  64. {
  65. if(!dfn[i])
  66. tarjan(i);
  67. }
  68. unordered_set<ll>ss;
  69. for(int i=1;i<=n;i++)
  70. {
  71. for(int j=h[i];j;j=edge[j].neaxty)
  72. {
  73. int y=edge[j].y;
  74. int a=scc[i],b=scc[y];//缩点
  75. if(a==b)continue;
  76. ll hash= a*1000000ll+b;//简易哈希
  77. if(!ss.count(hash))//判断重边
  78. {
  79. addedge(hs,a,b);
  80. ss.insert(hash);
  81. }
  82. }
  83. }
  84. for(int i = idx; i ;i --)
  85. //由于编号更大的点所在的强连通分量总是更先被找到,且这里要保证顺序,所以我们要逆着循环!
  86. {
  87. if(! f[i])
  88. {
  89. f[i] = siz[i];
  90. g[i] = 1;
  91. }
  92. for(int j = hs[i]; j ; j = edge[j].neaxty)
  93. {
  94. int k = edge[j].y;
  95. if(f[k] < f[i] + siz[k])
  96. {
  97. f[k] = f[i] + siz[k];
  98. g[k] = g[i];
  99. }
  100. else if(f[k] == f[i] + siz[k]) //如果以“点”的为终点的两条长链长度相同,那么将所得的的数目相加
  101. g[k] = (g[k] + g[i]) % mod;//数目很多,记得要%mod哦
  102. }
  103. }
  104. int maxn = 0 ,sum = 0;
  105. for(int i = 1;i <= idx;i ++)
  106. if(f[i] > maxn)
  107. {
  108. maxn = f[i];
  109. sum = g[i];
  110. }
  111. else if(f[i] == maxn) sum = (sum + g[i]) % mod;//将其他点所携带的最长链数目相加!
  112. cout<<maxn<<endl<<sum;
  113. return 0;
  114. }

Tarjan割点

(洛谷)【模板】割点(割顶)

tarjan部分与上面的模板有所不同,已标出

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. const int imax=1e9;
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. #define N 22222
  10. #define M 222222
  11. int n,m,sum;
  12. int dfn[N],low[N],tot;
  13. int stk[N],instk[N],top;
  14. int scc[N],siz[N],cnt,root;
  15. bool cut[N];
  16. vector<int>e[N];
  17. void tarjan(int x)
  18. {
  19. dfn[x]=low[x]=++tot;
  20. int child=0;
  21. for(int i=0;i<e[x].size();i++)
  22. {
  23. int y=e[x][i];
  24. if(!dfn[y])
  25. {
  26. tarjan(y);
  27. low[x]=min(low[x],low[y]);
  28. //1.割点为根节点,搜索树上存在两个子节点满足low[y]>=dfn[x] 2.割点不为根节点,只需一个就够
  29. if(low[y]>=dfn[x])
  30. {
  31. child++;
  32. if(x!=root||child>=2)
  33. {
  34. cut[x]=1;
  35. }
  36. }
  37. }
  38. else//1.不用特判是否在栈内
  39. {
  40. low[x]=min(low[x],dfn[y]);
  41. }
  42. }
  43. //这里不用记录分组
  44. }
  45. int main()
  46. {
  47. cin>>n>>m;
  48. while(m--)
  49. {
  50. int x,y;cin>>x>>y;
  51. e[x].push_back(y);
  52. e[y].push_back(x);
  53. }
  54. for(int i=1;i<=n;i++)
  55. {
  56. if(!dfn[i])
  57. {
  58. root=i;//没搜索过就以他为根节点搜索
  59. tarjan(i);
  60. }
  61. }
  62. for(int i=1;i<=n;i++)
  63. {
  64. if(cut[i])
  65. {
  66. sum++;
  67. }
  68. }
  69. cout<<sum<<endl;
  70. for(int i=1;i<=n;i++)
  71. {
  72. if(cut[i])cout<<i<<" ";
  73. }
  74. return 0;
  75. }

(洛谷)嗅探器(割点+思维)

欧拉路径

欧拉路径(欧拉通路):通过图中所有边的简单路。(换句话说,每条边都通过且仅通过一次)也叫”一笔画”问题。
欧拉回路:闭合的欧拉路径。(即一个环,保证每条边都通过且仅通过一次)
欧拉图:包含欧拉回路的图。

一、无向图
   1 存在欧拉路径的充要条件 : 度数为奇数的点只能有0或2个
   2 存在欧拉回路的充要条件 : 度数为奇数的点只能有0个                                                                     3.边连通,即cnt==m
二、有向图
   1 存在欧拉路径的充要条件 : 要么所有点的出度均==入度;
      要么除了两个点之外,其余所有点的出度==入度 剩余的两个点:一个满足出度-入度==1(起点) 一个满足入度-出度==1(终点)
   2 存在欧拉回路的充要条件 : 所有点的出度均等于入度                                                                       3.边连通,即cnt==m


 

(acwing)欧拉回路(判断有向图和无向图中的欧拉回路并输出)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=110111;
  10. const ll M=444444;
  11. typedef pair<int,int> PII;
  12. int n,m,t,cnt;
  13. int idx,e[M],h[N],ne[M];
  14. int din[N],dou[N],ans[M],tot;
  15. bool used[M];
  16. void add(int x,int y)
  17. {
  18. e[idx]=y,ne[idx]=h[x],h[x]=idx++;
  19. }
  20. void dfs(int x)
  21. {
  22. for(int &i=h[x];~i;)
  23. {
  24. if(used[i])
  25. {
  26. i=ne[i];//删边,因为i用了引用,这里相当于h[x]=ne[i],i=h[x]
  27. continue;
  28. }
  29. used[i]=1;//这里写used[i]=1只是代码规范而已(因为边都删了),used真正作用是要标记的是无向边的另外一条边
  30. if(t==1)used[i^1]=1;//无向边,则要标记两条边 ,,边的组合(0,1) (2,3) (3,4)
  31. int c;//记录第几条边
  32. if(t==1)//无向图
  33. {
  34. c=i/2 + 1;//第几条边
  35. if(i&1)c*=-1;//返回的边(题目要求)
  36. }
  37. else c=i+1;
  38. int j=e[i];
  39. i=ne[i];//先删边,再遍历
  40. dfs(j);
  41. ans[++cnt]=c;//存欧拉路径解释:如果某点有多条边,且有环,则某条边可能会dfs直通终点,所以要遍历完该点所有邻边,回溯时再存入点(边),最后再逆序输出才能不漏
  42. }
  43. }
  44. //补充:每条边用过之后要删掉,不能只标记used[]。不然如果有m条自环,那么第一层走第一个自环,第二层走第二个自环,第三层走第三个自环,
  45. //依次类推,走第k个自环就要遍历k次,所以总共会遍历 O(m2)次(即使有continue)。但是删掉用过的边就不会重复遍历了,就是 O(m)了
  46. int main()
  47. {
  48. cin>>t;
  49. cin>>n>>m;
  50. memset(h,-1,sizeof h);
  51. for(int i=1;i<=m;i++)
  52. {
  53. int x,y;
  54. cin>>x>>y;
  55. add(x,y);
  56. if(t==1)add(y,x);
  57. din[y]++,dou[x]++;
  58. }
  59. if(t==1)//无向图
  60. {
  61. for(int i=1;i<=n;i++)
  62. {
  63. if((din[i]+dou[i])%2)//无向图含欧拉回路的条件是每个点的度数为偶数
  64. { //无向图中,每个点的度数=(入度+出度)/2,因为一条边就可以让该点出度+1,入度+1,这里没有/2是因为前面入度和出度加少了
  65. puts("NO");
  66. return 0;
  67. }
  68. }
  69. }
  70. else
  71. {
  72. for(int i=1;i<=n;i++)
  73. {
  74. if(din[i]!=dou[i])//有向图含欧拉回路的条件是每个点出度=入度
  75. {
  76. puts("NO");
  77. return 0;
  78. }
  79. }
  80. }
  81. for(int i=1;i<=n;i++)
  82. {
  83. if(~h[i])//防止有孤立点
  84. {
  85. dfs(i);
  86. break;
  87. }
  88. }
  89. if(cnt<m)//边不连通
  90. {
  91. puts("NO");
  92. return 0;
  93. }
  94. puts("YES");
  95. for(int i=cnt;i>=1;i--)cout<<ans[i]<<" ";
  96. return 0;
  97. }

(acwing)骑马修栅栏(欧拉路径)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=666;
  10. const ll M=2222;
  11. typedef pair<int,int> PII;
  12. int n,m,t,cnt;
  13. int g[N][N];//邻接矩阵
  14. int d[N],ans[M],tot;
  15. bool used[M];
  16. void dfs(int x)
  17. {
  18. for(int i=1;i<=n;i++)
  19. {
  20. if(!g[x][i])continue;
  21. g[x][i]--,g[i][x]--;//删边
  22. dfs(i);
  23. }
  24. ans[++cnt]=x;//存欧拉路径解释:如果某点有多条边,且有环,则某条边可能会dfs直通终点,所以要遍历完该点所有邻边,回溯时再存入点(边),最后再逆序输出才能不漏
  25. //这里的点则是要遍历完所有的邻点再存自己
  26. }
  27. //思路:欧拉路径问题,对于输出最小解,从序号最小的点开始dfs(若从x点开始,因为回溯才记录答案,x会被放到ans数组末尾,但输出时因为逆序又来到最前面)
  28. //然后对于一个点,若有多条边,优先选择出点序号小的(只能用邻接矩阵实现了)
  29. //对于此题,没给出起点和终点,找度数为奇数的点作为起点开始dfs就行,但有可能是欧拉回路,不存在奇数点,就选小的点作起点
  30. int main()
  31. {
  32. n=500;
  33. cin>>m;
  34. for(int i=1;i<=m;i++)
  35. {
  36. int x,y;
  37. cin>>x>>y;
  38. g[x][y]++,g[y][x]++;
  39. d[x]++,d[y]++;
  40. }
  41. int start = 1;
  42. while (!d[start]) ++start;
  43. for(int i=1;i<=n;i++)
  44. {
  45. if(d[i]%2)//找度数为奇数的点作为起点开始dfs
  46. {
  47. start=i;
  48. break;
  49. }
  50. }
  51. dfs(start);
  52. for(int i=cnt;i>=1;i--)cout<<ans[i]<<endl;
  53. return 0;
  54. }

(acwing)单词游戏(判断有向图的欧拉路径)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL __int128
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define INF 0x3f3f3f3f
  7. const ll lmax=2e18;
  8. const ll mod =1e9+7;
  9. const ll N=30;
  10. const ll M=111111;
  11. typedef pair<int,int> PII;
  12. int t,n;
  13. int e[M],ne[M],h[N],idx,used[M];
  14. int din[N],dou[N],ds,de,cnt;
  15. //思路:题意是将所有单词排成一整排,判断有向图的欧拉路径
  16. void add(int x,int y)
  17. {
  18. e[idx]=y,ne[idx]=h[x],h[x]=idx++;
  19. }
  20. void dfs(int x)
  21. {
  22. for(int &i=h[x];~i;)
  23. {
  24. int j=e[i];
  25. i=ne[i];
  26. dfs(j);
  27. cnt++;
  28. }
  29. }
  30. //题意: 能否依据条件(头尾相连),每个单词用一次,且用完所有单词
  31. //判断有向图 是否为欧拉路径
  32. int main()
  33. {
  34. cin>>t;
  35. while(t--)
  36. {
  37. memset(h,-1,sizeof h);
  38. memset(din,0,sizeof din);
  39. memset(dou,0,sizeof dou);
  40. ds=de=cnt=0;
  41. idx=0;
  42. cin>>n;
  43. string str;
  44. for(int i=1;i<=n;i++)
  45. {
  46. cin>>str;
  47. int a=str[0]-'a';
  48. int b=str[str.size()-1]-'a';
  49. // cout<<a<<" "<<b<<endl;
  50. add(a,b);
  51. dou[a]++,din[b]++;
  52. }
  53. bool flag=true;
  54. for(int i=0;i<26;i++)
  55. {
  56. if(din[i]!=dou[i])
  57. {
  58. if(din[i]-dou[i]==1)de++;//记录入度-出度=1的点的数量
  59. else if(dou[i]-din[i]==1)ds++;//记录出度-入度=1的点的数量
  60. else flag=false;
  61. }
  62. }
  63. if(!((!ds&&!de)||(ds==1 && de==1))) flag=false;//如果不是环同时起点和终点数量不为1
  64. int start=0;
  65. while(!dou[start]) ++start;//可能是环,没有起点(有点模板的意思了)
  66. for(int i=0;i<26;i++)
  67. {
  68. if(dou[i]-din[i]==1)//从起点开始dfs
  69. {
  70. start=i;
  71. break;
  72. }
  73. }
  74. dfs(start);
  75. if(cnt!=n)flag=false;
  76. if(flag) cout<<"Ordering is possible."<<endl;
  77. else cout<<"The door cannot be opened."<<endl;
  78. }
  79. return 0;
  80. }

——————————————————————————————————————————

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/445489?site
推荐阅读
相关标签
  

闽ICP备14008679号