图论（未完）

（1）图的类型：有向图、无向图、加权图；

有向图和无向图从字面理解就可以知道一个有方向，一个无方向；

而加权图则是每条边都有权重，权重可以是任何一种度量，比如时间，距离，尺寸等。

（2）图的专业术语：

>>顶点、边、路径（从一个顶点到另一个顶点之间经过的所有顶点的集合）、路径长度（边数）。

>>环：起点和终点为同一个顶点的路径。

>>负权环：在「加权图」中，如果一个环的所有边的权重加起来为负数，我们就称之为「负权环」。

>>连通性：两个不同顶点之间存在至少一条路径，则称这两个顶点是连通的。

>>顶点的度：「度」适用于无向图，指的是和该顶点相连接的所有边数称为顶点的度。

>>顶点的入度：「入度」适用于有向图，一个顶点的入度为d，则表示有d条与顶点相连的边指向该顶点。

>>顶点的出度：「出度」适用于有向图，它与「入度」相反。一个顶点的出度为dd，则表示有dd条与顶点相连的边以该顶点为起点。

>>单源最短路：已知起始点，求起点到其他任意点最短路径的问题。

>>多源最短路：已知起点和终点，求任意两点之间的最短路径。

（1）矩阵存图法：

#include
#define maxn 102
using namespace std;
int n,a[maxn][maxn],x,y,k;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>k;
		a[x][y]=k;
		a[y][x]=k;  //无向图需要(元素对称) 
	}
    //依次对每个顶点访问
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]) cout<"< 
（2）邻接表存图法：
 
 
#include
#define maxn 1002
using namespace std;
int num;
int head[1001],next[maxn],to[maxn],w[maxn];
void add(int x,int y,int k){
	++num;
	to[num]=y;  //储存终点 
    w[num]=k;  //储存权值 
    next[num]=head[x];  //进行记录可查找邻边 
	head[x]=num;  //随时更新表头
}

