小田的acm模板仓库

mac2022-06-30 77

我们已经退无可退了，坚持下去就是胜利！线段树区间查最大最小值：

#include <bits/stdc++.h> using namespace std; #define limit 200000 + 5//代表总大小，开足够大小数组 #define INF 0x3f3f3f3f typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//用getchar方法读取输入方便计算 /**** 线段树模板，在poj3264中的运用，记住就好 * */ struct Node{ int L, R;//分别代表所储存区间的左和右边 int MIN, MAX;//当前区间的最大值和最小值 int mid(){ return L + (R - L) / 2; } Node():L(0), R(0){}//无参构造方法 }; Node tree[limit];//构建静态链表 int globMax = -INF, globMin = INF;//记录全局节点 void build(int root, int L, int R) {//用这个方法建树 tree[root].L = L;//左右分别赋值 tree[root].R = R; tree[root].MIN = INF; tree[root].MAX = -INF;//此处之所以不在构造方法里用BMI进行赋值主要是考虑到区间的统一性，显然前者无法达到我们需要的 if (L != R) { //二分建树，在此二分的思想不多说了 build(root * 2 + 1, L, L + (R - L) / 2);//这样做主要是防止溢出，java早期即存在此问题 build(root * 2 + 2, L + (R - L) / 2 + 1, R);//递归建树 } } void insertElement(int root ,int interval, int element){//用来插入元素并更新维护数组 if(tree[root].L == tree[root].R){ //左右相等即代表此时的区间不可继续细分，所以未曾更改，自然而然此时插入的数字便可以直接操作 tree[root].MIN = tree[root].MAX = element;//因为没有操作过，所以不用管直接insert return;//这一步实际上就是划分的最大限度，之后自然不可能继续下去，二分结束，维护完成 } tree[root].MIN = min (tree[root].MIN, element); tree[root].MAX = max(tree[root].MAX, element); if(interval <= tree[root].mid()){ insertElement(root * 2 + 1, interval, element); }else{ insertElement(root * 2 + 2, interval, element);//递归查找需要插入的区间 } } void query(int root, int start, int end){ if(tree[root].MIN >= globMin && tree[root].MAX <= globMax){ return;//因为此时已经不满足条件了，那就停止不用更改任何有关信息 } if(tree[root].L == start && tree[root].R == end){ //已经相当于所覆盖的区间了，所以不用再查下去了 globMax = max(globMax, tree[root].MAX); globMin = min(globMin, tree[root].MIN);//找出最大值和最小值 return; } if(end <= tree[root].mid()){//二分法，在此不多叙述 query(root * 2 + 1, start,end); }else if(start > tree[root].mid()){ query(root * 2 + 2, start,end); }else{ query(root * 2 + 1 ,start , tree[root].mid());//区间范围不合理，根本查不到 query(root * 2 + 2, tree[root].mid() + 1, end);//重新开始新的查找 } } int n, q;//两个变量 int main(){ scanf("%d%d",&n,&q);//读取输入 build(0,1,n);//建立区间总大小的树 for (int i = 1; i <= n; ++i) { int e; scanf("%d", &e);//读入输入 insertElement(0, i, e);//这一点是因为要一直更新前面的情况所以直接从0到i，i还是采用1-based下标 } for(int i = 0 ; i < q; ++i){ int s,e;//临时变量起始位置（区间） scanf("%d%d", &s,&e);//读入输入 globMin = INF; globMax = -INF;//还原初始设置 query(0,s,e); printf("%d\n",globMax - globMin);//身高差,大功告成，我太累了，明天还要上课，就到这里了 } return 0; }

线段树区间单点更新求和：

