图 论
1735年，数学家欧拉提出了著名的柯尼斯堡七桥（Seven Bridges of Königsberg）问题：
在柯尼斯堡（今俄罗斯加里宁格勒）有一条河流，普雷戈里亚河。人们修了七座桥把被河流分割开的陆地连接起来。旅客进行游玩的时候，在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍呢？
连通无向图G有欧拉路径的充要条件为：G中奇度顶点（即与其相连的边数目为奇数的顶点）有0个或者2个。
图的相关概念
图论（Graph Theory）以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些实体之间的某种特定关系，用点代表实体，用连接两点的线表示两个实体间具有的某种关系。图可以表示为G=（V，E），其中V是顶点的有穷（非空）集合，E为边的集合。
1、图的分类：
无向图：边集E（G）中为无向边。
有向图：边集E（G）中为有向边。
带权图 ：边上带有权的图。也称为网。（有向带权图、无向带权图）
简单图 (simple graph)：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。
2、顶点的度、入度、出度
顶点的度：与该顶点相关联的边的数目，有奇点、偶点之分。
对于有向图：有入度和出度之分
入度：该顶点的入边的数目。
出度：该顶点的出边的数目。
与度相关的几个问题
一个图中，全部顶点的度数为所有边数的2倍；
有向图中所有顶点的入度之和等于所有顶点的出度之和；
任意一个无向图一定有偶数个奇点；
具有至少两个顶点的简单无向图中一定存在度相同的结点。
3、完全图、稠密图、稀疏图
完全图：
若是无向图中，则每两个顶点之间都存在着一条边；若是有向图，则每两个顶点之间都存在着方向相反的两条边。
n阶的完全有向图含有n(n-1)条边，n阶完全无向图含有n(n-1)/2条边
稀疏图 (sparse graph)：
若一张图的边数远小于其点数的平方，那么它是一张 稀疏图。
稠密图 (dense graph)：
若一张图的边数接近其点数的平方，那么它是一张 稠密图 。
4、路径
在图G=(V,E)中，若从顶点vi出发，沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vi vp1 vp2 … vpm vj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、…、(vpm,vj)应是属于E的边。非带权图的路径长度是指路径上边的条数。带权图的路径长度是指路径上各边的权之和。
若路径上除vi、vj外其余各顶点均不互相同，则称这样的路径为简单路径。起点和终点相同的简单路径称为简单回路或环。
5、连通和连通分量
连通：
在一个图中，如果从顶点U到顶点V有路径，则称U和V是连通的；
连通图：
如果一个无向图中，任意两个顶点之间都是连通的，则称该无向图为连通图。否则称为非连通图；左图为一个连通图。
连通分量：
一个无向图的连通分支定义为该图的最大连通子图，左图的连通分量是它本身。
注意：
任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
6、强连通图和强连通分量
强连通图：在一个有向图中，对于任意两个顶点U和V，都存在着一条从U到V的有向路径，同时也存在着一条从V到U的有向路径，则称该有向图为强连通图；右图不是一个强连通图。
强连通分量：一个有向图的强连通分量定义为该图的最大的强连通子图，右图含有两个强连通分量，一个是1和2构成的一个子图，一个是3独立构成的一个子图。
注意：
强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。
图的存储
本课程主要介绍三种图的存储方式：邻接矩阵、邻接表（用数组模拟）、边集数组。
1、邻接矩阵
相邻矩阵是表示顶点间相邻关系的矩阵。若G=（V，E）是一个具有n个顶点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*n
//邻接矩阵的参考程序片段
int i,j,k,e,n,w,g[101][101];
int main() { int i,j;
memset(g, 0x3f, sizeof(g));
//如果是double数组，采用memset(g,127,sizeof(g))可全部初始化为1.38*10^306
cin >> e;
for (k = 1; k <= e; k++)
{ cin >> i >> j >> w;
g[i][j] = w; //对于不带权的图g[i][j]=1
g[j][i] = w; //无向图的对称性,如果是有向图则不要有这句！
}
}
邻接矩阵存储的特点
1、占用的存储单元数只与顶点数有关而与边数无关，n*n的二维数组。
2、方便度数的计算。
3、容易判断两点之间是否有边相连。
4、寻找一个点相连的所有边需要一个一到n的循环。
2、邻接表
结点 邻接点指针
邻接点 边权值 下一个邻接点指针
数组模拟邻接表方法一
int g[101][101];
寻找顶点i有边相连的点可以这样来做，g[i][0]表示i发出的边的数量，g[i][j]表示i发出的第j条边是通向哪个顶点的。
for (int j = 1; j <= g[i][0]; j++)
......g[i][j].....
这样就可以处理i发出的每条边，也就能找到顶点i有边相连的顶点。
数组模拟邻接表方法二
用c++stl中的
不定长数组vector存储;
#include<bits/stdc++.h>
using namespace std;
#define N 100000+5
struct node
{
int to,cost;
};
vector<node >adj[N];
int main()
{
int n,m,start;
node c;
cin>>n>>m;
for (int i=0;i<m;i++)
{
cin>>start>>c.to>>c.cost;
adj[start].push_back(c);
}
cout<<endl;
for (int i=1;i<=n;i++)
for (int j=0;j<adj[i].size();j++)
cout<<i<<" "<<adj[i][j].to<<" "<<adj[i][j].cost<<" "<<endl;
}
数组模拟邻接表方法三
数组模拟邻接表存储: 大多数情况下只要用数组模拟即可。
参考程序段：
#include <iostream>
using namespace std;
const int maxn=1001,maxm=100001;
struct edge
{
int next; //下一条边的编号
int to; //这条边到达的点
}edge[maxm];
int head[maxn],num_edge,n,m,u,v;
void add_edge(int from,int to) //加入一条从from到to的单向边
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
int main(){
num_edge=0;
scanf("%d %d",&n,&m); //读入点数和边数
for(int i=1;i<=m;i++){
scanf("%d %d",&u,&v); //u、v之间有一条边
add_edge(u,v);
}
int j,chudu[maxn];
for(int i=0;i<n;i++){ //求出每一个顶点的出度
int tot=0;
for(j=head[i];j!=0;j=edge[j].next)
tot++;
chudu[i]=tot;
}
return 0;
}
//两种方法各有用武之地，需按具体情况，具体选用。
邻接表存储特点
1、对于稀疏图，邻接表可以节省内存。
2、可以快速找到与当前顶点相连的点。
3、判断两点是否相连不如邻接矩阵快速。
3、边集数组
边集数组：
是利用一维数组存储图中所有边的一种图的表示方法。
图的遍历
从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。
遍历可以采取两种方法进行：
深度优先遍历
广度优先遍历
图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。
1、图的深度优先遍历
DFS算法实现框架
DFS( //顶点 i ) { //从顶点 i 进行深度优先搜索
visited[ i ] = 1; //将顶点 i 的访问标志置为 1
for( j=1; j<=n; j++ ) { //对其他所有顶点 j
//j 是 i 的邻接顶点，且顶点 j 没有访问过
if( a[i][j]==1 && !visited[j] ){
//递归搜索前的准备工作需要在这里写代码
DFS( j ) //从顶点 j 出发进行 DFS 搜索
//以下是 DFS 的回退位置
//在很多应用中需要在这里写代码
}
}
}
例：对图进行存储与遍历：
输入：
第一行：顶点数n。
第二行：边数m。
以下m行，每行两个顶点编号u，v。
//DFS参考代码
#include <cstdio>
using namespace std;
const int maxn = 1010;
int a[maxn][maxn];
int vis[maxn];
int n,m;
void dfs(int u){
printf("%d\n",u);
vis[u] = 1;
for(int i = 1; i <= n; i++)
if(a[u][i] == 1 && vis[i] == 0)
dfs(i);
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i++){
int x,y;
scanf("%d%d",&x,&y);
a[x][y] = a[y][x] = 1;
}
dfs(1);
return 0;
}
//为了避免重复访问某个顶点，可以设一个标志数组vis[i]，未访问时值为0，访问一次后就改为1。
//图的深度优先遍历类似于树的先根遍历。
欧拉路：
从图中某个点出发，遍历整个图，图中每条边通过且只通过一次。
欧拉回路：
起点和终点相同的欧拉路。
关于欧拉路和欧拉回路，我们有以下两个定理。
定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。
定理2：存在欧拉回路的条件：图是连通的，有0个奇点。
怎么找到一条欧拉路呢？
例1.一笔画问题(一本通1341)
【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行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<bits/stdc++.h>
using namespace std;
#define maxn 101
int g[maxn][maxn]; //此图用邻接矩阵存储
int du[maxn]; //记录每个点的度，就是相连的边的数目
int circuit[maxn*maxn]; //用来记录找到的欧拉路的路径
int n,e,circuitpos,i,j,x,y,start;
void find_circuit(int i) //这个点深度优先遍历过程寻找欧拉路
{ int j;
for (j = 1; j <= n; j++)
if (g[i][j] == 1) //从任意一个与它相连的点出发
{
g[j][i] = g[i][j] = 0;
find_circuit(j);
}
circuit[++circuitpos] = i; //记录下路径
}
int main()
{
memset(g,0,sizeof(g));
cin >> n >> e;
for (i = 1; i <= e; i++)
{ cin >> x >> y;
g[y][x] = g[x][y] = 1;
du[x]++; du[y]++; //统计每个点的度
}
start = 1; //如果有奇点，就从奇点开始寻找，这样找到的就是
for (i = 1; i <= n; i++) //欧拉路。没有奇点就从任意点开始，
if (du[i]%2 == 1) //这样找到的就是欧拉回路。(因为每一个点都是偶点)
start = i;
circuitpos = 0;
find_circuit(start);
for (i = 1; i <= circuitpos; i++)
cout << circuit[i] << ' ';
cout << endl;
return 0;
}
哈密尔顿环
欧拉回路是指不重复地走过所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。
可使用深度优先搜索求一张图中所有的哈密尔顿环。
2、图的广度优先遍历
广度优先遍历的实现：
为避免重复访问，也需要一个状态数组 vis[n]，用来存储各顶点的访问状态。如果 vis[i] = 1，则表示顶点 i 已经访问过；如果 vis[i] = 0，则表示顶点 i 已经访问过。初始时，各顶点的访问状态均为 0。
为了实现逐层访问， BFS 算法在实现时需要使用一个队列.
BFS 算法实现框架：
BFS( //顶点 i ) //从顶点 i 进行广度优先搜索{
visited[ i ] = 1; //将顶点 i 的访问标志置为 1
将顶点 i 入队列;
while( 队列不为空 ){
取出队列头的顶点，设为 k
for( j=0; j<n; j++ ) //对其他所有顶点 j{
//j 是 k 的邻接顶点，且顶点 j 没有访问过
if( a[k][j]==1 && !visited[j] ){
将顶点 j 的访问标志置为 1
将顶点 j 入队列
}
} //end of for
} //end of while
} //end of BFS
BFS参考代码
#include <iostream>
using namespace std;
const int maxn = 1010;
int q[maxn], a[maxn][maxn], vis[maxn]; int n,m;
void bfs(int u){
int head = 0, tail = 1;
q[0] = u; vis[u] = 1;
while(head < tail){
int p = q[head++];
cout << p << endl;
for(int i = 1; i <= n; i++){
if(a[p][i] == 1 && vis[i] == 0){
q[tail++]=i; vis[i]=1;
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
a[x][y] = a[y][x] = 1;
}
bfs(1);
return 0;
}
3.非连通图的遍历
如果一个图不是连通图，那么一次DFS或BFS只能遍历一个连通分量，每次找一个没有遍历的顶点i作为起点dfs(i)或bfs(i)即可。
应用举例：计算无向图的连通分量数量，调用dfs(i)或bfs(i)的次数就是连通分量数量。
算法：
for(int i=1;i<=n;i++)
if(!vis[i]){
dfs(i); //或bfs(i);
cnt++; //连通分量个数
}
例2.骑马修栅栏（一本通1375）
【题目描述】
农民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<bits/stdc++.h>
using namespace std;
int d[1010],ans[1010],map[1010][1010],n,cnt=0,max1=0;
void dfs(int v){
for(int i=1;i<=max1;i++){//从1寻找到最大值的点max1//这里也是因为矩阵存储，所以会从小到大寻找
if(map[v][i]>0){
map[v][i]--;
map[i][v]--;
dfs(i);
}
}
cnt++;//因为最后找的点在dfs里最先出来，所以我们记录下来dfs出来的值倒序输出
ans[cnt]=v;
}
int main(){
cin>>n;
int u,v;
for(int i=1;i<=n;i++){
cin>>u>>v;
map[u][v]++;//因为可能他给你好多栅栏的两侧都是同一组点，比如说给你三组数据：1 2 < 2 1 <1 2 那么就有三个栅栏，所以按照边数记录一共多少个点；
map[v][u]++;
d[u]++;//记录u连着几条边
d[v]++;//记录v连着几条边
max1=max(max(max1,u),v);//记录点的最大值；
}
int find=0;
for(int i=1;i<=max1;i++)//！！一定注意要从1寻找到最大的点而不是寻找到n //也是因为用矩阵存储，所以会从小到大寻找
if(d[i]%2==1){//如果有边数为奇数的点，那么就从最小的那个奇数点开始找
find=i;
break;
}
if(find==0){
for(int i=1;i<=max1;i++)
if(d[i]>0){//如果没有奇数点从最小的有边的点开始dfs
find=i;
break;
}
}
dfs(find);
for(int i=cnt;i>=1;i--)//因为最后找的点在dfs里最先出来，所以我们记录下来dfs出来的值倒序输出
cout<<ans[i]<<endl;
}
例3. 公司数量
【问题描述】
在某个城市里住着n个人，现在给定关于n个人的m条信息（即某2个人认识），假设所有认识（直接或间接认识都算认识）的人一定属于同一个公司。
若是某两人不在给出的信息里，那么他们不认识，属于两个不同的公司。
已知人的编号从1至n。
请计算该城市最多有多少公司。
【输入】
第一行：n（<=10000，人数）
第二行：m（<=100000，信息）
以下若干行：每行两个数i和j，中间一个空格隔开，表示i和j相互认识。
【输出】
公司的数量。
【数据规模】
100%的数据：n<=10000；m<=100000
city.in
11
9
1 2
4 5
3 4
1 3
5 6
7 10
5 10
6 10
8 9
city.out
3
分析：
以人为图的顶点，相互认识的建立无向边，求无向图的连通分量的个数。
//深度优先参考代码
#include <cstdio>
using namespace std;
const int maxn=10010;
int a[maxn][maxn];
int vis[maxn];
int n,m,cnt;
void dfs(int k){
vis[k]=1;
for(int i=1;i<=n;i++)
if(!vis[i]&&a[k][i]) dfs(i);
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
dfs(i);
cnt++;
}
printf("%d\n",cnt);
return 0;
}
//广度优先参考代码
#include <cstdio>
const int maxn=10010;
int a[maxn][maxn], vis[maxn], q[maxn]; int n,m,cnt;
void bfs(int k){
int head=0,tail=1;
q[0]=k; vis[k]=1;
while(head<tail){
int p=q[head++];
for(int i=1;i<=n;i++){
if(!vis[i]&&a[p][i]){ q[tail++]=i; vis[i]=1; }
}
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
}
for(int i=1;i<=n;i++)
if(!vis[i]) { bfs(i); cnt++; }
printf("%d\n",cnt);
return 0;
}
例4. 油田(poj1562)
【题目描述】https://www.luogu.com.cn/problem/UVA572
GeoSurvComp地质探测公司负责探测地下油田。每次GeoSurvComp公司都是在一块长方形的土地上来探测油田。在探测时，他们把这块土地用网格分成若干个小方块，然后逐个分析每块土地，用探测设备探测地下是否有油田。方块土地底下有油田则称为pocket，如果两个pocket相邻，则认为是同一块油田，油田可能覆盖多个pocket。
你的工作是计算长方形的土地上有多少个不同的油田。
【输入描述】
输入文件中包含多个测试数据，每个测试数据描述了一个网格。
每个网格数据的第一行为两个整数：m、n，分别表示网格的行和列；如果m=0，则表示输入结束，否则，接下来有m行数据，每行数据有n个字符（不包括行结束符）。每个字符代表一个小方块，如果为”*”，则代表没有石油，如果为”@”，则代表有石油，是一个 pocket。 1≤m≤100，1≤n≤100。
【输出描述】
对输入文件中的每个网格，输出网格中不同的油田数目。如果两块不同的pocket在水平、垂直、或者对角线方向上相邻，则被认为属于同一块油田。每块油田所包含的pocket 数目不会超过100。
输入样例
3 5
*@*@*
**@**
*@*@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
输出样例
1
2
分析：
从网格中某个“@”字符位置开始进行 DFS 搜索，可以搜索到跟该“@”字符位置同属一块油田的所有“@”字符位置。
遍历整个图，求图的连通分量。注意是8连通。
//DFS油田
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=110;
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,1,1,-1};
int g[maxn][maxn];
int n,m,cnt;
void dfs(int x,int y){
g[x][y]=0;
for(int i=0;i<8;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]==1){
dfs(xx,yy);
}
}
}
int main(){
while((cin>>n>>m)&&m){
char ch;
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>ch;
g[i][j]=(ch=='@'?1:0);
}
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(g[i][j]==1){ dfs(i,j); cnt++; }
cout<<cnt<<endl;
}
return 0;
}
//BFS油田
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=110;
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,1,1,-1};
int g[maxn][maxn];
int n,m,cnt;
struct node{
int x,y;
}cur,nxt;
node q[maxn*maxn];
void bfs(int x,int y){
int head=0; tail=1;
g[x][y]=0; q[0].x=x; q[0].y=y;
while(head<tail){
cur=q[head++];
for(int i=0;i<8;i++){
int xx=cur.x+dx[i], yy=cur.y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]==1){
g[xx][yy]=0;
nxt.x=xx;
nxt.y=yy;
q[tail++]=nxt;
}
}
}
}
int main(){
while((cin>>n>>m)&&m)){
char ch;
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>ch;
g[i][j]=(ch=='@'?1:0);
}
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(g[i][j]==1){ bfs(i,j); cnt++; }
cout<<cnt<<endl;
}
return 0;
}
例5.（洛谷P2052 [NOI2011] 道路修建）
【问题描述】
在 W 星球上有 n个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 n - 1 条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4 个国家，如果该道路长度为 1，则费用为 1×|2 - 4|=2。图中圆圈里的数字表示国家的编号。由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。
【输入格式】
输入的第一行包含一个整数 n，表示 W 星球上的国家的数量，国家从 1 到 编号。
接下来 n–1行描述道路建设情况，其中第 i行包含三个整数 ai，bi，ci，表示第i条双向道路修建在ai与bi两个国家之间，长度为ci。
【输出格式】
输出一个整数，表示修建所有道路所需要的总费用。
【输入样例】
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
【输出样例】
20
参考代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000010;
ll n,cnt,ans;
ll size[maxn],head[maxn];
struct node{
int w,to,nt;
}e[maxn*2];
void add(int x,int y,int z){
e[++cnt].to=y; e[cnt].nt=head[x]; e[cnt].w=z; head[x]=cnt;
}
void dfs(int x,int fa){
size[x]=1;
for(int i=head[x];i;i=e[i].nt){
int to=e[i].to;
if(fa==to) continue;
dfs(to,x);
size[x]+=size[to];
ans+=e[i].w*abs(2*size[to]-n);
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
拓扑排序
1. AOV网
在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动” ）组成的集合，这些活动之间存在一些先后关系，即某些子活动必须在其它一些活动完成之后才能开始，我们可以用有向图来形象地表示这些活动之间的先后关系，活动为顶点，活动之间的先后关系为有向边，这种有向图称为“顶点活动网络” ，又称“AOV网”。
把一条有向边起点的活动称为终点活动的前驱活动，终点的活动称为起点活动的后继活动。而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。例如在下图中，只有当1完成之后，2、3、4、5、6才能开始进行。只有当2、3、4全部完成之后，7才能开始进行。
一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。
检查有向图中是否存在回路的方法，是对有向图进行拓扑排序。
2. 拓扑排序算法
拓扑排序算法，只适用于AOV网（有向无环图）。
按照有向图给出的次序关系，将图中顶点排成一个线性序列， 使得每个活动的所有前驱活动都排在该活动的前面，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑有序序列”。
一个AOV网的拓扑序列是不唯一的，例如下面的有向图，它的拓扑序列可以是ABCDE，也可以是ACBDE，或是ADBCE。
算法思想：
(1) 选择一个入度为0的顶点并输出。
(2) 从AOV网中删除此顶点及以此顶点为起点的所有边。
(3) 重复上述两步，直到不存在入度为0的顶点为止。
(4) 若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。
从第四步可以看出，拓扑排序可以用来判断一个有向图是否有环。只有有向无环图才存在拓扑序列。
算法实现：
(1) 数据结构：
indgr[i]：顶点i的入度
stack[ ]：栈，存储入度为0的顶点
(2) 初始化:top=0 (栈顶指针置零)
(3) 将初始状态所有入度为0的顶点入栈
(4) i=0 (计数器)
(5) while 栈非空(top>0)
① 栈顶的顶点v出栈; top-1; 输出v; i++;
② for v的每一个后继顶点u
a. indgr[u]--; //u的入度减1
b. if （u的入度变为0） 顶点u入栈
(6) 算法结束
例6. 家谱树
【问题描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
【输入格式】
第1行一个整数N（1<=N<=100），表示家族的人数。
接下来N行，第i行描述第i个人的儿子。
每行最后是0表示描述完毕。
【输出格式】
输出一个序列，使得每个人的后辈都比那个人后列出。
如果有多解输出任意一解。
#include<iostream>
using namespace std;
int a[101][101],c[101],r[101],ans[101];
int i,j,tot,temp,num,n,m;
int main(){
cin >> n;
for (i = 1; i <= n; i++){
do{
cin >> j;
if (j !=0 ){
c[i]++; //c[i]用来存i的出度
a[i][c[i]] = j;
r[j]++; //r[j]用来存j的入度
}
} while (j != 0);
}
for (i = 1; i <= n; i++)
if (r[i] == 0)
ans[++tot] = i;//把图中所有入度为0的顶点入栈，栈用一维数组ans[]表示
do{
temp = ans[tot];
cout << temp << " ";
tot--;num++;//栈顶元素出栈输出
for (i = 1; i <= c[temp]; i++){
r[a[temp][i]]--;
if (r[a[temp][i]] == 0) //如果入度减1后变成0，则将这个顶点入栈
ans[++tot] = a[temp][i];
}
}while (num != n);//如果输出的点的数目num等于n，说明算法结束
return 0;
}
例7.奖金（一本通1352）
【问题描述】
由于无敌的凡凡在 2005 年世界英俊帅气男总决选中胜出，Yali Company 总经理 Mr.Z 心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是 Mr.Z下令召开 m 方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工 a 的奖金应该比 b 高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为 100 元。
【输入格式】
第一行两个整数 n,m，表示员工总数和代表数；以下 m 行，每行 2 个整数 a,b，表示某个代表认
为第 a 号员工奖金应该比第 b 号员工高。
【输出格式】
若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。
【输入样例】
2 1
1 2
【输出样例】
201
```
【数据规模】
80％的数据满足 n<=1000，m<=2000；100％的数据满足 n<=10000，m<=20000。
#### 分析：首先构图，若存在条件“a 的钱比 b 多”则从 b 引一条有向指向 a；然后拓扑排序，若无法完成排序则表示问题无解（存在圈）；若可以得到完整的拓扑序列，则按序列顺序进行递推。
#### 参考代码：
```cpp
#include<iostream>
using namespace std;
int a[10001][301]={0},into[10001],ans[10001],m,n,money,head[11000],num_edge;
struct edge
{ int next; //下一条边的编号
int to; //这条边到达的点
}edge[21000];
void add_edge(int from,int to) //加入一条从from到to的单向边
{ edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
void init() //读入数据，并构建图，统计入度
{ int i,x,y;
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>x>>y;
add_edge(y,x);
into[x]++; //统计入度
}
}
bool topsort() //拓扑排序
{ int t,tot,k,i,j;
tot=0;k=0;
while(tot<n) //tot顶点个数
{ t=0; //用来判断有无环
for(i=1;i<=n;i++)
if(into[i]==0)
{ tot++;t++;money+=100;
ans[t]=i;
into[i]=0xfffffff;
}
if(t==0)return false; //存在环
money+=k*t;k++;
for(i=1;i<=t;i++) //去掉相连的边
for(j=head[ans[i]];j!=0;j=edge[j].next)
into[edge[j].to]--;
}
return true;
}
int main()
{
init();
money=0;
if(topsort())
cout<<money<<endl;
else
cout<<"Poor Xed"<<endl;
return 0;
}
哇~我好像不会用这个耶~【装疯卖傻】
几乎全乱码了
```这里放代码
```谢谢orz
感谢神犇指导，本蒟蒻悟了
会用了【嘿嘿(^▽^)】
为什么现在初中生还懂大学的内容
emm🤔
什么天才少女
例4 油田应该算搜索的吧
应该吧，晚安