int main(){
	int n,m,x,y,k;
	cin>>n>>m;  //n为边数，m为顶点数 
	for(int i=1;i<=n;i++){ //i为边的编号 
		cin>>x>>y>>k;
	    add(x,y,k);
	    add(y,x,k);  //无向图需要 
	}
	//依次对每个顶点访问
	for(int i=1;i<=m;i++){ 
		for(int j=head[i];j ;j=next[j]){
			cout<"< 
（3）链式前向星存图法：
 
3.图的深度优先搜索(dfs) 
  注：欧拉回路有0个奇点，欧拉路有2个奇点（起点是一个奇点，终点是另一个奇点）！ 
 
1341：【例题】一笔画问题 

 时间限制: 1000 ms         内存限制: 65536 KB
 提交数: 14352     通过数: 5157
 
【题目描述】 
 
 
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
 
 
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。
 
 
【输入】 
 
 
第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
 
 
【输出】 
 
 
欧拉路或欧拉回路,输出一条路径即可。
 
 
【输入样例】 
5 5
1 2
2 3
3 4
4 5
5 1
 
【输出样例】 
1 5 4 3 2 1
 
题解：  
#include //欧拉路2个奇点，欧拉回路0个奇点 
#define maxn 1002
using namespace std;
int n,m,a[maxn][maxn],vis[maxn],p[maxn],t=0;

void dfs(int i){
	vis[++t]=i;
	for(int j=1;j<=n;j++){
		if(a[i][j]){
			a[i][j]=0,a[j][i]=0; //删除已走边 
		    dfs(j);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int x,y,i=1;i<=m;i++){
		cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;
		p[x]++;
		p[y]++;
	}
	int flag=1;
	for(int i=1;i<=n;i++){ //找奇点 
		if(p[i]%2){
			flag=0;
			dfs(i);
			break;
		}
	}
	if(flag) dfs(1);
	for(int i=1;i<=t;i++) cout< 
1375：骑马修栅栏(fence) 

 时间限制: 1000 ms         内存限制: 65536 KB
 提交数: 10644     通过数: 3109
 
【题目描述】 
 
 
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
 
 
John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。
 
 
每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(≥1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
 
 
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 输入数据保证至少有一个解。
 
 
【输入】 
 
 
第1行:一个整数F(1≤F≤1024)，表示栅栏的数目;
 
 
第2到F+1行:每行两个整数i,j(1≤=i,j≤500)表示这条栅栏连接i与j号顶点。
 
 
【输出】 
 
 
输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。
 
 
【输入样例】 
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
 
【输出样例】 
1
2
3
4
2
5
4
6
5
7
 
题解：  
 分析：和一笔画问题有一点点不一样，需要回溯记录路径，两点之间的栅栏不一定只有一个 。
 
 
#include
#include
#define maxn 1030
using namespace std;
int n,a[maxn][maxn],mx,mn=1000,vis[maxn],s,p[maxn];
void dfs(int x){
	for(int i=mn;i<=mx;i++){
		if(a[x][i]){
			a[x][i]--,a[i][x]--;
			dfs(i);
		}
	}
	p[++s]=x; //需要回溯记录路径 ！！！ 
}

int main(){
	cin>>n;
	for(int x,y,i=1;i<=n;i++){
		cin>>x>>y;
		//两点之间的栅栏不一定只有一个 ！！！ 
		a[x][y]++;
		a[y][x]++;
		mx=max(mx,max(x,y));
		mn=min(mn,min(x,y));
		vis[x]++,vis[y]++;
	}
	int flag=1;
	for(int i=mn;i<=mx;i++){
		if(vis[i]%2){
			flag=0;
			dfs(i);
			break;
		}
	}
	if(flag) dfs(mn);
	for(int i=s;i>0;i--){
		cout< 
4.图的广度优先搜索（bfs） 
5.最短路径（详细文章） 
 
（1）Floyd算法（求多源最短路）
 
1342：【例4-1】最短路径问题 

 时间限制: 1000 ms         内存限制: 65536 KB
 提交数: 16583     通过数: 7507
 
【题目描述】 
 
 
平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
 
 
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
 
 
【输入】 
 
 
共n+m+3行，其中:
 
 
第一行为整数n。
 
 
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
 
 
第n+2行为一个整数m，表示图中连线的个数。
 
 
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
 
 
最后一行：两个整数s和t，分别表示源点和目标点。
 
 
【输出】 
 
 
一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
 
 
【输入样例】 
5 
0 0
2 0
2 2
0 2
3 1
5 
1 2
1 3
1 4
2 5
3 5
1 5
 
【输出样例】 
3.41
 
题解：  
#include
#include
#include
#include
#define maxn 1000000
using namespace std;
int n,x[102],y[102],m,s,t;
double g[102][102];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		for(int j=1;j<=n;j++) g[i][j]=maxn;
	} //memset(g,0x7f,sizeof g);
	cin>>m;
	for(int a,b,t1,t2,i=1;i<=m;i++){
		cin>>a>>b;
		t1=x[a]-x[b];
		t2=y[a]-y[b];
		g[a][b]=sqrt(1.0*t1*t1+1.0*t2*t2);
		g[b][a]=g[a][b];
	}
	cin>>s>>t;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(k!=i&&k!=j&&i!=j)
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}
	printf("%.2lf",g[s][t]);
	return 0;
}
 
（2）Dijkstra算法（主要求单源最短路） 详细文章
 
1381：城市路(Dijkstra) 

 时间限制: 1000 ms         内存限制: 65536 KB
 提交数: 14709     通过数: 4666
 
【题目描述】 
 
 
罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。
 
 
现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。
 
 
【输入】 
 
 
输入n, m，表示n个城市和m条路;
 
 
接下来m行，每行a b c， 表示城市a与城市b有长度为c的路。
 
 
【输出】 
 
 
输出1到n的最短路。如果1到达不了n，就输出-1。
 
 
【输入样例】 
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
 
【输出样例】 
90
 
【提示】 
 
 
【数据规模和约定】
 
 
1≤n≤2000
 
 
1≤m≤10000
 
 
0≤c≤10000
 
 
题解：  
#include
#define maxn 10000000
using namespace std;
int n,m,g[2003][2003],dp[2003],vis[2003];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) g[i][j]=maxn;
	}
	for(int a,b,c,i=1;i<=m;i++){
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
		g[b][a]=g[a][b];
	}
	for(int i=1;i<=n;i++) dp[i]=g[1][i];
	vis[1]=1;
	for(int i=1;i 
（3）Bellman－Ford算法
 
（4）SPFA算法
 
6.并查集 
7.最小生成树相关算法 
8.拓扑排序