#include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <math.h> #include <cstdio> using namespace std; #define limit 1200000 + 5 #define INF 0x3f3f3f3f #define lowbit(i) i&(-i)//定义lowbit函数 #define EPS 1e-6 #define ff(a) printf("%d\n",a ); typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//快读 struct Node{ int L,R; ll inc ,sum; Node() = default; int mid(){ return L + (R - L) / 2; } }tree[limit]; void pushdown(int root){ if(tree[root].inc){ tree[root * 2 + 1].inc += tree[root].inc; tree[root * 2 + 2].inc += tree[root].inc;//增量 tree[root].sum += (tree[root].R - tree[root].L + 1) * tree[root].inc; tree[root].inc = 0;//向下劝退 } } void pushup(int root){ tree[root].sum = tree[root * 2 + 1].sum + tree[root * 2 + 2].sum;//左右子树向上传递 } void build(int root, int L ,int R){ tree[root].L = L; tree[root].R = R; tree[root].sum = 0; tree[root].inc = 0; int mid = tree[root].mid(); if(L != R){ build(root * 2 + 1 , L ,mid);//建立左子树 build(root * 2 + 2 , mid + 1 , R);//右子树 } } void insert(int root ,int pos ,ll val){ if(tree[root].L == pos && tree[root].R == pos){ tree[root].sum = val; return; } pushdown(root); int mid = tree[root].mid(); if(pos <= mid){ insert(root * 2 + 1 ,pos, val); }else{ insert(root * 2 + 2 , pos, val); } pushup(root);//一层层回溯 } void update(int root ,int vs ,int ve ,int val){ //区间更新 if(vs > ve) swap(vs,ve); if(tree[root].L == vs && tree[root].R == ve){ tree[root].inc += val; return; } tree[root].sum += (ve - vs + 1) * val;//此行增量 //tree[root].sum += (tree[root].R - tree[root].L + 1) * tree[root].inc; int mid = tree[root].mid(); if(ve <= mid){ update(root * 2 + 1 , vs , ve , val); }else if(vs > mid){ update(root * 2 + 2 , vs , ve ,val); }else{ update(root * 2 + 1, vs , mid ,val); update(root * 2 + 2 , mid + 1 , ve , val); } //pushup(root);//一步步回溯 } ll query(int root ,int vs ,int ve){ if(vs > ve) swap(vs,ve); if(tree[root].L == vs && tree[root].R == ve){ return tree[root].sum + (ve - vs + 1) * tree[root].inc; } pushdown(root); int mid = tree[root].mid(); if(ve <= mid){ return query(root * 2 + 1, vs ,ve); }else if(vs > mid){ return query(root * 2 + 2 , vs ,ve); }else{ return query(root * 2 + 1, vs ,mid) + query(root * 2 + 2 , mid + 1 , ve); } } int n,m; int main(){ while(scanf("%d%d" , &n, &m) == 2) { int root = 0; char cmd[10]; build(root , 1, n); int a1, b; for(int i = 1; i <= n ; ++i){ int ee; scanf("%d" , &ee); insert(root ,i ,ee); } while (m--) { scanf("%s%d%d", &cmd[0], &a1, &b); if (cmd[0] == 'C') { ll c; scanf("%lld",&c); update(root ,a1, b , c); } else { printf("%lld\n",query(root ,a1,b)); } } } return 0; }

线段树区间合并：

