[关闭]
@Simon-Sun 2025-04-11T14:25:38.000000Z 字数 14801 阅读 117

算法模板

学术

数据结构

1、动态开点线段树

  1. #include <iostream>
  2. #define int long long 
  3. using namespace std ; 
  4. const int maxn = 2e5 + 7 ;
  5. int root , n , m , cnt , p , nxt ; 
  6. struct node 
  7. {
  8.     int l , r , max , L , R ;
  9. } tr[maxn * 2 ] ;
  10. void insert(int &p , int now , int l , int r , int val )
  11. {
  12.     if( !p)
  13.     {
  14.         p = ++cnt ; 
  15.         tr[p].L = l , tr[p].R = r ; 
  16.     }
  17.     if(l == r )
  18.     {
  19.         tr[p].max = val ; 
  20.         return ; 
  21.     }
  22.     int mid = l + r >> 1 ;
  23.     if(now <= mid ) insert(tr[p].l , now , l , mid , val ) ; 
  24.     else insert(tr[p].r , now , mid + 1 , r , val ) ; 
  25.     tr[p].max = max(tr[tr[p].l].max , tr[tr[p].r].max ) ;
  26.     //cout << tr[p].max << ' ' ; 
  27. }
  28. int query(int &p , int l , int r )
  29. {
  30.     //cout<<l<<' '<<r<<endl;
  31.     int ans = -maxn ; 
  32.     if(!p)  return -1 ;
  33.     //if( >= l && ) return tr[p].max ;
  34.     int L = tr[p].L , R = tr[p].R ;
  35.     //if(l == r ) return tr[p].max ;
  36.     if(L == l && R == r)    return tr[p].max ; 
  37.     //  if(L >= l && r >= R )   return tr[p].max ; 
  38.     int mid = L + R >> 1 ;
  39.     if(r <= mid )   ans = max(ans , query(tr[p].l , l , r) ) ;
  40.     else if(l > mid )   ans = max(ans , query(tr[p].r , l , r )) ;
  41.     else 
  42.     {
  43.         if(l <= mid )   ans = max(ans , query(tr[p].l , l , mid )) ;
  44.         if(r > mid )    ans = max(ans , query(tr[p].r , mid + 1 , r )) ;
  45.     }
  46. //  cout << ans << '\n' ; 
  47.     return ans ; 
  48. }
  49. signed main()
  50. {
  51.     cin >> m >> p ;
  52.     while( m-- )
  53.     {
  54.         int x ; 
  55.         char op ;   cin >> op >> x ;
  56.         if(op == 'Q')   nxt = query(root , n - x + 1 , n ) ,cout << nxt << '\n' ; 
  57.         else 
  58.         {
  59.             insert(root , ++n , 1 , 200005 , ((x + nxt) % p + p ) % p) ; 
  60.             //cout << ((x + nxt) % p + p ) % p<< ' ' << nxt << '\n' ; 
  61.         }
  62.     }
  63. }

