Summary1.3 算法板题
[TOC]
算法模版
背包DP-01背包
for (int i = 0; i < m; ++i)
for (int j = t; j >= c[i] ; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
背包DP-多重背包
for (int i = 1; i <= n; ++i)
for (int j = w; j >= c[i]; --j)
for (int k = 1; k <= num[i] && k*c[i]<=j; ++k)
dp[j] = max(dp[j], dp[j-k*c[i]]+k*val[i]);
背包DP-多重背包二进制加速
类似于快速幂的思路，对首先将多重背包拍平成01背包，然后再跑01，将跑01的过程用快速幂加速。
int n, m ,ta, tb ,tc, c[maxn], val[maxn], idx = 0, dp[maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
for (int j = 1; j <= tc; j<<=1) {
c[++idx] = tb*j; val[idx] = ta*j;
tc-=j;
}
if (tc) {c[++idx] = tb*tc;val[idx] = ta*tc;}
}
for (int i = 1; i <= idx; ++i)
for (int j = m; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
printf("%d\n", dp[m]);}
区间DP-区间合并代价
题目大意：删除一段数组的数，代价为这个区间的左右端点值的差的绝对值*长度，求全部删去的最大代价。
区间DP的水题，维护一个dp二维数组，然后三层遍历左右端点+中间割点，利用状态转移方程dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])即可。
注意：要上来初始化一下，初始化的值就是运算法则算出来的，而dp所做的就是排列组合来搜索组合。
int n, a[maxn], dp[maxn][maxn]; // dp[i][j] 表示区间[i, j]所获得的最大价值
// dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]);
int main() {
scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", a+i);
for (int i = 1; i <= n; ++i)
for (int l = 0; l+i <= n; ++l)
if (l == 0) dp[i][i+l] = a[i];
else dp[i][i+l] = abs(a[i]-a[i+l])*(l+1);
for (int i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
for (int k = i; k <= j; ++k)
dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]);
printf("%d\n", dp[1][n]);}
区间DP-环形区间合并代价
题目大意：环形的一圈石子，合并相邻的两个，得到最大的和最小的合并代价。
1、不可以用贪心，因为贪心出来的话，不能确定选取的那最小的两个是相邻的，因为题目要求只能合并最小的两个
2、把环形拆解成链状，也就是转换成了第一个问题，线性的问题。 => 通过延长到2倍的长度。思路类似于原来的并查集的对立集，也是将数组长度延长到了两倍
3、遍历次序：通过先遍历长度，然后再遍历左索引i，从而得到右索引j，就得到一个区间(i, i+len-1)，然后再在区间中遍历k，也就是分割点即可。dp_max[i][j] = max(dp_max[i][j], dp_max[i][k]+dp_max[k+1][j]+cost(i, j));
4、代价计算：通过前缀和来维护，或者直接用区间来算出来。sum[i][j]表示合并区间的代价
int n, a[maxn], sum[maxn][maxn], dp_min[maxn][maxn], dp_max[maxn][maxn], ans_min = INF, ans_max;
int main() {
scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);a[i+n] = a[i];}
for (int i = 1; i <= 2*n; i++)
for (int j = 1; j <= 2*n; j++)
for (int k = i; k <= j; k++)
sum[i][j] += a[k];
for (int i = 1; i <= n; ++i) dp_min[i][i] = dp_max[i][i] = 0;
for (int len = 1; len < n; len++)
for (int i = 1, j = i+len; i <= 2*n - 1 && j < 2*n; i++, j = i + len) {
dp_min[i][j] = INF;
for (int k = i; k < j; k++) {
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum[i][j]);
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum[i][j]);
}
}
for (int i = 1; i <= n; ++i) {ans_min = min(ans_min, dp_min[i][i+n-1]);ans_max = max(ans_max, dp_max[i][i+n-1]);}
printf("%d\n%d\n", ans_min, ans_max); }
树形DP-子树和
题目大意：获取该棵树中最大的子树和
对于该题：数据结构：链式前向星储存，然后通过维护一个dp[i]数组，表示第i个节点为根的子树的最大和。dp状态转移方程：dp[x] = max(dp[x], dp[x]+dp[to]);
int n, dp[maxn], in[maxn], ta, tb;
struct node {
int to, next;
}edges[maxn<<1];int head[maxn], tot;
void addedge(int from, int to) {
edges[++tot].to = to; edges[tot].next = head[from]; head[from] = tot; in[to]++;}
void tree_dp(int x) {
for (int i = head[x]; i; i=edges[i].next) {
int to = edges[i].to;
tree_dp(to);
dp[x] = max(dp[x], dp[x]+dp[to]); }}
int main() {
scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", dp+i);
for (int i = 1; i < n; ++i) {
scanf("%d%d", &ta, &tb);
addedge(tb, ta);}
for (int i = 1; i <= n; ++i)
if (!in[i]) {
tree_dp(i);
printf("%d\n", dp[i]); }}
树形DP-依赖关系子树和
题目大意：没有上司的晚会，某个节点出现的条件是上下节点不出现。（在树上体现出来就是上下不相邻），如何挑选树上节点使得快乐值最大
对于该题：数据结构：链式前向星储存，然后通过维护一个dp[i][j]数组，在i=0表示不取当前这个节点的时候所获的的值 i=1表示取这个节点所获得的值；dp状态转移方程：dp[0][x] += max(dp[0][to], dp[1][to]); dp[1][x] += dp[0][to];
int n, dp[5][maxn], in[maxn], ta, tb;
struct node {
int to, next;
}edges[maxn<<1];int head[maxn], tot;
void addedge(int from, int to) {
edges[++tot].to = to; edges[tot].next = head[from]; head[from] = tot; in[to]++;}
void tree_dp(int x) {
for (int i = head[x]; i; i=edges[i].next) {
int to = edges[i].to; tree_dp(to); dp[1][x] += dp[0][to];
dp[0][x] += max(dp[1][to], dp[0][to]); }}
int main() {
scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &dp[1][i]);
for (int i = 1; i <= n-1; ++i) {
scanf("%d%d", &ta, &tb);
addedge(tb, ta);}
for (int i = 1; i <= n; ++i) if (!in[i]) {tree_dp(i);printf("%d\n", max(dp[0][i],dp[1][i]));}}
树形DP-依赖关系背包和
题目大意：有先后关系，需要是一条树上的前后关联，然后问最大的和
int n, dp[maxn][maxn], ta, tb, q;
struct node {
int to, next;
}edges[maxn];int head[maxn], tot;
void addedge(int from, int to) {
edges[++tot].to = to; edges[tot].next = head[from]; head[from] = tot;}
void tree_dp(int x) {
for (int i = head[x]; i; i=edges[i].next) {
int to = edges[i].to;
tree_dp(to);
for (int j = q+1; j >= 1; --j)
for (int k = 0; k < j; ++k)
dp[j][x] = max(dp[j][x], dp[k][to]+dp[j-k][x]);}}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &ta, &tb);
dp[1][i] = tb;
addedge(ta, i);
}
tree_dp(0);
printf("%d\n", dp[q+1][0]);}
线性DP-LIS 单个序列最大递增子序列
int n, a[maxn], dp[maxn], ans; // dp[i]表示到i之前的最长递增序列 // 状态转移方程：dp[j] = max
int main() {
scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j)
if (a[i] > a[j]) dp[i] = max(dp[i], dp[j]+1);
ans = max(ans, dp[i]);}
printf("%d\n", ans);}
线性DP-LCS 两个序列之间最长公共相同序列
int n, a[maxn], b[maxn], dp[maxn][maxn]; //dp[i][j] i是在第一个串中的索引的位置，j是第二个串中的索引的位置
// 状态转移方程：dp[i][j] = a[i] == a[j] ? dp[i-1][j-1]:max(dp[i-1][j], dp[i][j-1]);
int main() {
scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = (a[i] == b[j] ? dp[i-1][j-1]+1:max(dp[i-1][j], dp[i][j-1]));
printf("%d\n", dp[n][n]);}
回文DP-判断最长回文串
bool dp[i][j]表示从[i,j]这一段是否为回文串- 状态转移方程：
dp[i][j] = (s[i] == s[j] && (j-i == 1||dp[i+1]dp[j-1]))?true:false (j > i) - j-i == 1 是对aa这种两个字符呈对称形式的情况
int len = strlen(s),ans = 0;bool dp[len][len];
for (int i = 0; i < len; i++) dp[i][i] = true;
for (int j = 1; j < len; j++)
for (int i = 0; i < j; i++)
if (s[i] == s[j] && (j-i == 1 || dp[i+1][j-1])) {dp[i][j] = true;ans = max(ans,j-i+1);}
else dp[i][j] = false;
printf("%d\n",ans);
回文DP-最小删除次数使字串为回文串
- dp[i][j]表示区间[i,j]的最少抽取次数
- 状态转移方程
if (s[i] == s[j]) dp[i][j] = (j-i == 1)?1:dp[i+1][j-1]dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j])
int dp[maxn][maxn],a[maxn]; //dp[i][j]表示i-j这段区间合并所需要的次数 a是储存的原来的
int n,len,i,j,k; //j是起点加上重点的位置，然后k是这段区间中第一段分割的长度
int main(int argc, const char * argv[]) {
scanf("%d",&n); cl(dp, INF);
for (i = 1; i <= n; i++) {scanf("%d",&a[i]);dp[i][i] = 1;}
for (len = 1; len < n; len++) //先遍历长度，在遍历起点
for (i = 1; i+len <= n; i++) {
j = i+len;
if (a[i] == a[j]) dp[i][j] = len == 1?1:dp[i+1][j-1];
for (k = i; k < j; k++) dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);} //从中间找切断点k
cout<<dp[1][n]<<endl;}
二维DP-01坐标系中最大正方形
首先每个坐标都是变长为1的正方形，然后进行状态转换的话要根据i-1,j-1/i,j-1/i-1,j这三个点进行转移（并且需要满足合成正方形的条件才可以转移），从而得到0～当前点范围内的最大正方形。
int n, m, a[maxn][maxn], dp[maxn][maxn], ans; // dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
if (a[i][j]) dp[i][j] = min(min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) ans = max(ans, dp[i][j]);
printf("%d\n", ans);}
排序-逆序对数，最少相邻交换次数
int n, a[maxn], t[maxn], tidx, lidx, ridx; ll ans;
void mergesort(int l, int r){
if (r > l) {
int mid = (l+r)>>1; mergesort(l, mid); mergesort(mid+1, r);
tidx = lidx = l, ridx = mid+1;
while (lidx <= mid && ridx <= r) {
if (a[lidx] <= a[ridx]) t[tidx++] = a[lidx++];
else t[tidx++] = a[ridx++], ans += (mid-lidx+1); }
while (lidx <= mid) t[tidx++] = a[lidx++];
while (ridx <= r) t[tidx++] = a[ridx++];
for (int i = l; i <= r; ++i) a[i] = t[i];}}
int main() {
scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a+i);
mergesort(1, n); printf("%lld\n", ans);}
并查集-给定处于相同集合的元素关系，元素是否在同一集合，有多少集合
int n, m, p, fa[maxn], ta, tb;
int findfa(int x){return fa[x] == x?x:findfa(fa[x]);}
int main() {
scanf("%d%d%d", &n, &m, &p); for (int i = 1; i <= n; ++i) fa[i]=i;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &ta, &tb);
if (findfa(ta) != findfa(tb)) fa[findfa(tb)] = findfa(ta);}
for (int i = 1; i <= p; ++i) {
scanf("%d%d", &ta, &tb);
if (findfa(ta) != findfa(tb)) printf("No\n");else printf("Yes\n");}
// 集合个数
for (int i = 1; i <= n; ++i) if (fa[i] == i) cnt++; printf("%d\n", cnt-1);// cnt即为集合个数}
并查集-给定处于敌对集合的元素关系，敌对集合
关键：敌对的敌对是朋友。运用反集解决。
int n, m, fa[maxn], ta, tb, cnt = 0; char ch;
int findfa(int x){return fa[x]==x?x:findfa(fa[x]);}
int main() {
scanf("%d%d", &n, &m);for (int i = 1; i <= 2*n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
cin>>ch>>ta>>tb;
if (ch == 'F'){
fa[findfa(ta)] = findfa(tb);
} else{
fa[findfa(ta+n)] = findfa(tb);
fa[findfa(tb+n)] = findfa(ta);}}
for (int i = 1; i <= n; ++i) if (fa[i] == i) cnt++; printf("%d", cnt);}
字符串-trie树，动态不断查询，返回当前查询是否是第一次出现或者重复出现
struct trie {
int nex[maxn][26], cnt; int exist[maxn]; // 0 没出现；1 第一出现；2 重复出现
int val[maxn]; // -1 查不到这个人的对应的值
void insert(char *s) {
int p = 0, l = strlen(s);
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++cnt;
p = nex[p][c];}// 修改val数组 }
int find(char *s) {
int p = 0, l = strlen(s);
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c]) return 0;
p = nex[p][c];}
// 修改exist数组的地方
if (!exist[p]) {exist[p] = 1;return 1;} return 2; }
int getvalue(char *s) {
int p = 0, l = strlen(s);
for (int i = 0; i < l; i++) {
int c = s[i] - 'a'; if (!nex[p][c]) return -1; p = nex[p][c];}
return val[p];}
}tree;
int n, m; char s[55];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) { scanf("%s", s); tree.insert(s);}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%s", s);
switch (tree.find(s)) {
case 0: printf("WRONG\n");break; case 1: printf("OK\n");break; case 2: printf("REPEAT\n");break;}}}
bfs-最短步数、路径
int mp[maxn][maxn], vis[maxn][maxn], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, ansx[300], ansy[300], idx;
struct node{int x, y;node * fa;node(){}node(int x, int y, node * fa): x(x), y(y), fa(fa){}};
queue<node> q;
void printTrace(node nw){
ansx[idx] = nw.x;ansy[idx++] = nw.y;node * nt = nw.fa;
while (nt!=NULL) { ansx[idx] = nt->x;ansy[idx++] = nt->y; nt = nt->fa;}
for (int i = idx-1; i >= 0; --i) printf("(%d, %d)\n",ansx[i], ansy[i]);}
void bfs(int x, int y) {
q.push(node(x, y, NULL));
while (!q.empty()) {
node nw = q.front();
if (nw.x == 4 && nw.y == 4) {printTrace(nw);return;}
for (int i = 0; i < 4; ++i) {
int nx = nw.x+dir[i][0], ny = nw.y+dir[i][1];
if (nx == 4 && ny == 4) {printTrace(node(nx, ny, &nw));return;}
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !mp[nx][ny] && !vis[nx][ny]) {
vis[nx][ny] = 1; q.push(node(nx, ny, &q.front()));}}
q.pop();}}
int main() {
for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) scanf("%d", &mp[i][j]);
bfs(0,0); }
dfs-记忆化搜索，重复调用函数，进行记录防止tle
ll ta, tb, tc, dp[maxn][maxn][maxn];
ll dfs(int a, int b, int c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
if (dp[a][b][c]) return dp[a][b][c];
if (a < b && b < c) return dp[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);
else return dp[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);}
int main() {
while (scanf("%lld%lld%lld", &ta, &tb, &tc) && !(ta==-1 && tb==-1 && tc==-1))
printf("w(%lld, %lld, %lld) = %lld\n", ta, tb, tc, dfs(ta, tb, tc));}
dfs-记忆话搜索，固定变量不同的数值组合
int a, b, c, na, nb, nc, vis[25];int v[25][25][25];
void dfs(int x, int y, int z) {
if (!x && !vis[z]) vis[z] = 1; if (v[x][y][z]) return;
v[x][y][z] = 1;
if (x) {if (y < b) {
if (x > b-y) dfs(x-(b-y), b, z);
else dfs(0, y+x, z);}
if (z < c) {
if (x > c-z) dfs(x-(c-z), y, c);
else dfs(0, y, z+x);}}
if (y) {if (x < a) {
if (y > a-x) dfs(a, y-(a-x), z);
else dfs(x+y, 0, z);}
if (z < c) {
if (y > c-z) dfs(x, y-(c-z), c);
else dfs(x, 0, z+y);}}
if (z) {if (x < a) {
if (z > a-x) dfs(a, y, z-(a-x));
else dfs(x+z, y, 0);}
if (y < b) {
if (z > b-y) dfs(x, b, z-(b-y));
else dfs(x, y+z, 0);}}}
int main() {
scanf("%d%d%d", &a, &b, &c);na = 0, nb = 0, nc = c;vis[c] = 1;dfs(0, 0, c);
for (int i = 0; i <= 21; ++i)if (vis[i]) printf("%d ", i);}
DFS-记忆话搜索，前面DFS输出所有组合数
通过剪枝的方式，记录上一层的last，然后保证递增可以，也可以通过记忆话搜索给记录下来
dp[0][0] = 1; // 首先初始化一下
for (int i = 1; i <= total; ++i) // 遍历第一维度的时候就不会再涉及到初始化的那个维度，不然会覆盖掉
for (int j = i; j <= total; ++j)
for (int k = 1; k <= n; ++k)
dp[k][j] += dp[k-1][j-i];
DFS-记忆话搜索，组合数【小于等于4个数平方的和 组合成目标数】 的方案总和
dp[0][0] = 1;
for (int i = 1; i*i <= M; ++i) // 遍历第一维度的时候就不会再涉及到初始化的那个维度，不然会覆盖掉
for (int j = i*i; j <= M; ++j)
for (int k = 1; k <= 4; ++k)
dp[k][j] += dp[k-1][j-i*i];
DFS-记忆话搜索，组合数【不限个数 组合成目标数】的方案总和
dp[1][1]=1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j <= nn/2; ++j)
if (j > i) dp[i][j] = dp[i-1][j]+dp[i-1][j-i];
else dp[i][j] = dp[i-1][j];
DFS-记忆话搜索，地图中最长的路线
int r, c, mp[maxn][maxn], dp[maxn][maxn], ans, dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // dp[i][j]这个点开始的最长连续下降的长度
int dfs(int x, int y) {
if (dp[x][y]) return dp[x][y];
dp[x][y] = 1;
for (int i = 0; i < 4; ++i) {
int nx = x+dir[i][0], ny = y+dir[i][1];
if (nx >= 0 && nx < r && ny >= 0 && ny < c && mp[nx][ny] < mp[x][y]){
dfs(nx, ny);dp[x][y] = max(dp[x][y], dp[nx][ny]+1);}}
return dp[x][y];}
int main() {
scanf("%d%d", &r, &c);
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) scanf("%d", &mp[i][j]);
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) ans = max(ans, dfs(i, j));
printf("%d\n", ans);}
数论-获取唯一的奇数个的不匹配的数 & 找未配上的对
- 思路一：数组存，然后排序，然后再遍历，两个两个遍历=> 爆内存，爆时间。
- 思路二：map存，找到配对的删除。一边即过。=> 6个点爆内存
- 正确思路：直接用一个变量，然后来异或
^所有的数，a^a = 0，所以最后剩下的那个数就是没匹配的。
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t); ans ^= t;}
printf("%d\n", ans);
数论-获取唯一的出现偶数次数的 & 找配上对的
这个需要先把所有存在的数都输入进去，得到所有数的异或，然后再异或数组种的所有数，那么出现偶数次的就会显露出来了，出现单次的就会和第一次的异或掉了。
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t);ans^=t;}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {scanf("%d", &t);ans^=t;}
数论-区间中可以用平方差计算得到的个数
题目大意：区间[a, b]中，某个数i，这个数i可以写成c^2-d^2
正向数学推导：i=(c+d)(c-d)，那么c+d/c-d必定为同奇偶，同奇偶必定乘积要不满足是奇数，要不满足是4的倍数（因为是两个2的倍数相乘）。
反推验证：若i为奇数，也就是2k+1，那么可以找到c=k+1, d=k满足c+d=2k+1与c-d=1的乘积为2k+1这个条件。
若i为4的倍数，也就是4k，那么可以找到c=k+1, d=k-1满足c+d=2k与c-d=2的乘积是4k这个条件。
for (int i = a; i <= b; ++i)
if (i%2 || !(i%4)) ans++;
数论-第二类Stirling数
数学意义：把n个数划分成k个集合
实际意义：将n个球分到k个相同的盒子
// 递归写法
ll stirling(int n, int k){
if (k==n || k==1) return 1;
else if (k==2) return pow(2, (n-1)*1.0)-1;
else return stirling(n-1, k-1)+k*stirling(n-1, k);
}
// 非递归写法
数论-第二类Stirling数的变形
数学意义：把n个数划分成k个不同的集合
实际意义：把n个球分到k个不同的盒子里
和第二类Stirling数的区别：就是划分出来的集合再进行容器的匹配，对于不同的集合划分到不同的容器中。匹配原则：Ann
ll stirling(int n, int k){
if (k==n || k==1) return 1;
else if (k==2) return pow(2, (n-1)*1.0)-1;
else return stirling(n-1, k-1)+k*stirling(n-1, k);
}
// 排列数Ann
ll factorial(ll n) {
ll fc = 1;
for (ll i = 1; i <= n; ++i) fc *= i;
return fc;
}
数论-线性素数筛，高效率达标素数
线性筛：O(n)
prime是质数列表，isprime
#define maxn 10000010
int vis[maxn], prime[maxn], isprime[maxn];
void Prime()
{
for(int i=2; i<=b; i++)
{
if(!vis[i]) prime[cnt++] = i, isprime[i] = 1;
for(int j=0; j<cnt&&i*prime[j]<=b; j++)
{
vis[i*prime[j]] = i;
if(i%prime[j]==0) break;
}
}
}
b = 100; // 设置筛的边界
LPrime();
for (int i = 5; i < 20; ++i) {
printf("%d %d %d\n", i, prime[i], isprime[i]); // prime是按照顺序的素数存放进来， isprime是索引的数是否为质数
}
数据结构-ST表，RMQ，区间最小最大值RangeMinMaxQuery，包含最大与最小
int n, m, a[maxn], maxx[maxn][21], minn[maxn][21], ta, tb;
inline int read() { // 快速读取模版
int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f;}
void init() {
for (int i = 1; i <= n; ++i) {minn[i][0] = a[i]; maxx[i][0] = a[i];}
for (int j = 1; j <= 21; ++j) for (int i = 1; i+(1<<j)-1 <= n; ++i){
maxx[i][j] = max(maxx[i][j-1], maxx[i+(1<<(j-1))][j-1]);
minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);}}
int query_max(int l, int r) { int k = log2(r-l+1); return max(maxx[l][k], maxx[r-(1<<k)+1][k]);}
int query_min(int l, int r) { int k = log2(r-l+1); return min(minn[l][k], minn[r-(1<<k)+1][k]);}
int main() {
n = read();m = read(); for (int i = 1; i <= n; ++i) a[i] = read(); init();
while (m--) { ta = read();tb = read(); printf("%d %d\n", query_min(ta, tb), query_max(ta, tb));}}
数据结构-ST表，RGCD，区间最小公倍数，可重复贡献
int n, m, a[maxn], gcdd[maxn][21], ta, tb;
int gcd(int a, int b) {return b>0?gcd(b, a%b):a;}
void init(){
for (int i = 1; i <= n; ++i) gcdd[i][0] = a[i];
for (int j = 1; j <= 21; ++j) for (int i = 1; i+(1<<j)-1 <= n; ++i) gcdd[i][j] = gcd(gcdd[i][j-1], gcdd[i+(1<<(j-1))][j-1]); }
int query_gcd(int l, int r) { int k = log2(r-l+1); return gcd(gcdd[l][k], gcdd[r-(1<<k)+1][k]);}
int main() {
scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);init();
while (m--) { scanf("%d%d", &ta, &tb); printf("%d\n", query_gcd(ta, tb));}}
二叉树-哈夫曼编码
struct node { int data; node *lchild; node *rchild;} *huffmantree, huffman[maxn];
int n, ll, rr;
struct nd { int val, idx; bool operator < (const nd n) const {return val > n.val;}};
priority_queue<nd, vector<nd>, less<nd>> pq;
void PreOrder(node *T) {if (T) {cout << T->data << " "; PreOrder(T->lchild);PreOrder(T->rchild);}}
node * HuffmanTree() {
for (int j = 0; j < n; ++j) pq.push({huffman[j].data, j});
for (int i = 0; i < n - 1; i++) {
ll = pq.top().idx;pq.pop();rr = pq.top().idx;pq.pop();
node * lnode = new node {huffman[ll].data, huffman[ll].lchild, huffman[ll].rchild};
huffman[ll] = {huffman[ll].data + huffman[rr].data, lnode, &huffman[rr]};
pq.push({huffman[ll].data, ll});}
return &huffman[ll];}
int main(void) {
scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &huffman[i].data);
// build tree
huffmantree = HuffmanTree();PreOrder(huffmantree);}
二叉搜索树
性质情况一：左儿子小于父节点 && 右儿子大于父节点 => 中序遍历得到递增序列情况二：左儿子大于父节点 && 右儿子小于父节点 => 中序遍历得到递减序列
实现二叉链表实现，每添加一次新的值，就build一次，从根节点往下插入新的值;要插入的数比当前节点的值小=>往左子树插入;要插入的数比当前节点的值大=>往右子树插入;然后如果插到最底部了，当前这个节点直接NULL了，那就重新new一个这个要插入的数对应的节点。
struct nd {int val, pri; bool operator < (const nd n) const {return pri < n.pri;}}a[35];
int n, nwval, nwpri;
struct node { int val, pri; node * l, *r;}* root;
node * build(node * nw) {
if (nw == NULL) {nw = new node();nw->pri = nwpri;nw->val = nwval;nw->l = nw->r = NULL;return nw;}
if (nwval <= nw->val) nw->l = build(nw->l);else nw->r = build(nw->r);return nw;}
queue<node*> q;
vector<int> v_val, v_pri;
void level_traverse(node * nw) {
q.push(nw);
while (!q.empty()) {
node * nwnode = q.front();q.pop();
v_val.push_back(nwnode->val);v_pri.push_back(nwnode->pri);
if (nwnode->l) q.push(nwnode->l);if (nwnode->r) q.push(nwnode->r);}}
int main() {
scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].val, &a[i].pri);sort(a+1, a+1+n);
for (int i = 1; i <= n; ++i) { nwval = a[i].val, nwpri = a[i].pri; root = build(root);}
level_traverse(root);
for (int i = 0; i < v_val.size(); ++i) { if (i != 0) cout<<" ";cout<<v_val[i];}
for (int i = 0; i < v_pri.size(); ++i) { if (i != 0) cout<<" "; cout<<v_pri[i];}}
二叉链表
由于是二叉链表，实质上是指针指向的，所以就写一个递归的返回指针的函数。
node * build() { char ch; cin>>ch;
if (ch == '#') return NULL; else {// 声明出当前指向结构体的指针
node * n = (node*)malloc(sizeof(node));n->data = ch-'0';n->lchild = build();n->rchild = build(); }}
// main函数里 => 先创建一个指向根节点的指针，然后就可以开始给这个指针build了
node * tree = (node*)malloc(sizeof(node)); tree = build();
4、前周后序遍历，都只需要将指向根节点的指针传入即可。
struct node {
int data; node * lchild; node * rchild;
node(){} node(int data): data(data){}
node(int data, node * lchild, node * rchild): data(data), lchild(lchild), rchild(rchild){}};
char ch;// 构造二叉树
node * build(){
cin>>ch; if (ch == '#') return NULL;
else {
node * n = (node*)malloc(sizeof(node)); n->data = ch-'0'; n->lchild = build(); n->rchild = build();
return n;}}
void pre_traverse(node * n) { cout<<n->data<<" "; if (n->lchild) pre_traverse(n->lchild); if (n->rchild) pre_traverse(n->rchild);} // 前序遍历
void in_traverse(node * n) { if (n->lchild) in_traverse(n->lchild); cout<<n->data<<" "; if (n->rchild) in_traverse(n->rchild);} // 中序遍历
void post_traverse(node * n) {if (n->lchild) post_traverse(n->lchild); if (n->rchild) post_traverse(n->rchild);cout<<n->data<<" ";}// 后序遍历
// 非递归遍历
int cnt_node, cnt_1, cnt_2, cnt_leaf, val_min=INT_MAX, val_max;
queue<node*> q1;
void non_recursive_traverse(node * n) {
q1.push(n);
while (!q1.empty()) {
node * nw = q1.front();q1.pop();cnt_node++;
val_min = min(val_min, nw->data); val_max = max(val_max, nw->data);
if (nw->lchild && nw->rchild) cnt_2++;
else if (nw->lchild==NULL && nw->rchild==NULL) cnt_leaf++;
else cnt_1++;
if (nw->lchild) q1.push(nw->lchild); if (nw->rchild) q1.push(nw->rchild);}}
queue<node*> q2;// 选做内容：bfs 层次遍历
void bfs(node * n) {
q2.push(n);
while (!q2.empty()) {
node * nw = q2.front();q2.pop();
cout<<nw->data<<" "; if (nw->lchild) q2.push(nw->lchild); if (nw->rchild) q2.push(nw->rchild);}}
int main() {
node * tree = (node*)malloc(sizeof(node));
tree = build();
cout<<"前序遍历: "; pre_traverse(tree); cout<<endl<<"中序遍历: "; in_traverse(tree);
cout<<endl<<"后序遍历: "; post_traverse(tree);
cout<<endl<<"非递归遍历: "; non_recursive_traverse(tree);
cout<<"节点个数:"<<cnt_node<<" 度为1的节点个数:"<<cnt_1<<" 度为2的节点个数:"<<cnt_2<<" 叶子节点个数:"<<cnt_leaf<<endl<<"最大值:"<<val_max<<" 最小值:"<<val_min;
cout<<endl<<"层次遍历(bfs): "; bfs(tree); cout<<endl;}
二叉树建树 - 节点值做索引表示
https://www.luogu.com.cn/problem/P1305
1、节点值做索引的数据结构
结构体中不需要当前节点的值，因为这个节点的值已经在做数据结构的索引了
struct node {int left, right;}tree[maxnode];
要求给出的数据（节点的顺序必须为对应的，不然这样匹配是有问题的）
// 读入字符串abc，得到a为根节点，bc分别为两个子节点 (注意读取单个字符的时候，要给空格来冲刷掉回车的影响)
scanf(" %c", &ch); scanf(" %c%c", &tree[ch].left, &tree[ch].right);
2、前中后序的遍历
- 前：根->左->右
- 中：左->根->右
- 后：右->根->左
void front_traverse(char ch) {
printf("%c", ch);
if (当前节点的左儿子不是空) front_traverse(tree[ch].left);
if (当前节点的右儿子不是空) front_traverse(tree[ch].right);
}
void mid_traverse(char ch) {
if (当前节点的左儿子不是空) mid_traverse(tree[ch].left);
printf("%c", ch);
if (当前节点的右儿子不是空) mid_traverse(tree[ch].right);
}
void back_traverse(char ch) {
if (当前节点的左儿子不是空) back_traverse(tree[ch].left);
if (当前节点的右儿子不是空) back_traverse(tree[ch].right);
printf("%c", ch);
}
AC代码：
#include <iostream>
using namespace std;
int n;
struct node {
char left, right;
}tree[1000];
char ch, root;
void front_traverse(char ch) {
// front traverse => root, left, right
printf("%c", ch);
if (tree[ch].left != '*') front_traverse(tree[ch].left);
if (tree[ch].right != '*') front_traverse(tree[ch].right);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf(" %c", &ch);
if (i == 1) root = ch;
scanf(" %c%c", &tree[ch].left, &tree[ch].right);
}
front_traverse(root);
return 0;
}
二叉树 - 节点值做索引 搜索深度
https://www.luogu.com.cn/problem/P4913
1、遍历的过程中就筛选出最大的深度，通过维护一个ans来提取。
第一种，通过在dfs深搜到儿子节点之前来判断是否要搜他。
void dfs(int val, int depth) {
ans = max(ans, depth);
if (!tree[val].left) dfs(tree[val].left, depth+1);
if (!tree[val].right) dfs(tree[val].right, depth+1);
}
第二种，通过在搜到之后，判断这个搜到的点是否符合搜的要求。
void dfs(int val, int depth) {
if (!val) return;
ans = max(ans, depth);
dfs(tree[val].left, depth+1);
dfs(tree[val].right, depth+1);
}
AC代码：
#include <iostream>
using namespace std;
#define maxnode 1000010
struct node{
int left, right;
}tree[maxnode];
int n, ans;
void dfs(int val, int depth) {
ans = max(ans, depth);
if (tree[val].left) dfs(tree[val].left, depth+1);
if (tree[val].right) dfs(tree[val].right, depth+1);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &tree[i].left, &tree[i].right);
dfs(1, 1);
printf("%d\n", ans);
return 0;
}
二叉树的前序 中序 后序 dfs序等性质 // 【给出前后，求中序】
题目：给出前序后序，不给中序，求这棵树有多少种形态。【中序有多少种】
分析：前序：根左右，中序：左根右，后序：左右根
性质：一个树有多少种形态，取决于儿子节点只有1个的节点的个数。【形态数 = pow(2, 儿子节点为1的节点个数)】
- 如果一棵树没有只有一个儿子节点的节点=》也就是是一个完满二叉树，只要有儿子节点，就是两个，要不就没有儿子节点。
- 此时树形态已经被确定了，例如前序abc后序bca，那这就是一个a->(b,c)的完满二叉树，在例如前序abdecfg后序debfgca，那就是一个a->(b->(d,e), c->(f,g))的完满二叉树
- 如果一个棵树的节点都只有一个儿子节点=》和一根线一样，就例如如果就是abc往下排列的一根线，那么可以计算得到两个节点满足只有一个儿子节点，那么总共有4种，分别为左左，左右，右左，右右。
#include <iostream>
using namespace std;
string pre, post;
int ans;
int main() {
cin>>pre>>post;
for (int i = 0; i < pre.length()-1; ++i)
for (int j = 0; j < post.length()-1; ++j)
if (pre[i] == post[j+1] && post[j] == pre[i+1]) ans++;
printf("%d\n", 1<<ans);
return 0;
}
二叉树的前序 中序 后序 dfs序等性质 // 【给出中序+前后中的一个，求另一个】
https://www.luogu.com.cn/problem/P1030 该题是由中序+后序求前序
https://www.luogu.com.cn/problem/P1827 该题是由中序+前序求后序
思路：首先明确前：根左右 中：左根右 后：左右根
然后整体思路就是通过前或者后的根在一边的特性，直接从对应的一段提取出根，然后再在中序中找到根，根左边的就是左子树，根右边的就是右子树，然后再递归两颗子树即可。
string pre, in, post;
void transform_pre(string i, string p) {
if (i.length() > 0) {
char root = p[p.length() - 1];
cout << root;
int pos = i.find(root);
transform_pre(i.substr(0, pos), p.substr(0, pos));
transform_pre(i.substr(pos + 1), p.substr(pos, i.size() - pos - 1));}}
void transform_post(string pr, string i) {
if (i.length() > 0) {
char root = pr[0];
int pos = i.find(root);
transform_post(pr.substr(1, pos), i.substr(0, pos));
transform_post(pr.substr(pos + 1), i.substr(pos + 1));
cout << root;}}
int main() { cin >> in >> pre; transform_post(pre, in);}
//1 2 3 4 5 6 7//中序遍历: 3256471//后序遍历: 3657421 //1 2 4 5 3 6 7//中序遍历: 4251637//后序遍历: 4526731
树状数组-模版-区间求和(查询)、单点修改(操作)
0、lowbit()看当前节点的归属情况/看当前节点所管辖的节点的个数 eg：8(10) & -8(10) = 8 => 根据树状数组结构图，就是8个节点
eg：4(10) & -4(10) = 4 => 根据树状数组结构图，就是4个节点 eg：6(10) & -6(10) = 2 => 根据树状数组结构图，就是2个节点
1、单点修改 => 自下而上修改 => c数组的索引pos从1开始往上找，但是要限定永远≤n => 从下往上找的话，看当前的节点归属那个父节点范围，则需要pos+=lowbit(pos)，此时就可以直接爬升到父节点。
void single_add(int pos, int k) { while(pos <= n) { c[pos] += k; pos += lowbit(pos);}}
2、区间求和「注意这个区间求的是前缀和，也就是1到pos的和。如果区间和的话，可以通过两个前缀和相减得到」=> 自上而下累加 => c数组的索引pos从target目标开始往下找，但是要限定下限，不能让下限爆掉，pos≥1 => 从上往下累加的话，看当前的节点归属那个的子节点，则需要pos-=lowbit(pos)，此时就可以直接下降到子节点。
int getsum(int pos) {int ans = 0; while(pos >= 1) { ans += c[pos]; pos -= lowbit(pos); } }
int n, m, tm, tp, ta, tb, c[maxn];
int lowbit(int x) {return x & (-x);}
void single_add(int pos, int k) { while (pos <= n) {c[pos] += k;pos += lowbit(pos);}}
int getsum(int pos) { int ans = 0; while (pos >= 1) { ans += c[pos]; pos -= lowbit(pos);}return ans;}
int main() {
scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", &tm);single_add(i, tm);}
while (m--) {
scanf("%d%d%d", &tp, &ta, &tb);
if (tp-1) printf("%d\n", getsum(tb)-getsum(ta-1));else single_add(ta, tb);}}
树状数组-模版-区间修改(操作)、单点求和(查询)
区间修改+单点求和 模版：https://www.luogu.com.cn/problem/P3368
区间修改+单次范围最值 【范围最值也可以看作是所有的点取一遍最值】：https://www.luogu.com.cn/problem/P2367
1、区间修改：考虑到差分，之不过是在树上进行差分，利用树状数组进行差分，此时对于树状数组c的修改就只需要修改两头即可了，也就是在l的位置加上k，在r+1的位置减去k，最后再利用树状数组c进行还原即可。
2、此时沿着树状数组进行求和，求的就不是上面的那个区间和了 => 因为这个树状数组代表的是差分，累加所得到的该索引的数组的值。
P3368模版区间修改+多次查询单个点
int n, m, a[maxn], c[maxn], tp, ta, tb, tc;
int lowbit(int x) {return x & (-x);}
void single_add(int pos, int k) {
while (pos <= n) {
c[pos] += k;
pos += lowbit(pos); }}
void interval_add(int l, int r, int k) { single_add(l, k); single_add(r+1, -k);}
int getsum(int pos) {
int ans = 0;
while (pos >= 1) {
ans += c[pos];
pos -= lowbit(pos);
} return ans;}
int getval(int pos) { return a[pos] + getsum(pos);}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
while (m--) {
scanf("%d", &tp);
if (tp-1) {scanf("%d", &ta);printf("%d\n", getval(ta));}
else {scanf("%d%d%d", &ta, &tb, &tc);interval_add(ta, tb, tc);}}}
P2367区间修改+最终单次查询所有点
int n, m, a[maxn], c[maxn], ta, tb, tc, minn = (1<<31)-1; // c为树上的差分数组，a为记录原数据的数组
#define lowbit(x) x&(-x)
void add(int pos, int k) {
while (pos <= n) {
c[pos] += k;
pos += lowbit(pos); }}
void interval_add(int l, int r, int k) { add(l, k); add(r+1, -k);}
int query(int pos){
int ans = 0;
while (pos >= 1) {
ans += c[pos];
pos -= lowbit(pos);}
return ans;}
int main() {
scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
while (m--) { scanf("%d%d%d", &ta, &tb, &tc); interval_add(ta, tb, tc); }
for (int i = 1; i <= n; ++i) minn = min(a[i]+query(i), minn);
printf("%d\n", minn);}
树状数组-模版-区间修改(操作)、区间求和(查询)
https://www.luogu.com.cn/problem/P2367
1、区分上面的单点修改+区间求和 // 区间修改+单点查询，都可以解决尾一类问题，核心代码相似，只不过后者就是前者的基础上增添了差分的思想，根据差分用求和来查单点的值 == 根据累加用单点来查求和的值。
2、区间修改+区间查询需要维护两个数组，sum1数组是求和的数组，sum2数组是乘积的数组。进行区间修改的时候，进行差分来修改 // 进行区间查询的时候，根据前缀和来进行查询。
区间修改：
void add(ll pos, ll k) {
ll tem = k*pos;
while (pos <= n) {
sum1[pos] += k;sum2[pos] += tem;
pos += lowbit(pos);}}
void interval_add(ll l, ll r, ll k) { add(l, k); add(r+1, -k);}
区间查询
ll ans = 0, tem = pos;
while (pos >= 1) {
ans += ((tem+1)*sum1[pos] - sum2[pos]);
pos -= lowbit(pos);
}
return ans;
}
ll interval_query(ll l, ll r) {
return query(r)-query(l-1);
}
完整代码
ll n, m, tm, last, first_val, sum1[maxn], sum2[maxn], tp, ta, tb, tc;
#define lowbit(x) x&(-x)
void add(ll pos, ll k) {
ll tem = k*pos;
while (pos <= n) {
sum1[pos] += k;sum2[pos] += tem;
pos += lowbit(pos);}}
void interval_add(ll l, ll r, ll k) add(l, k); add(r+1, -k);}
ll query(ll pos) {
ll ans = 0, tem = pos;
while (pos >= 1) {
ans += ((tem+1)*sum1[pos] - sum2[pos]);
pos -= lowbit(pos);}
return ans;}
ll interval_query(ll l, ll r) { return query(r)-query(l-1);}
int main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {scanf("%lld", &tm);add(i, tm-last);last=tm;}
while (m--) {
scanf("%lld", &tp);
switch (tp) {
case 1: scanf("%lld%lld%lld", &ta, &tb, &tc);interval_add(ta, tb, tc);break;
case 2: scanf("%lld", &ta);first_val += ta;break;
case 3: scanf("%lld", &ta);first_val -= ta;break;
case 4: scanf("%lld%lld", &ta, &tb);printf("%lld\n", interval_query(ta, tb)+(ta==1)*first_val);break;
case 5: printf("%lld\n", query(1)+first_val);break;}}}
图论-LCA最近公公祖先
int n, m, root, ta, tb, depth[maxnode], p[maxnode][21];
struct node { int to, next;}edge[maxnode<<1];int head[maxnode],tot;
void addedge(int from, int to) {edge[++tot].to = to; edge[tot].next = head[from];head[from] = tot;}
void dfs(int from, int fa) {
depth[from] = depth[fa]+1;
p[from][0] = fa;
for (int i = 1; (1<<i) <= depth[from]; ++i) p[from][i] = p[p[from][i-1]][i-1];
for (int i = head[from]; i; i=edge[i].next) {
int to = edge[i].to; if (to != fa) dfs(to, from);}}
int lca(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
for (int i = 20; i >= 0; --i) if (depth[a] <= depth[b]-(1<<i)) b = p[b][i];
if (a == b) return a;
for (int i = 20; i >= 0; --i)
if (p[a][i] == p[b][i]) continue;else a = p[a][i],b=p[b][i];
return p[a][0];}
int main() {
scanf("%d%d%d", &n, &m, &root);
for (int i = 1; i <= n-1; ++i) {scanf("%d%d", &ta, &tb);addedge(ta, tb);addedge(tb, ta);}
dfs(root, 0);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &ta, &tb);int ans = lca(ta, tb);
int hh=H[a]+H[b]-H[u]*2+(PZ[u]=='H');
int gg=G[a]+G[b]-G[u]*2+(PZ[u]=='G');
if(c=='H'){if(hh) printf("1");else printf("0");}
else{if(gg) printf("1");else printf("0");}
printf("%d\n", lca(ta, tb));}}
图论-起终点一样，权值和为0，floyd算法
题目大意：给出一个图，有双向边和单向边（其中单向边的权值是负的），问是否存在路径可以满足起终点一样，权值和为0。
int t, n, m, w, mp[maxn][maxn], ta, tb, tc;
bool Floyd() {
for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)
if (mp[i][k]+mp[k][j] < mp[i][j]) mp[i][j] = mp[i][k]+mp[k][j];
if (mp[i][i] < 0) return true; // 判断负权闭环
} return false;}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &w);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j){ if (i == j) mp[i][j] = 0; mp[i][j] = mp[j][i] = inf; }
while (m--){
scanf("%d%d%d", &ta, &tb, &tc);
if (tc < mp[ta][tb]) mp[ta][tb] = mp[tb][ta] = tc;
}
while (w--){scanf("%d%d%d", &ta, &tb, &tc);mp[ta][tb] = -tc;}
if (Floyd()) puts("YES"); else puts("NO");}
return 0;}
图论-Floyd - 传递闭包
题意：给出已知的大小关系，问可以确定具体排名的个数有多少。
#include <iostream>
using namespace std;
const int maxn = 109;
int n, m, mp[maxn][maxn], ta, tb, ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &ta, &tb);
mp[ta][tb] = 1;
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
for (int i = 1; i <= n; ++i) {
int tem = 0;
for (int j = 1; j <= n; ++j)
if (mp[i][j] || mp[j][i]) tem++;
if (tem == n-1) ans++;
}
printf("%d\n", ans);
return 0;
}