#include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <math.h> #include <cstdio> using namespace std; #define limit 1000000 + 5//防止溢出 #define INF 0x3f3f3f3f #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-6 #define ff(a) printf("%d\n",a ); typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//快读 int n; struct Node{ int L , R ,MAX, MIN; int mid(){ return L + (R - L) / 2; } }tree[limit]; void build(int root ,int L ,int R){ tree[root].L = L; tree[root].R = R; tree[root].MAX = 0; tree[root].MIN = n + 1; int mid = tree[root].mid(); if(L != R){ build(root * 2 + 1, L , mid); build(root * 2 + 2 , mid + 1, R); } } void updateMax(int root , int pos ,int val){ if(tree[root].L == pos && pos == tree[root].R){ tree[root].MAX = val; return; } int mid = tree[root].mid(); if(pos <= mid){ updateMax(root * 2 + 1 , pos ,val); }else{ updateMax(root * 2 + 2, pos ,val); } tree[root].MAX = max(tree[root * 2 + 1].MAX, tree[root * 2 + 2].MAX); //tree[root].MAX = max(tree[root].MAX, val); } void updateMin(int root , int pos ,int val){ if(tree[root].L == pos && pos == tree[root].R){ tree[root].MIN = val; return; } int mid = tree[root].mid(); if(pos <= mid){ updateMin(root * 2 + 1 , pos ,val); }else{ updateMin(root * 2 + 2, pos ,val); } tree[root].MIN = min(tree[root * 2 + 1].MIN, tree[root * 2 + 2].MIN); //tree[root].MIN = min(tree[root].MIN , val); } int queryMax(int root ,int vs ,int ve){ if(tree[root].L == vs && ve == tree[root].R){ return tree[root].MAX; } int mid = tree[root].mid(); if(ve <= mid){ return queryMax(root * 2 + 1, vs ,ve); }else if(vs > mid){ return queryMax(root * 2 + 2, vs ,ve); }else{ return max(queryMax(root * 2 + 1, vs ,mid), queryMax(root * 2 + 2 , mid + 1, ve)); } } int queryMin(int root ,int vs ,int ve){ if(tree[root].L == vs && ve == tree[root].R){ return tree[root].MIN; } int mid = tree[root].mid(); if(ve <= mid){ return queryMin(root * 2 + 1, vs ,ve); }else if(vs > mid){ return queryMin(root * 2 + 2, vs ,ve); }else{ return min(queryMin(root * 2 + 1, vs ,mid), queryMin(root * 2 + 2 , mid + 1, ve)); } } int m; int main(){ //freopen("C:\\Users\\administrator01\\CLionProjects\\untitled13\\data.txt", "rt" , stdin); while(scanf("%d%d" , &n, &m) == 2){ const int root = 0; build(root ,1, n); stack<int>history; int opt; char cmd[10]; for(int i = 0 ; i < m ; ++i) { scanf("%s" ,&cmd[0]); if (cmd[0] == 'D') { scanf("%d", &opt); updateMax(root, opt, opt); updateMin(root, opt, opt); history.push(opt); } else if (cmd[0] == 'R') { updateMin(root, history.top(), n + 1); updateMax(root, history.top(), 0); history.pop(); } else { scanf("%d", &opt); int maxx = queryMax(root, 1, opt); int minn = queryMin(root, opt, n); if(minn == maxx)ff(0) else printf("%d\n", minn - maxx - 1); } } } return 0; }

线段树区间集体更新：