线段树（普通）

  1. //非动态开点
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define maxn 1010101
  5. #define ls p<<1
  6. #define rs p<<1|1
  7. using namespace std;
  8. ll a[maxn],n,m;
  10. struct node 
  11. {
  12.     ll L,R;
  13.     ll add,sum;
  14.     ll len()
  15.     {
  16.         return R-L+1;
  17.     }
  18. }tree[maxn*3];
  20. void Up(ll p)
  21. {
  22.     tree[p].sum=tree[ls].sum+tree[rs].sum;
  23. }
  25. void build(ll l,ll r,ll p)
  26. {
  27.     tree[p].L=l;    tree[p].R=r;
  28.     if(l==r)
  29.     {
  30.         tree[p].add=0;
  31.         tree[p].sum=a[l];//区间是个点直接赋值即可
  32.         return ;
  33.     }
  34.     ll mid=l+r>>1;
  35.     build(l,mid,ls);    build(mid+1,r,rs);
  36.     Up(p);
  37. }
  39. void down(ll p)
  40. {
  41.     ll &t=tree[p].add;
  42.     if(t==0)//如果没有标记，就不用下传
  43.         return ;
  44.     tree[ls].add+=t; tree[rs].add+=t;
  45.     tree[ls].sum+=tree[ls].len()*t; tree[rs].sum+=tree[rs].len()*t;
  46.     t=0;//清空标记
  47. } 
  49. void update(ll l,ll r,ll a,ll p)
  50. {
  51.     if(tree[p].L==l&&tree[p].R==r)
  52.     {
  53.         tree[p].add+=a;
  54.         tree[p].sum+=(r-l+1)*a;
  55.         return ;
  56.     }
  57.     ll mid=(tree[p].L+tree[p].R)>>1;
  58.     down(p);//由于要修改下面的区间的值了，所以先把未下传的标记下传
  59.     if(r<=mid)
  60.         update(l,r,a,ls);
  61.     else if(l>mid)
  62.         update(l,r,a,rs);
  63.     else 
  64.     {
  65.         update(l,mid,a,ls);
  66.         update(mid+1,r,a,rs);
  67.     }
  68.     Up(p);//向上合并一下
  69. }
  71. ll query(ll l,ll r,ll p)
  72. {
  73.     if(l==tree[p].L&&r==tree[p].R)
  74.         return tree[p].sum;
  75.     down(p);
  76.     ll mid=tree[p].L+tree[p].R>>1;
  77.     if(r<=mid)
  78.         return query(l,r,ls);
  79.     if(l>mid)
  80.         return query(l,r,rs);
  81.     else 
  82.     {
  83.         return query(l,mid,ls)+query(mid+1,r,rs);//原因见配套notepad
  84.     }
  85. }
  86. int main()
  87. {
  88.     cin>>n>>m;
  89.     for(ll i=1;i<=n;i++)
  90.          cin>>a[i];
  91.     build(1,n,1);
  92.     while(m--)
  93.     {
  94.         char op ; 
  95.         cin>>op;
  96.         if(op == 'C')
  97.         {
  98.             ll x,y,t;
  99.             cin>>x>>y>>t;
  100.             update(x,y,t,1);
  101.         }
  102.         else 
  103.         {
  104.             ll x,y;
  105.             cin>>x>>y;
  106.             cout<<query(x,y,1)<<endl; 
  107.         }
  108.     }
  109.     return 0;
  110. }
  1. //牛客王老师版本
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define maxn 1010101
  5. #define ls p<<1
  6. #define rs p<<1|1
  7. using namespace std;
  8. ll a[maxn],n,m;
  10. struct node 
  11. {
  12.     ll L,R;
  13.     ll add,sum;
  14.     ll len()
  15.     {
  16.         return R-L+1;
  17.     }
  18. }tree[maxn*3];
  20. void Up(ll p)
  21. {
  22.     tree[p].sum=tree[ls].sum+tree[rs].sum;
  23. }
  25. void build(ll l,ll r,ll p)
  26. {
  27.     tree[p].L=l;    tree[p].R=r;
  28.     if(l==r)
  29.     {
  30.         tree[p].add=0;
  31.         tree[p].sum=a[l];//区间是个点直接赋值即可
  32.         return ;
  33.     }
  34.     ll mid=l+r>>1;
  35.     build(l,mid,ls);    build(mid+1,r,rs);
  36.     Up(p);
  37. }
  39. void down(ll p)
  40. {
  41.     ll &t=tree[p].add;
  42.     if(t==0)//如果没有标记，就不用下传
  43.         return ;
  44.     tree[ls].add+=t; tree[rs].add+=t;
  45.     tree[ls].sum+=tree[ls].len()*t; tree[rs].sum+=tree[rs].len()*t;
  46.     t=0;//清空标记
  47. } 
  49. void update(ll l,ll r,ll a,ll p)
  50. {
  51.     if(tree[p].L==l&&tree[p].R==r)
  52.     {
  53.         tree[p].add+=a;
  54.         tree[p].sum+=(r-l+1)*a;
  55.         return ;
  56.     }
  57.     ll mid=(tree[p].L+tree[p].R)>>1;
  58.     down(p);//由于要修改下面的区间的值了，所以先把未下传的标记下传
  59.     if(r<=mid)
  60.         update(l,r,a,ls);
  61.     else if(l>mid)
  62.         update(l,r,a,rs);
  63.     else 
  64.     {
  65.         update(l,mid,a,ls);
  66.         update(mid+1,r,a,rs);
  67.     }
  68.     Up(p);//向上合并一下
  69. }
  71. ll query(ll l,ll r,ll p)
  72. {
  73.     if(l==tree[p].L&&r==tree[p].R)
  74.         return tree[p].sum;
  75.     down(p);
  76.     ll mid=tree[p].L+tree[p].R>>1;
  77.     if(r<=mid)
  78.         return query(l,r,ls);
  79.     if(l>mid)
  80.         return query(l,r,rs);
  81.     else 
  82.     {
  83.         return query(l,mid,ls)+query(mid+1,r,rs);//原因见配套notepad
  84.     }
  85. }
  86. int main()
  87. {
  88.     cin>>n>>m;
  89.     for(ll i=1;i<=n;i++)
  90.          cin>>a[i];
  91.     build(1,n,1);
  92.     while(m--)
  93.     {
  94.         ll k;
  95.         cin>>k;
  96.         if(k==1)
  97.         {
  98.             ll x,y,t;
  99.             cin>>x>>y>>t;
  100.             update(x,y,t,1);
  101.         }
  102.         else 
  103.         {
  104.             ll x,y;
  105.             cin>>x>>y;
  106.             cout<<query(x,y,1)<<endl; 
  107.         }
  108.     }
  109.     return 0;
  110. }

树状数组

