一个同学 LSQ 在小课堂后对矩阵产生极大的感兴趣，他想到了一个对矩阵求和的问题，但是这个矩阵实在太大了，他算不过来，你能帮帮他吗？ 第一个坐标(a,c)，第二个坐标(b,d)。 a<b<=10^18，c<d<=10^18。
一行四个正整数a,b,c,d。
一行一个整数表示答案
1 3 4 6
108
因为题目乘以2，可以想到两个数之间应该有关系。 由图看一看出第一行第i个数和最后一行倒数第i个数之和sum都是相等的。所以题答案等于，sum*矩阵大小/2*2 = sum*矩阵大小。 但是题目数值过大，所以需要进行求余。
#include <bits/stdc++.h>
using namespace std;
const long mo=332748118;
int main(void) {
long height, width;
long start, end;
long a, b, c, d;
cin >> a >> b >> c >> d;
height = (b - a + 1) % mo;
width = (d - c + 1) % mo;
start = (a + c - 1);
end = (b + d - 1);
long result = (((height * width) % mo) * ((start + end) % mo)) % mo;
cout << result << endl;
}
(1) Prim算法
Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。
(2) Kruskal算法
Kruskal算法与Prim算法的不同之处在于，Kruskal在找最小生成树结点之前，需要对所有权重边做从小到大排序。将排序好的权重边依次加入到最小生成树中，如果加入时产生回路就跳过这条边，加入下一条边。当所有结点都加入到最小生成树中之后，就找出了最小生成树。
Kruskal算法在效率上要比Prim算法快，因为Kruskal只需要对权重边做一次排序，而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边，但是随着所使用的排序算法的效率的提高，Kruskal算法和Prim算法之间的差异将会清晰的显性出来。
考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边 的权值之和定义为该路径的路径长度或称带权路径长度。
从源点到终点可能不止一条路径，把路径长度最短的那条路径 称为最短路径。
(1) Dijkstra算法
算法思想是按路径长度递增的次序一步一步并入来求取，是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径问题。
设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。
(2) Floyd算法
Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。
对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。
设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1， v2，…，vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件： 若<i，j>是图中的边（或从顶点i → j有一条路径）: 在一个有向图中找一个拓扑序列的过程称为拓扑排序。
举个例子，课程安排问题，学习某门课程有时候需要先学习其他课程，如，要学习高数二，就必须先将高数一学完，因此课程学习就必须将高数一安排在高数二前面学习。
(1)AOE网
用一个带权有向图（DAG）描述工程的预计进度。
顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的 时间（比如天数）。
图中入度为0的顶点表示工程的开始事件（如开工仪式），出度为0的 顶点表示工程结束事件。
AOE网（Activity On Edge）
(2)关键路径
从AOE网中源点到汇点的最长路径，具有最大长度的路径叫 关键路径。
关键路径是由关键活动构成的，关键路径可能不唯一。
简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
准确地说，把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。
最大匹配：
在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数.如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配。
最优匹配：
最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。
最小覆盖：
分为最小顶点覆盖和最小路径覆盖：
①最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；
②最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数= V - 二分图的最大匹配数；
最大独立子集：
最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集= V -二分图的最大匹配数。
(1)匈牙利算法
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路
由增广路的性质，增广路中的匹配边总是比未匹配边多一条，所以如果我们放弃一条增广路中的匹配边，选取未匹配边作为匹配边，则匹配的数量就会增加。匈牙利算法就是在不断寻找增广路，如果找不到增广路，就说明达到了最大匹配。
它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
并查集是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
并查集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。
可以将森林合并成一颗树。
一般分为：初始化、查找、合并三步，在查找的时候可以进行路径压缩，即让所有子节点连接在根节点上。
就是在一个无向图中找出一个点数最多的完全图。
完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
如果一个回路是欧拉路径，则称为欧拉回路。
如果一个回路是欧拉路径，则称为欧拉回路。
对于一个无向图，若该图的任意一个长度大于3的环中存在一条边连接这个环上不相邻的两点，则此图称作弦图。
最小环是指在一个图中，有n个节点构成的边权和最小的环。
从一个点出发,经过一条简单路径回到起点成为环。图的最小环就是所有环中长度最小的。
无向图的割：就是去掉一些边，使得原图不连通，最小割就是要去掉边的数量最小。
(1) 01背包
有N件物品和一个容量为V的背包。每种物品只有一个。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
(2) 完全背包
有N件物品和一个容量为V的背包。每种物品都有无限个。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
(3) 多重背包
有N中物品和一个容量为V的背包。第i中物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！
但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为1个整数N，表示小Hi拥有的城市数量。
接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，
其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。
对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.
对于每组测试数据，输出1个整数Ans。
表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
5
0 1005 6963 392 1182
1005 0 1599 4213 1451
6963 1599 0 9780 2789
392 4213 9780 0 5236
1182 1451 2789 5236 0
4178
最小生成树Prim算法
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
//Prim算法
const int maxn = 1005;
//vis用来记录某个点是否被访问过，d用来记录无效集连接到有效集的最小值
int n,mat[maxn][maxn],vis[maxn],d[maxn];
int end,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mat[i][j]);
memset(d,0x3f3f3f3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[1]=0;
ans=0;
for(int i=1;i<=n;i++){
end=-1;
for(int j=1;j<=n;j++){
//如果该点没有被访问过并且（end是第一个元素或者j到有效集的距离小于最小的距离，则更新最小下标)
if(!vis[j]&&(end==-1||d[end]>d[j]))
end=j;
}
ans += d[end];
vis[end]=1;
//更新无效集中每个点到有效集的最小值
for(int j=1;j<=n;j++){
if(!vis[j]&&d[j]>mat[end][j])
d[j] = mat[end][j];
}
}
printf("%d\n",ans);
return 0;
}
给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。
第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <= 10^9)
第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9)
共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。
2 3
1 1
1 1
4 4
4 4
矩阵快速幂问题
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 110;
const int MOD = 1e9+7;
//宏定义 用来替代一段代码
#define mod(x) ((x)%MOD);
int n;
//矩阵结构体
struct mat{
int m[maxn][maxn];
}unit;
//乘法重载
mat operator * (mat a,mat b){
mat ret;
ll x;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
x=0;
for(int k=0;k<n;k++){
x += mod((ll)a.m[i][k]*b.m[k][j]);
}
ret.m[i][j] = mod(x);
}
return ret;
}
//单位矩阵初始化
void init_unit(){
for(int i=0;i<maxn;i++)
unit.m[i][i] = 1;
return ;
}
//快速幂
mat pow_mat(mat a,ll n){
mat ret = unit;
while(n){
if(n&1) ret = ret*a;
a = a*a;
n>>=1;
}
return ret;
}
int main(){
ll x;
init_unit();
while(cin>>n>>x){
mat a;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a.m[i][j];
a = pow_mat(a,x);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(j+1==n) cout<<a.m[i][j]<<endl;
else cout<<a.m[i][j]<<" ";
}
return 0;
}
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
1
8 2
2 100 4
4 100 2
400
多重背包问题。每种大米都有一定的数量。
#include<bits/stdc++.h>
using namespace std;
//多重背包问题
int c,v,m,weight[105],value[105],bag[105],dp[105];
int main(){
ios::sync_with_stdio(false);
scanf("%d",&c);
while(c--){
memset(dp,0,sizeof(dp));
scanf("%d%d",&v,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&weight[i],&value[i],&bag[i]);
for(int j=0;j<bag[i];j++){
for(int k=v;k>=weight[i];k--)
dp[k] = max(dp[k],dp[k-weight[i]]+value[i]);
}
}
printf("%d\n",dp[v]);
}
return 0;
}
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。。
对每个测试用例，在1行里输出最少还需要建设的道路数目。
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
1
0
2
998
并查集问题。先建立森林，得到森林的个数n，需要修的路就是n-1。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
//并查集问题
int pre[1050];
//返回x的根节点
int Find(int x) {
int r = x;
//当不成立时，r是x的根节点
while (r != pre[r])
r = pre[r];
int i = x, j;
//路径压缩，所有节点直接连接在根节点上
while (i != r) {
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
//合并
void join(int x, int y) {
int fx, fy;
fx = Find(x);
fy = Find(y);
if (fx != fy) {
pre[fx] = fy;
}
}
int main() {
int n, m, a, b;
while (scanf("%d", &n) && n) {
scanf("%d", &m);
//初始化
int result = 0;
for (int i = 1; i <= n; i++)
pre[i] = i;
//建立初始森林
for (int i = 1; i <= m; i++) {
scanf("%d%d", &a, &b);
join(a, b);
}
for (int i = 1; i <= n; i++) {
if (pre[i] == i) result++;
}
printf("%d\n", result-1);
}
return 0;
}