#include <bits/stdc++.h> using namespace std; #define limit 1000000 + 5//防止溢出 #define INF 0x3f3f3f3f #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-6 #define ff(a) printf("%d\n",a ); typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//快读 struct Node{ int L, R , inc, sum; int mid(){ return L + (R - L) / 2; } }tree[limit]; void build(int root ,int L ,int R){ tree[root].L = L; tree[root].R = R; tree[root].sum = R - L + 1;//初始化为区间长度 tree[root].inc = 1; int mid = tree[root].mid(); if(L != R){ build(root * 2 + 1, L, mid); build(root * 2 + 2, mid + 1, R); } } void update(int root,int vs ,int ve ,int val){ if(tree[root].L == vs && tree[root].R == ve){ tree[root].sum = (ve - vs + 1) * val; tree[root].inc = val; return; } if(tree[root].inc){ tree[root * 2 + 1].inc = tree[root * 2 + 2].inc = tree[root].inc; tree[root * 2 + 1].sum = (tree[root * 2 + 1].R - tree[root * 2 + 1].L + 1) * tree[root].inc;//更新迭代 tree[root * 2 + 2].sum = (tree[root * 2 + 2].R - tree[root * 2 + 2].L + 1) * tree[root * 2 + 2].inc;//更新迭代 tree[root].inc = 0;//归位 } int mid = tree[root].mid(); if(ve <= mid){ update(root * 2 + 1 , vs ,ve , val); }else if(vs > mid){ update(root * 2 + 2, vs , ve, val); }else{ update(root * 2 + 1 ,vs ,mid , val); update(root * 2 + 2 , mid + 1 , ve ,val); } tree[root].sum = tree[root * 2 + 1].sum + tree[root * 2 + 2].sum;//一层层传上来 } int query(int root ,int vs ,int ve){ if(tree[root].L == vs && tree[root].L == ve){ return tree[root].sum ;//+ (ve - vs + 1) * tree[root].inc; } if(tree[root].inc){ tree[root * 2 + 1].inc = tree[root * 2 + 2].inc = tree[root].inc; tree[root * 2 + 1].sum = (tree[root * 2 + 1].R - tree[root * 2 + 1].L + 1) * tree[root].inc;//更新迭代 tree[root * 2 + 2].sum = (tree[root * 2 + 2].R - tree[root * 2 + 2].L + 1) * tree[root * 2 + 2].inc;//更新迭代 tree[root].inc = 0;//归位 } int mid = tree[root].mid(); if(ve <= mid){ return query(root * 2 + 1, vs ,ve); }else if(vs > mid){ return query(root * 2 + 2, vs ,ve); }else{ return query(root * 2 + 1, vs , mid) + query(root * 2 + 2 , mid + 1, ve); } }

spfa模板算法：

#include <bits/stdc++.h> using namespace std; #define limit 10000 + 5 #define INF 0x3f3f3f3f #define EPS 1e-6 typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//读输入优化 int kase; struct vertex{ int x; vertex() = default; vertex(int xx):x(xx){} }; struct edge{ int to, cost; edge() = default; edge( int tt,int cc):to(tt),cost(cc){}//定义变量 }; vector<vector<edge >>v;//建立邻接表 int n , m,start; int dist[limit],update[limit],vis[limit]; int spfa(int s){ memset(dist , INF, sizeof(dist)); memset(update, 0 , sizeof(update)); memset(vis, 0 , sizeof(vis)); vis[s] = 1; dist[s] = 0;//自己到自己是0 queue<int>q; q.push(s); while(!q.empty()){ int vs = q.front(); q.pop(); vis[vs] = 0; for(int i = 0 ; i < v[vs].size() ; ++i){ int ve = v[vs][i].to , weight = v[vs][i].cost; if(dist[vs] != INF && dist[vs] + weight < dist[ve]){ dist[ve] = dist[vs] + weight; update[ve]++; if(!vis[ve]){ vis[ve] = 1; q.push(ve); } if(update[ve] >= n)return 0; } } } return 1; }//spfa算法写好了 int main(){//最短路 scanf("%d",&kase); while(kase--){ scanf("%d%d%d",&n,&m,&start); v.resize(n + 1); for(int i = 1 ; i <= m ; ++i){ int from ,to , weight; scanf("%d%d%d",&from, &to, &weight); v[from].push_back(edge(to , weight));//推入邻接表 } if(!spfa(start)){ //代表有负权回路 printf("Error\n"); }else{ for(int i = 1 ; i <= n ; ++i){ if(dist[i] == INF) printf("null "); else printf("%d ",dist[i]); } printf("\n"); } v.clear(); } return 0; }

dijkstra模板算法：