用于前缀和优化

  1. #include <iostream>
  2. using namespace std ; 
  3. const int maxn = 5e5 + 9 ; 
  4. int n , m , nxt ; 
  5. int a[maxn] , c[maxn] ; 
  6. int lowbit(int x )
  7. {
  8.     return x & -x ; 
  9. }
  10. void add(int x , int d )
  11. {
  12.     for(int i = x ; i <= n ; i += lowbit(i) )
  13.         c[i] += d ; 
  14. }
  15. int sum(int x )
  16. {
  17.     int res = 0 ;
  18.     for(int i = x ; i ; i -= lowbit(i) )
  19.         res += c[i] ; 
  20.     return res ; 
  21. }
  22. signed main()
  23. {
  24.     cin >> n >> m ; 
  25.     for(int i = 1 ; i <= n ; i++ )
  26.     {
  27.         int x ; cin >> x ; 
  28.         add(i , x - nxt ) ; 
  29.         nxt = x ; 
  30.     }
  31.     while( m-- )
  32.     {
  33.         char op ;   cin >> op ; 
  34.         if(op == 'C')  
  35.         {
  36.             int l , r , d ;     cin >> l >> r >> d ; 
  37.             add(l , d ) , add(r + 1 , -d) ; 
  38.         }
  39.         else 
  40.         {
  41.             int x ; cin >> x ; 
  42.             cout << sum(x ) << '\n' ; 
  43.         }
  44.     }
  45. }

st表

st表建树 ，查询是 的

  1. //求静态区间最大值
  2. #include <bits/stdc++.h>
  4. using namespace std ;
  5. const int maxn =  1e5 + 7 , Mod = 1e9 + 7 ;
  6. int n , m , cnt ; 
  7. int lg[maxn] , st[maxn][22] ; 
  8. int read()
  9. {
  10.     int res = 0 , f = 1 ; 
  11.     char ch = getchar() ;
  12.     while(ch > '9' || ch < '0' )
  13.     {
  14.         if(ch == '-' )  f = -1 ; 
  15.         ch = getchar() ;
  16.     }
  17.     while(ch >= '0' && ch <= '9' )
  18.     {
  19.         res = res * 10 + ch - '0' ;
  20.         ch = getchar() ;
  21.     }
  22.     return res * f ; 
  23. }
  24. void build()
  25. {
  26.     for(int j = 1 ; j <= lg[n] ; j++ )
  27.         for(int i = 1 ; i <= n - (1 << j) + 1 ; i++ )
  28.             st[i][j] = max(st[i][j - 1] , st[i + (1 << j - 1)][j - 1] ) ;
  29. }
  30. int query(int l , int r )
  31. {
  32.     int mid = r - l + 1 ;
  33.     mid = lg[mid] ;
  34.     return max(st[l][mid] , st[r - (1 << mid) + 1][mid] ) ;
  35. }
  36. signed main() 
  37. {
  38.     cin >> n >> m ; 
  39.     cin >> st[1][0] ; 
  40.     for(int i = 2 ; i <= n ; i++ )
  41.     {
  42.         lg[i] = lg[i >> 1] + 1 ; 
  43.         cin >> st[i][0] ;
  44.     }
  45.     build() ;
  46.     while( m-- )
  47.     {
  48.         int l = read() , r = read() ;
  49.         cout << query(l , r ) << '\n' ; 
  50.     }
  51. }

并查集、可秩并查集

  1. #include <iostream>
  2. using namespace std ; 
  3. int fa[30007] , siz[30007] , d[30007]; 
  4. int find(int x )
  5. {
  6.     if(fa[x] == x ) return x ; 
  7.     int root = find(fa[x] ) ; 
  8.     d[x] += d[fa[x]] ; 
  9.     return fa[x] = root ; 
  10. }
  11. void merge(int x , int y )
  12. {
  13.     if(x == y ) return ;
  14.     fa[x] = y ; 
  15.     d[x] = siz[y] ; 
  16.     siz[y] += siz[x] ; 
  17. }
  18. int n , t ;
  19. signed main()
  20. {
  21.     cin >> t ; 
  22.     for(int i = 1 ; i <= 30007  ; i++ ) fa[i] = i , siz[i] = 1 ; 
  23.     while( t-- )
  24.     { 
  25.         char op ; 
  26.         int x , y ; 
  27.         cin >> op >> x >> y ;
  28.         if(op == 'M')   merge(find(x) , find(y) ) ; 
  29.         else 
  30.         {
  31.             if(find(y) != find(x) ) puts("-1") ; 
  32.             else cout << max(abs(d[y] - d[x] ) - 1 , 0 ) << '\n' ; 
  33.         }
  34.     }
  35. }
  1. //普通并查集的合并操作
  2. int find(int x )
  3. {
  4.     if(fa[x] == x ) return x ;
  5.     return fa[x] = find(fa[x] ) ;
  6. }