#include <bits/stdc++.h> using namespace std; #define limit 150000 + 5//代表总大小，开足够大小数组 #define INF 0x3f3f33f typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//用getchar方法读取输入方便计算 struct edge{ int destination;//表示这条边的终点 int weight; edge():destination(0), weight(0){}//这里记得一定要初始化为0，最开始写的是0xff，后来一直segfault,换成0就可以了 edge(int dd, int ww): destination(dd), weight(ww){} bool operator<(const edge &rhs)const{ return weight > rhs.weight;//因为优先队列是升序，我们需要降序，所以自己重载定义一个运算符 } }; int visited[limit];//visited数组用来存放每个点是否被遍历过的状态 vector< vector <edge> >v;//邻接表,实际相当于一个G[][]二维数组，和网络流的题一样 int n, m;//用来存放点和边 int main(){ scanf("%d%d" ,&n, &m); priority_queue<edge>q;//优先队列插入方法时间复杂度为O（N）,因为这点需要动态求最大最小边，所以可以以牺牲一部分时间来换取升序排列 edge shortest;//定义成全局变量用于获得最短路的权值 v.clear(); v.resize(n + 1);//重新规划大小 memset(visited, 0 , sizeof(visited));//清空全部都为unvisited for(int i = 1 ; i <= m;++i){ int from, to ,weight;//接受信息 scanf("%d%d%d", &from, &to, &weight); shortest.destination = to; shortest.weight = weight; v[from].push_back(shortest);//推入邻接表中 } shortest.destination = 1;//源点为第一条边 shortest.weight = 0;//自己到自己肯定是0 q.push(shortest);//推入 while(!q.empty()){ shortest = q.top();//一直更新shortest q.pop();//走你 if(visited[shortest.destination]){ //如果找过了，因为利用了贪心法，所以直接跳过，用短路运算符加速 continue;//不找了 } visited[shortest.destination] = 1;//找过了 if(shortest.destination == n){ //找到这么多条边了不需要再找了 break; } for(int i = 0 ; i < v[shortest.destination].size();++i){ //遍历邻接表 edge tmp; tmp.destination = v[shortest.destination][i].destination;//这一步是要找到可行的边 if(visited[tmp.weight]) continue;//这点已经求出 tmp.weight = shortest.weight + v[shortest.destination][i].weight;//加上总权值之和，因为贪心算法和优先队列 //tmp的weight是从边权值最小开始查起的，所以weight最小一定是成立的 q.push(tmp);//下一次寻找 } } cout<<shortest.weight<<endl;//最短路权值已经求出 return 0; }

dinic最大流算法：

#include <bits/stdc++.h> using namespace std; #define limit 200 + 5 #define INF 0x3f3f3f3f void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//读输入 /*** *图论算法之最大最小流dinic算法在POJ1273上的运用,ACM冲鸭！！！！！ */ int G[limit][limit]; int s,e,f;//分别表示起点，终点和流量 int visited[limit], level[limit]; bool countLayer(){ int layer = 0; deque<int>q;//当做栈使用的q memset(level, 0xff , sizeof(level));//初始化为-1表示没有遍历过 level[1] = 0;//表示初始分层 q.push_back(1);//推入栈中以开始编号 while(!q.empty()){ int vertices = q.front();//栈的性质是LIFO,在此不在多解释,vertices代表是发展的节点 q.pop_front();//相当于stack的pop方法 for(int i = 1 ; i <= e; ++i){ if(G[vertices][i] > 0 && level[i] == -1){ //代表如果这点和下一点之间有流量而且没有被分过层 level[i] = level[vertices] + 1;//分层,从开始开发的点到上一个节点的距离层数 + 1 if(i == e){ //i == e 代表分到了汇点，所以直接完成整个步骤 return true; }else{ q.push_back(i);//继续探索下一个节点 } } } } return false; } int dinic(){ //注入灵魂 int i, start, maxFlow = 0;//i在此处需要用作判断是否已经到达汇点，所以不能在for循环里面定义 //emm别问我为什么要定义start这个无用变量，郭神是这样说的，这样写的，所以为了尊重原作还是定义一下吧 deque<int>q;//定义一个双向队列当成栈使用，什么？这里其实是利用了deque是动态数组实现，有[]这个运算符可以在O(1)时间内访问任意一个元素 //同时又具有栈的性质，即后进先出，所以在此处选用双向队列 while(countLayer()){//只要还能分层，就继续这个循环 q.push_back(1);//原作上郭神是用了1-based 下标，我个人喜欢用0-based下标，但在icpc中这样有诸多不便，所以还是视情况而定 memset(visited , 0, sizeof(visited));//别问，问就是没来过 visited[1] = 1;//将原点标为visited，这一步骤和dfs还有bfs类似 while(!q.empty()){ int n = q.back();//这一步为什么是从后面取点等下会讲 if(n == e){ //e为代表汇点的全局变量，所以此处为碰到汇点了怎么办 int minC = 999999;//设为无穷大方便比较出最小值，INF最好定义成0x3f3f3f3f而不是0x7fffff int minV;//minV记录最小流出现的节点 for(i = 1 ; i < q.size(); i++){ int vs = q[i - 1];//记录起始点 int ve = q[i];//记录终点 if(G[vs][ve] > 0){ if(minC > G[vs][ve]){ minC = G[vs][ve];//如果该增光路径仍然有剩余流量，而且比minC小，那么记住它 minV = vs;//记录最小流节点出处 } } } maxFlow += minC;//单位最大流为各个增广路径的最小流（卡着脖子），所以此处要加上 for(i = 1 ; i < q.size();++i){ int vs = q[i - 1];//记录起始点 int ve = q[i];//记录终点 G[vs][ve] -= minC; G[ve][vs] += minC;//添加反向边，表示此处流量已经被计算过无需重复计算 } while(!q.empty() && q.back() != minV){ visited[q.back()] = 0;//回溯，因为要从上一个最小流节点继续探索，所以需要恢复这之前的一切 q.pop_back(); } }else{ for(i = 1 ; i <= e ; ++i){ if(G[n][i] > 0 && level[i] == level[n] + 1 && !visited[i]){//这一点需要符合三个条件 //第一是这一条边仍然有剩余流量，再就是这一点是选定开发节点的下一层，并且没有被访问过 visited[i] = 1;//表示访问过了 q.push_back(i);//把这一点当做下一次dfs的对象 break;//找到就歇菜了，如果不及时停止的话会出现大量重复访问的情况拉低效率 } } if(i > e){ q.pop_back();//如果i == e了就代表在这之前也没有找到一个合适的点，意味着下一次是死胡同， //所以进行退栈回溯处理 } } } } return maxFlow;;//嘿嘿终于找到了 } int main(){ while(scanf("%d%d", &s, &e) == 2){ memset(G,0, sizeof(G));//初始化数组存边 int vs, ve ,flow; for(int i = 0 ; i < s; ++i){ scanf("%d%d%d" , &vs, &ve,&flow); G[vs][ve] += flow;//因为可能存在共同边，所以在此直接合并为一条边避免麻烦 } printf("%d\n", dinic());//大功告成啦！hhhhh } return 0; }

树状数组区间求和更新：

遇到求最值的问题首先用线段树吧还是拓扑排序算法模板：