分块

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,block,cnt;
  4. int a[100010],addv[400],belong[100010];
  5. vector<int> vc[400];
  6. void pre()
  7. {
  8.     for(int i=1;i<=cnt;i++)
  9.     {
  10.         sort(vc[i].begin(),vc[i].end());
  11.     }
  12. }
  13. void update(int blockn)
  14. {
  15.     vc[blockn].clear();
  16.     for(int i=(blockn-1)*block+1;i<=blockn*block;i++)
  17.     {
  18.         vc[blockn].push_back(a[i]); 
  19.     } 
  20.     sort(vc[blockn].begin(),vc[blockn].end());
  21. }
  22. void modify(int l,int r,int add)
  23. {
  24.     for(int i=l;i<=min(belong[l]*block,r);i++)
  25.     {
  26.         a[i]+=add;
  27.     }
  28.     update(belong[l]);
  29.     if(belong[l]!=belong[r])
  30.     {
  31.         for(int i=(belong[r]-1)*block+1;i<=r;i++)
  32.         {
  33.             a[i]+=add; 
  34.         }
  35.         update(belong[r]);
  36.     }
  37.     for(int i=belong[l]+1;i<belong[r];i++)
  38.     {
  39.         addv[i]+=add;
  40.     }
  41. }
  42. int query(int l,int r,int maxn)
  43. {
  44.     int ans=-0x3f3f3f3f;
  45.     for(int i=l;i<=min(belong[l]*block,r);i++)
  46.     {
  47.         if(a[i]+addv[belong[i]]<maxn)
  48.         {
  49.             ans=max(ans,a[i]+addv[belong[i]]);
  50.         }
  51.     }
  52.     if(belong[l]!=belong[r])
  53.     {
  54.         for(int i=(belong[r]-1)*block+1;i<=r;i++)
  55.         {
  56.             if(a[i]+addv[belong[i]]<maxn)
  57.             {
  58.                 ans=max(ans,a[i]+addv[belong[i]]);
  59.             }
  60.         }
  61.     }
  62.     for(int i=belong[l]+1;i<belong[r];i++)
  63.     {
  64.         if(vc[i].at(0)+addv[i]>=maxn)
  65.         {
  66.             continue;
  67.         }
  68.         int k=lower_bound(vc[i].begin(),vc[i].end(),maxn-addv[i])-vc[i].begin();
  69.         ans=max(ans,vc[i].at(k-1)+addv[i]);
  70.     }
  71.     return ans;
  72. }
  73. int main()
  74. {
  75.     int n;
  76.     cin>>n;
  77.     block=sqrt(n);
  78.     for(int i=1;i<=n;i++)
  79.     {
  80.         scanf("%d",&a[i]);
  81.         belong[i]=(i-1)/block+1;
  82.         vc[belong[i]].push_back(a[i]);
  83.         if(i%block==1)
  84.         {
  85.             cnt++;
  86.         }
  87.     }
  88.     pre();
  89.     for(int i=1;i<=n;i++)
  90.     {
  91.         int opt,l,r,c;
  92.         scanf("%d%d%d%d",&opt,&l,&r,&c);
  93.         if(opt==0)
  94.         {
  95.             modify(l,r,c);
  96.         }
  97.         else
  98.         {
  99.             int k=query(l,r,c);
  100.             if(k==-0x3f3f3f3f)
  101.             {
  102.                 printf("-1\n");
  103.                 continue;
  104.             }
  105.             printf("%d\n",k);
  106.         }
  107.     }
  108. }

莫队

图论

拓扑排序

  1. void tupo()
  2. {
  3.     for(int i = 1 ; i <= n ; i++ )  if(!rd[i])  q.push(i ) ; 
  4.     while( ! q.empty() )
  5.     {
  6.         int u = q.front() ; q.pop() ;
  7.         ans.push_back(u ) ; 
  8.         for(int i = head[u] ; i ; i = ed[i].nxt )
  9.         {
  10.             int v = ed[i].to ; 
  11.             rd[v]-- ; 
  12.             if(! rd[v] )    q.push(v ) ; 
  13.         }
  14.     }
  15. }

tarjan 求强联通分量

  2. /*
  3. 见识到了，这就是缩点的板子吗？？？
  4. 整体思路：
  5.     1、将整张图跑一边tarjan将每个强连通分量都缩成一个点来处理（即将每个强连通分量的权值都加在同一个点上）
  6.         ----> 这一步用一个数组来实现
  7.     2、用拓扑序重建整张图
  8.     3、在重建的图上跑DP 
  9. */
  10. #include <bits/stdc++.h>
  11. #define maxn 101010
  12. #define int long long 
  13. using namespace std;
  14. int n,m;
  15. int cnt_tup,ans,res,cnt_ad,tot;
  16. int head[maxn],dfn[maxn],low[maxn],lian_t_k[maxn],dis_lian_t[maxn],rdd[maxn],cdd[maxn],tupo_x[maxn],dis_d[maxn],f[maxn];
  17. bool pd[maxn];
  18. vector<int>q;//tarjan 
  19. vector<int>rd[maxn],cd[maxn];
  20. vector<int>tup;//tupo
  21. inline int read()
  22. {
  23.     int x=0,f=1;
  24.     char ch=getchar();
  25.     while (ch<'0'||ch>'9')
  26.         if (ch=='-') f=-1;ch=getchar();
  27.     while (ch>='0'&&ch<='9')
  28.     {
  29.         x=x*10+ch-48;
  30.         ch=getchar();
  31.     }
  32.     return x*f;
  33. }
  35. struct node
  36. {
  37.     int nxt,frm,to;
  38. }ed[maxn*10];
  40. void add(int u,int v)
  41. {
  42.     ed[++cnt_ad].nxt=head[u];
  43.     ed[cnt_ad].frm=u;
  44.     ed[cnt_ad].to=v;
  45.     head[u]=cnt_ad;
  46. }
  48. void tarjan(int u)
  49. {
  50.     dfn[u]=low[u]=++tot;
  51.     q.push_back(u);
  52.     pd[u]=true;
  53.     for(int i=head[u];i;i=ed[i].nxt)
  54.     {
  55.         int v=ed[i].to;
  56.         if(!dfn[v])
  57.         {
  58.             tarjan(v);
  59.             low[u]=min(low[u],low[v]);
  60.         }
  61.         else if(pd[v])
  62.             low[u]=min(low[u],low[v]);
  63.     }
  64.     if(dfn[u]==low[u])
  65.     {
  66.         dis_lian_t[++res]+=dis_d[u];
  67.         pd[u]=false;
  68.         lian_t_k[u]=res;
  69.         while(q.back()!=u)
  70.         {
  71.             int w=q.back();
  72.             q.pop_back();
  73.             pd[w]=false;
  74.             dis_lian_t[res]+=dis_d[w];
  75.             lian_t_k[w]=res;    
  76.         }
  77.         q.pop_back();   
  78.     }
  80. }
  82. void topu()
  83. {
  84.     for(int i=1;i<=res;i++)
  85.     {
  86.         if(!rdd[i])
  87.             tup.push_back(i);
  88.     }
  89.     int w=tup.back();
  90.     q.pop_back();
  91.     tupo_x[++cnt_tup]=w;
  92.     for(int i=0;i<cd[w].size();i++)
  93.     {
  94.         int v=cd[w][i];
  95.         rdd[v]--;
  96.         if(!rdd[v])
  97.             tup.push_back(v);
  98.     }
  99. }
  100. signed main()
  101. {
  102.     cin>>n>>m;
  103.     for(int i=1;i<=n;i++)
  104.         cin>>dis_d[i];//dis_d[i]=read();
  105.     while(m--)
  106.     {
  107.         int u,v;
  108.         cin>>u>>v;//u=read(),v=read();
  109.         add(u,v);
  110.     }
  111. //----------------------------------> tarjan求强连通分量  
  112.     for(int i=1;i<=n;i++)
  113.         if(!dfn[i])
  114.             tarjan(i);
  115. //---------------------------------> topu重建边    
  116.     for(int i=1;i<=cnt_ad;i++)
  117.     {
  118.         int x=ed[i].frm,y=ed[i].to;
  119.         if(lian_t_k[x]!=lian_t_k[y])
  120.         {
  121.             int a,b;
  122.             a=lian_t_k[x],b=lian_t_k[y];
  123.             rdd[y]++,cdd[x]++;
  124.             cd[x].push_back(y);
  125.             rd[y].push_back(x);
  126.         }
  127.     }
  128.     topu();
  129. //---------------------------------> dp求点权最大的路径
  130.     for(int i=1;i<=res;i++)
  131.     {
  132.         int w=tupo_x[i];//tupo序的第i个数的强连通分量的编号
  133.         f[w]=dis_lian_t[w];
  134.         for(int j=0;j<rd[w].size();j++)
  135.         {
  136.             int u=rd[w][j];
  137.             f[w]=max(f[w],f[u]+dis_lian_t[w]);  
  138.         }   
  139.     } 
  140.     for(int i=1;i<=res;i++)
  141.         ans=max(f[i],ans);
  142.     cout<<ans;
  143.     return 0;
  144. }
  145. // 我*你妈ghc，你TM太卷了，闲的！写尼玛的缩点！！！ cnmd！！！ nmsl！！！

dij 跑最短路