#include <bits/stdc++.h> using namespace std; #define limit 300 + 5//代表总大小，开足够大小数组 #define INF 0x3f3f3f3f typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; } /*** * 拓扑排序 * poj1094 的运用 * @return */ vector<vector <int> >v;//建立邻接表 void init(){ for(int i = 0 ; i < v.size() ; ++i){ v[i].clear();//清空 } } int n;//读取输入 int start;//确定入度为0的点 int status[limit]; int main(){ scanf("%d", &n); start = 0;//归零 init(); vector<int>ret;//记录排序 memset(status, 0 , sizeof(status)); memset(vis,0, sizeof(vis)); v.resize(n + 1);//变成和N一样的大小,开辟邻接表空间 for(int i = 1 ; i <= n ; ++i){ int p;//接受输入 int cnt = 0; while(scanf("%d",&p) == 1 && p){ v[i].push_back(p);//储存在邻接表里面 status[p]++;//记录入度 ++cnt;//记录入度 } }//建立邻接表而且记录了入度为0的点 queue<int>q; for(int i = 1 ; i <= n; ++i){ if(!status[i])q.push(i); } int cnt = 0;//再次归零 while(!q.empty()){ int vs = q.front(); vis[++cnt] = vs;//增加点数 q.pop();//退栈处理 for(int i = 0 ; i < v[vs].size() ; ++i){//拓扑排序 status[v[vs][i]]--;//入度减少,删边 if(!status[v[vs][i]])//入度为0就推送 q.push(v[vs][i]); } } for(int i = 1 ; i <= n ; ++i){ printf("%d ",vis[i]); } printf("\n"); return 0; }

修改并查集模板：

#include <bits/stdc++.h> using namespace std; #define limit 1000000 + 5//代表总大小，开足够大小数组 #define INF 0x3f3f3f3f #define EPS 1e-6 typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; } int parent[limit],sum[limit], under[limit];//sum表示总和，under代表第i个底下的数量 int getRoot(int a){//代表是敌人的时候的操作 if(parent[a] == a) return a; int s = getRoot(parent[a]); under[a] += under[parent[a]];//代表底下的那个加一 parent[a] = s; return parent[a]; }//代表属不属于同一个连通分量 void merge(int a , int b){ int root1 = getRoot(a); int root2 = getRoot(b); if(root1 == root2) return; parent[root2] = root1;//更改root under[root2] = sum[root1];//先加再更改,所以还没有更新，需要在询问的时候进行路径压缩然后询问 sum[root1] += sum[root2]; } bool query(int a, int b){ int root1 = getRoot(a); int root2 = getRoot(b); return root1 == root2;//不需要属于一个连通分量 } int n; int main(){ scanf("%d",&n); for(int i = 0; i <= n ; ++i){ parent[i] = i; sum[i] = 1; under[i] = 0; } char ch[20]; for(int i = 1; i <= n ; ++i){ int a, b; scanf("%s",&ch); if(ch[0] == 'M'){ scanf("%d%d",&a, &b); merge(b,a); }else{ scanf("%d",&a); getRoot(a); printf("%d\n", under[a]); } } return 0; }

普通并查集模板：