spfa 判负环

  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. const int maxn = 1e4 + 7 ;
  4. struct node 
  5. {
  6.     int nxt , to , vis ;
  7. }ed[maxn << 1] ;
  8. int n , m , cnt ;
  9. int dis[maxn] , num[maxn] , head[maxn] ;
  10. bool pd[maxn] ;
  11. queue<int> q ; 
  12. void add(int u , int v , int w)
  13. {
  14.     ed[++cnt].nxt = head[u] ;
  15.     ed[cnt].to = v ;
  16.     ed[cnt].vis = w ;
  17.     head[u] = cnt ;
  18. }
  19. bool spfa()
  20. {
  21.     for(int i = 1 ; i <= n ; i++ )  q.push(i), pd[i] = true ;
  22.     while(! q.empty())
  23.     {
  24.         int u = q.front() ;   q.pop() ;
  25.         for(int i = head[u] ; i ; i = ed[i].nxt)
  26.         {
  27.             int v = ed[i].to ; int w = ed[i].vis ;
  28.             if(dis[v] > dis[u] + w)
  29.             {
  30.                 dis[v] = dis[u] + w ;
  31.                 q.push(v) ;     num[v] = num[u] + 1 ;
  32.                 if(num[v] > n)  
  33.                 {
  34.                     pd[v] = true ; //      puts("Yes") ;
  35.                     return 0 ;   
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     return 1 ;
  41. }
  42. signed main()
  43. {
  44.     cin >> n >> m ;
  45.     while(m--)
  46.     {
  47.         int u , v , w ;
  48.         cin >> u >> v >> w ;
  49.         add(u , v , w) ;
  50.     }
  51.     if(! spfa())    puts("Yes") ;
  52.     else puts("No") ;
  53.     return 0 ;
  54. }

Kruscal 最小生成树

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  6. const int MaxN = 200000 + 5, MaxM = 200000 + 5;
  8. int N, M;
  9. int U[MaxM], V[MaxM], W[MaxM];
  10. bool used[MaxM];
  11. int par[MaxN], Best[MaxN];
  13. void init() {
  14.     scanf("%d %d", &N, &M);
  15.     for (int i = 1; i <= M; ++i)
  16.         scanf("%d %d %d", &U[i], &V[i], &W[i]);
  17. }
  19. void init_dsu() {
  20.     for (int i = 1; i <= N; ++i)
  21.         par[i] = i;
  22. }
  24. int get_par(int x) {
  25.     if (x == par[x]) return x;
  26.     else return par[x] = get_par(par[x]);
  27. }
  29. inline bool Better(int x, int y) {
  30.     if (y == 0) return true;
  31.     if (W[x] != W[y]) return W[x] < W[y];
  32.     return x < y;
  33. }
  35. void Boruvka() {
  36.     init_dsu();
  38.     int merged = 0, sum = 0;
  40.     bool update = true;
  41.     while (update) {
  42.         update = false;
  43.         memset(Best, 0, sizeof Best);
  45.         for (int i = 1; i <= M; ++i) {
  46.             if (used[i] == true) continue;
  47.             int p = get_par(U[i]), q = get_par(V[i]);
  48.             if (p == q) continue;
  50.             if (Better(i, Best[p]) == true) Best[p] = i;
  51.             if (Better(i, Best[q]) == true) Best[q] = i;
  52.         }
  54.         for (int i = 1; i <= N; ++i)
  55.             if (Best[i] != 0 && used[Best[i]] == false) {
  56.                 update = true;
  57.                 merged++; sum += W[Best[i]];
  58.                 used[Best[i]] = true;
  59.                 par[get_par(U[Best[i]])] = get_par(V[Best[i]]);
  60.             }
  61.     }
  63.     if (merged == N - 1) printf("%d\n", sum);
  64.     else puts("impossible");
  65. }
  67. int main() {
  68.     init();
  69.     Boruvka();
  70.     return 0;
  71. }

prim 最小生成树

  1. int  n , m , tot , cnt , ans ; 
  2. struct node 
  3. {
  4.     int to , nxt , dis ; 
  5. }ed[maxn] ; 
  6. int dis[maxn] , head[maxn] ;
  7. bool pd[maxn] ; 
  8. void add(int u , int v , int w)
  9. {
  10.     ed[++cnt].to = v ;
  11.     ed[cnt].dis = w ; 
  12.     ed[cnt].nxt = head[u] ; 
  13.     head[u] = cnt ; 
  14. }
  15. priority_queue<pii , vector<pii> , greater<pii> > q ; 
  16. int prim()
  17. {
  18.     int res = 0 ; 
  19.     memset(dis , 0x3f , sizeof(dis)) ; 
  20.     dis[1] = 0 ;    q.push({0 , 1}) ;
  21.     while(! q.empty())
  22.     {
  23.         int u = q.top().second , val = q.top().first ; q.pop() ;
  24.         if(pd[u])   continue ;  pd[u] = true ;  res += val ;    tot++ ;  
  25.         for(int i = head[u] ; i ; i = ed[i].nxt )
  26.         {
  27.             int v = ed[i].to ;
  28.             if(dis[v] > ed[i].dis)
  29.             {
  30.             //  orz ;
  31.                 dis[v] = ed[i].dis ; 
  32.                /* if(!pd[v])
  33.                      q.push({dis[v] , v}) ;*/
  34.                 q.push({ dis[v] , ed[i].to}) ;
  35.             }
  36.         }
  37.     }
  38.     if(tot != n)    return 0x3f3f3f3f ; 
  39.     return res ;
  40. }
  41. signed main()
  42. {
  43.     cin >> n >> m ;
  44.     while( m-- )
  45.     {
  46.         int u , v , w ; 
  47.         cin  >> u >> v >> w ;
  48.         add(u , v , w) ;               
  49.         add(v , u , w) ; 
  50.     }
  51.     ans =  prim() ; 
  52.     //cout << tot  ; 
  53.     if(ans == 0x3f3f3f3f) puts("impossible") ;
  54.     else cout << ans ; 
  55.     return 0 ; 
  56. }

差分约束

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。FJ 有编号为 的 头奶牛 。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 。

请计算：如果满足上述所有条件， 号奶牛和 号奶牛之间的距离最大为多少

输入格式

第一行：三个整数 ，用空格分隔。

第 行：每行三个整数 ，用空格分隔，表示 号奶牛与 号奶牛之间的距离须 。保证 .

第 行：每行三个整数 ，用空格分隔，表示 号奶牛与 号奶牛之间的距离须 。保证 .

输出格式

一行，一个整数。如果没有合法方案，输出 -1. 如果有合法方案，但 号奶牛可以与 号奶牛相距无穷远，输出 -2. 否则，输出 号奶牛与 号奶牛间的最大距离。

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define orz cout << "xyc_ak_ioi"  
  4. using namespace std ;
  5. const int maxn = 1e6 + 7 ;  const int MAX = 1e5 + 7 ;
  6. int n , m1 , m2 , cnt , ans ;
  7. int dis[maxn] , head[maxn] , num[maxn] ;
  8. bool pd[maxn] ;
  9. inline int read()
  10. {
  11.     int x = 0 , f = 1 ;
  12.     char ch = getchar() ;
  13.     while(ch < '0' || ch > '9' )
  14.     {
  15.         if(ch == '-') f = -1 ;
  16.         ch = getchar() ;
  17.     }
  18.     while(ch >= '0' && ch <= '9')
  19.     {
  20.         x = x * 10 + ch - 48 ;
  21.         ch = getchar() ;
  22.     }
  23.     return x * f ;
  24. }
  25. struct node
  26. {
  27.     int to , nxt , vis ;
  28. }    ed[maxn << 1] ;
  29. void add(int u , int v , int dis)
  30. {
  31.     ed[++cnt].to = v ; 
  32.     ed[cnt].vis = dis ;
  33.     ed[cnt].nxt = head[u] ; 
  34.     head[u] = cnt ;
  35. }
  36. bool spfa(int k)
  37. {
  38.     queue<int> q ;
  39.     memset(dis , 0x3f , sizeof(dis)) ;
  40.     memset(pd , 0 , sizeof(pd)) ;
  41.     memset(num , 0 , sizeof(num)) ;
  42.     for(int i = 1 ; i <= k ; i++ )
  43.     {
  44.         pd[i] = true ;    q.push(i) ;
  45.         dis[i] = 0 ;
  46.     }
  47.     /*q.push(1) ; 
  48.     dis[1] = 0 ;    pd[1] = true ;*/
  49.     while(!q.empty())
  50.     {
  51.         //orz ;
  52.         int u = q.front() ; q.pop() ;
  53.         pd[u] = false ;    
  54.         for(int i = head[u] ; i ; i = ed[i].nxt)
  55.         {
  56.             int v = ed[i].to , val = ed[i].vis ;
  57.             if(dis[v] > dis[u] + val)
  58.             {
  59.                 dis[v] = dis[u] + val ;
  60.                 num[v] = num[u] + 1 ;
  61.                 if(num[v] > n)    return false ;
  62.                 if(!pd[v])    q.push(v) , pd[v] = true ;
  63.             }
  64.         }
  65.     }
  66.     return true ;
  67. }
  68. signed main()
  69. {
  70.     cin >> n >> m1 >> m2 ;
  71.    // add(0 , 1 , 0x3f3f3f) ;
  72.     for(int i = 2 ; i <= n ; i++ )  add(i , i - 1 , 0) ;
  73.     while( m1-- )
  74.     {
  75.         int a = read() , b = read() , dis = read() ;
  76.         add(a , b , dis) ;
  77.     }
  78.     while( m2-- )
  79.     {
  80.         int a = read() , b = read() , dis = read() ;
  81.         add(b , a , -dis) ;
  82.     }
  83.     if(! spfa(n))    puts("-1") ;
  84.     else
  85.     {
  86.         spfa(1) ;
  87.         if(dis[n] >= 0x3f3f3f3f)    cout << "-2" ;
  88.         else cout << dis[n] ;
  89.     }
  90.     return 0 ; 
  91. }

二分图

1、二分图的判定

  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3. const int maxn = 1e5 + 7 ; 
  4. struct node 
  5. {
  6.     int to , nxt ; 
  7. } ed[maxn << 1 ] ; 
  8. int clr[maxn] , head[maxn] ; 
  9. int cnt , n , m ;
  10. void add(int u , int v )
  11. {
  12.     ed[++cnt] = { v , head[u] } ; 
  13.     head[u] = cnt ; 
  14. }
  15. bool dfs(int u , int op )
  16. {
  17.     clr[u] = op ; 
  18.     for(int i = head[u] ; i ; i = ed[i].nxt )
  19.     {
  20.         int v = ed[i].to ;
  21.         if(clr[v] == -1 )
  22.         {
  23.             if(! dfs(v , !op))  return false  ;
  24.         }
  25.         else if(clr[v] == op)   return false ; 
  26.     }
  27.     return true ; 
  28. }
  30. signed main()
  31. {
  32.     cin >> n >> m ; 
  33.     while( m-- )
  34.     {
  35.         int u , v ; 
  36.         cin >> u >> v ; 
  37.         add(u , v ) ;   add( v , u ) ; 
  38.     }
  39.     memset(clr , -1 , sizeof clr ) ; 
  40.     for(int i = 1 ; i <= n ; i++ )
  41.     {
  42.         if(clr[i] == -1 )
  43.         {
  44.             int flg = dfs(i , 0) ;
  45.             if(! flg)
  46.             {
  47.                 puts("No") ; 
  48.                 return 0 ; 
  49.             }
  50.         }
  51.     }
  52.     cout << "Yes" ; 
  53.     return 0 ; 
  54. }

2、二分图的最大匹配

  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3. const int maxn = 1e5 + 7 ; 
  4. int n , m , cnt , ans , N ; 
  5. int hus[501] , head[501] ;
  6. bool pd[501] ; 
  7. struct node 
  8. {
  9.     int to , nxt ; 
  10. } ed[maxn] ;
  11. void add(int u , int v )
  12. {
  13.     ed[++cnt] = { v , head[u] } ;
  14.     head[u] = cnt ; 
  15. }
  16. bool find(int u )
  17. {
  18.     for(int i = head[u] ; i ; i = ed[i].nxt )
  19.     {
  20.         int v = ed[i].to ; 
  21.         if(!pd[v])
  22.         {
  23.             pd[v] = true ; 
  24.             if(! hus[v] || find(hus[v]))
  25.             {
  26.                 hus[v] = u ; 
  27.                 return true ;
  28.             }
  29.         }
  30.     }
  31.     return false ; 
  32. }
  33. signed main()
  34. {
  35.     cin >> n >> N >> m ; 
  36.     while( m-- )
  37.     {
  38.         int u , v ; 
  39.         cin >> u >> v ;     add(u , v ) ; 
  40.     }
  41.     for(int i = 1 ; i <= n ; i++ )
  42.     {
  43.         memset(pd , false , sizeof pd ) ; 
  44.         if(find(i) ) ans++ ;
  45.     }
  46.     cout << ans ;
  47.     return 0 ; 
  48. }

数论

试除法判断质数

  1. bool check(int x )//艹，丢人了。这题居然看了模板……！
  2. {
  3.     if(x < 2 )  return false ; 
  4.     for(int i = 2 ; i <= x / i ; i++ )
  5.     {
  6.         if(x % i )  continue ;
  7.         else return false ; 
  8.     }
  9.     return true ; 
  10. }

分解质因数

  1. void check(int n )
  2. {
  3.     for(int i = 2 ; i <= n / i ; i++ )
  4.     {
  5.         int now = 0 ;
  6.         //int x = n ; 
  7.         //if(n % i == 0 ) 
  8. //      cout << i << " " ; 
  9.         while(n % i == 0 )
  10.         {
  11.             now++ ; 
  12.             n /= i ; 
  13.         }
  14.         if(now )    cout << i << " " << now << '\n' ;
  15.     }
  16.     if(n > 1)   cout << n << " " << 1 << '\n' ;
  17. }

试除法求约数

  1. void check(int x )
  2. {
  3.     q.clear() ; 
  4.     for(int i = 1 ; i <= x / i ; i++ )
  5.     {
  6.         if(x % i == 0 )
  7.         {
  8.             q.push_back(i) ; 
  9.             if(x / i != i)  q.push_back(x / i ) ; 
  10.         }
  11.     }
  12.     sort(q.begin() , q.end()) ; 
  13.     for(auto i : q )
  14.     {
  15.         cout << i << " "; 
  16.     }
  17.     puts("") ; 
  18. }

线性筛

  1. void erlu()
  2. {
  3.     for(int i = 2 ; i <= n ; i++ )
  4.     {
  5.         if(! pd[i] )    prime[++cnt] = i ; 
  6.         for(int j = 1 ; prime[j] * i <= n ; j++ )
  7.         {
  8.             pd[prime[j] * i ]  = true ; 
  9.             if(i % prime[j] == 0 )  break ; 
  10.         }
  11.     }
  12. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注