int parent[limit]; int getRoot(int a){//代表是敌人的时候的操作 if(parent[a] == a) return a; parent[a] = getRoot(parent[a]); return parent[a]; }//代表属不属于同一个连通分量 void merge(int a , int b){ int root1 = getRoot(a); int root2 = getRoot(b); if(root1 == root2){ return; } parent[root2] = root1;//更改root } bool query(int a, int b){ int root1 = getRoot(a); int root2 = getRoot(b); return root1 == root2;//不需要属于一个连通分量 }

多源最短路佛洛依德算法：

#include <stdio.h> #include <iostream> #include <string.h> #include <vector> #include <algorithm> using namespace std; #define limit 11200 + 5 #define INF 0x3f3f3f3f #define EPS 1e-6 void read(int &x){ char ch = getchar();x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; }//读输入优化 int G[limit][limit];//存边 int n,m; int main(){ scanf("%d%d",&n,&m); for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= n ; ++j){ if(i == j)G[i][i] = 0; else G[i][j] = INF; } } for(int i = 0 ; i < m ; ++i){ int a,b; scanf("%d%d",&a,&b); G[a][b] = 1;//有边 } for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= n ; ++j){ for(int k = 1 ; k <= n ; ++k){ if(G[j][i] + G[i][k] < G[j][k]){ G[j][k] = G[j][i] + G[i][k];//floyd算法 } } } } int cnt = 0, tot = 0; for(int i = 1 ; i <= n ; ++i){ cnt = 0; for(int j = 1 ; j <= n ; ++j){ if(i == j)continue; if(G[i][j] != INF)++cnt; if(G[j][i] != INF)++cnt; } if(cnt == n - 1)++tot; } printf("%d\n",tot); return 0; }

贪心安排时间模板：

贪心钓鱼动态队列模板：

#include <bits/stdc++.h> using namespace std; #define limit 200000 + 5 #define INF 0x3f3f3f3f #define lch root * 2 + 1 #define rch root * 2 + 2 #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-6 #define ff(a) printf("%d\n",a ); typedef long long ll; void read(int &x){ char ch = getchar();x = 0; for (; ch < ‘0’ || ch > ‘9’; ch = getchar()); for (; ch >=‘0’ && ch <= ‘9’; ch = getchar()) x = x * 10 + ch - ‘0’; }//快读 int fish[limit], cost[limit], decr[limit]; int n ; int stay[limit]; int timeLeft; struct lake{ //记录湖的状态 int id, stay, fish ,decc;//id记录号码，stay初始化为0记录在这个地方呆的时间 lake() = default; lake(int ii , int ff, int dd):id(ii) ,stay(0), fish(ff) , decc(dd){} bool operator<(const lake &rhs)const{ if(fish == rhs.fish){ return id > rhs.id;//这点主要是为了让所有地方的鱼清空之后把剩余时间分配给前面的湖 }else{ return fish < rhs.fish; } } }; int solve(){ priority_queueq; int ans = -INF;//答案初始化为负无穷 for(int i = 1 ; i <= n ; ++i){//这一层循环是为了给池塘数目设界，比如1-3，在1，12，123停留的情况都要考虑到 //每走一起枚举一遍 int tot = timeLeft - cost[i - 1];//总时间，每次走几个湖的问题.预先打表不用挨个算了 while(!q.empty()){ q.pop(); }//把可能的元素剔除，防止干扰判断 int tmp = 0; for(int j = 1 ; j <= i ;++j ){ q.push(lake(j , fish[j] , decr[j]));//推进去 } while(tot > 0){ lake cur = q.top(); //printf(“The sample being drawn has the value of %d\n”, cur.fish); q.pop(); tmp += cur.fish; cur.fish -= cur.decc; tot -= 5; if(cur.fish < 0) cur.fish = 0;//拨正归零 cur.stay += 5; q.push(cur);//做完dfs再送回去，这里鱼钓完了，所有池塘数目为0，根据运算符规定按id序排列 // 进行处理是因为刚才重载运算符的时候已经考虑了这种情况，id靠前的优先，无鱼可钓之后 //自然把时间加到第一个了 } if(tmp > ans){//这里是如果渔获大于原来的才可以更新，等于排除在外 ans = tmp; while(!q.empty()){ lake now = q.top(); q.pop(); stay[now.id] = now.stay;//如果没有了就更新 } } } return ans; }; int main(){ while(scanf("%d" , &n) == 1 && n ){ scanf("%d" , &timeLeft); memset(cost , 0 , n + n); memset(stay, 0 , sizeof(stay)); timeLeft *= 60;//剩余时间 for(int i = 1 ; i <= n ; ++i){ scanf("%d" , &fish[i]);//输入渔获数量 } for(int i = 1 ; i <= n ; ++i){ scanf("%d" , &decr[i]);//输入减少数量 } for(int i = 1 ; i < n ; ++i){ scanf("%d" , &cost[i]);//输入数量 cost[i] *= 5;//打表 } //到哪个地方的费用，到时候O(1)提取 for(int i = 1 ; i <= n ; ++i){ cost[i] += cost[i - 1]; } int ans = solve(); printf("%d", stay[1]); for(int i = 2 ; i <= n ; ++i ){ printf(", %d", stay[i]); } puts("");//换行 printf(“Number of fish expected: %d\n”, ans); puts("");//记住这里还有个空行 } return 0; }

最新回复(0)