最小生成树和拓扑排序课件

最小生成树和最小生成树和7 7月月月月1818日日日日最小生成树和7月18日1最小生成树最小生成树最小生成树2一、什么是图的最小生成树（MST）？不知道大家还记不记得树的一个定理：不知道大家还记不记得树的一个定理：N N个点用个点用N-1N-1条边连接条边连接成成一一个连通块个连通块，形成的图形只可能是树，没有别的可能。，形成的图形只可能是树，没有别的可能。一个有一个有N N个点的图，边一定是大于等于个点的图，边一定是大于等于N-1N-1条的。图的最小生成树，条的。图的最小生成树，就是在这些边中选择就是在这些边中选择N-1N-1条出来，连接所有的条出来，连接所有的N N个点。这个点。这N-1N-1条边的边权之条边的边权之和是所有方案中最小的。和是所有方案中最小的。一、什么是图的最小生成树（MST）？一个有N个点的图，3二、最小生成树用来解决什么问题？就是用来解决如何用最小的就是用来解决如何用最小的“代价代价”用用N-1N-1条边连接条边连接N N个点的问题。个点的问题。【引例】【引例】有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？造价最少？123452471162二、最小生成树用来解决什么问题？就是用来解决如何用最4Prim算法算法分析算法分析&思想讲解：思想讲解：Prim Prim算法采用算法采用“蓝白点蓝白点”思想：思想：白点代表已经进入最小生成树的点，白点代表已经进入最小生成树的点，蓝点代表未进入最小生成树的点。蓝点代表未进入最小生成树的点。Prim Prim算法每次循环都将一个蓝点算法每次循环都将一个蓝点u u变为白点，并且此蓝点变为白点，并且此蓝点u u与白点相连与白点相连的最小边权的最小边权minuminu还是当前所有蓝点还是当前所有蓝点中最小的。这样相当于向生成树中添中最小的。这样相当于向生成树中添加了加了n-1n-1次最小的边，最后得到的一次最小的边，最后得到的一定是最小生成树。定是最小生成树。我们通过对右图最小生成树的求我们通过对右图最小生成树的求解模拟来理解上面的思想。蓝点和虚解模拟来理解上面的思想。蓝点和虚线代表未进入最小生成树的点、边；线代表未进入最小生成树的点、边；白点和实线代表已进入最小生成树的白点和实线代表已进入最小生成树的点、边。点、边。123452471162Prim算法算法分析&思想讲解：1234524711625初始时所有点都是蓝点，初始时所有点都是蓝点，min1=0,min2min1=0,min2、3 3、4 4、5=5=。权值之和。权值之和MST=0MST=0。123452471162第一次循环自然是找到min1=0最小的蓝点1。将1变为白点，接着枚举与1相连的所有蓝点2、3、4，修改它们与白点相连的最小边权。123452471162min2=w12=2;min3=w13=4;min4=w14=7;123452471162第一次循环自然是找到min1=06第二次循环是找到第二次循环是找到min2min2最小的蓝点最小的蓝点2 2。将。将2 2变为白点，接着枚举与变为白点，接着枚举与2 2相连的所有蓝相连的所有蓝点点3 3、5 5，修改它们与白点相连的最小边权。，修改它们与白点相连的最小边权。123452471162min3=w23=1;min5=w25=2;第三次循环是找到第三次循环是找到min3min3最小的蓝点最小的蓝点3 3。将。将3 3变为白点，接着枚举与变为白点，接着枚举与3 3相连的所有相连的所有蓝点蓝点4 4、5 5，修改它们与白点相连的最小边权。，修改它们与白点相连的最小边权。123452471162min4=w34=1;由于min5=2 w35=6;所以不修改min5的值。123452471162min3=w23=1;7最后两轮循环将点最后两轮循环将点4 4、5 5以及边以及边w25,w34w25,w34添加进最小生成树。添加进最小生成树。123452471162最后权值之和MST=6。这n次循环，每次循环我们都能让一个新的点加入生成树，n次循环就能把所有点囊括到其中；每次循环我们都能让一条新的边加入生成树，n-1次循环就能生成一棵含有n个点的树；每次循环我们都取一条最小的边加入生成树，n-1次循环结束后，我们得到的就是一棵最小的生成树。这就是Prim采取贪心法生成一棵最小生成树的原理。算法时间复杂度：O(N2)。123452471162最后权值之和MST=6。8算法描述：算法描述：以以1 1为起点生成最小生成树，为起点生成最小生成树，minvminv表示蓝点表示蓝点v v与白点与白点相连的最小边权。相连的最小边权。MSTMST表示最小生成树的权值之和。表示最小生成树的权值之和。a a）初始化：）初始化：minv=(v1);min1=0;MST=0;minv=(v1);min1=0;MST=0;b b）for(i=1;i=n;i+)for(i=1;i=n;i+)1.1.寻找寻找minuminu最小的蓝点最小的蓝点u u。2.2.将将u u标记为白点标记为白点3.MST+=minu3.MST+=minu4.for 4.for 与白点与白点u u相连的所有蓝点相连的所有蓝点v v if(wuvminv)if(wuvminv)minv=wuv;minv=wuv;c c）算法结束：）算法结束：MST MST即为最小生成树的权值之和即为最小生成树的权值之和算法描述：9【例【例1 1】、最优布线问题】、最优布线问题 【问题描述】【问题描述】学校有学校有n n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同，因此不同的计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。的或间接的）。【输入格式】【输入格式】输入文件输入文件wire.inwire.in，第一行为整数，第一行为整数n n（2=n=1002=n=100），表示计算机的数目。此后），表示计算机的数目。此后的的n n行，每行行，每行n n个整数。第个整数。第x+1x+1行行y y列的整数表示直接连接第列的整数表示直接连接第x x台计算机和第台计算机和第y y台计算机台计算机的费用。的费用。【输出格式】【输出格式】输出文件输出文件wire.outwire.out，一个整数，表示最小的连接费用。，一个整数，表示最小的连接费用。【输入样例】【输入样例】3 30 1 20 1 21 0 11 0 12 1 02 1 0【输出样例】【输出样例】2 2 （注：表示连接（注：表示连接1 1和和2 2，2 2和和3 3，费用为，费用为2 2）【例1】、最优布线问题 10【参考程序参考程序】#include#include#include#include#include#includeusing namespace std;using namespace std;int g101101;/int g101101;/邻接矩阵邻接矩阵int minn101;/minniint minn101;/minni存放蓝点存放蓝点i i与白点相连的最小边权与白点相连的最小边权bool u101;/ui=Truebool u101;/ui=True，表示顶点，表示顶点i i还未加入到生成树中还未加入到生成树中 /ui=False /ui=False，表示顶点，表示顶点i i已加入到生成树中已加入到生成树中 int n,i,j;int n,i,j;int main()int main()cin n;cin n;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=n;j+)for(j=1;j gij;cin gij;memset(minn,0 x7f,sizeof(minn);/memset(minn,0 x7f,sizeof(minn);/初始化为初始化为maxintmaxint minn1=0;minn1=0;memset(u,1,sizeof(u);/memset(u,1,sizeof(u);/初始化为初始化为TrueTrue，表示所有顶点为蓝点，表示所有顶点为蓝点【参考程序】11for(i=1;i=n;i+)for(i=1;i=n;i+)int k=0;int k=0;for(j=1;j=n;j+)/for(j=1;j=n;j+)/找一个与白点相连的权值最小的蓝点找一个与白点相连的权值最小的蓝点k k if(uj&(minnj minnk)if(uj&(minnj minnk)k=j;k=j;uk=false;/uk=false;/蓝点蓝点k k加入生成树，标记为白点加入生成树，标记为白点 for(j=1;j=n;j+)/for(j=1;j=n;j+)/修改与修改与k k相连的所有蓝点相连的所有蓝点 if(uj&(gkj minnj)if(uj&(gkj minnj)minnj=gkj;minnj=gkj;int total=0;int total=0;for(i=1;i=n;i+)/for(i=1;i=n;i+)/累加权值累加权值 total+=minni;total+=minni;cout total endl;cout total endl;return 0;return 0;知识扩展：本算法在移动通信、智能交通、移动物流、生产调度等物联网相关领域知识扩展：本算法在移动通信、智能交通、移动物流、生产调度等物联网相关领域都有十分现实的意义，采用好的算法，就能节省成本提高效率。都有十分现实的意义，采用好的算法，就能节省成本提高效率。for(i=1;i=n;i+)12 【引例】【引例】有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？造价最少？123452128967310 12345212896731013Kruskal算法KruskalKruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。Kruskal Kruskal算法将一个连通块当做一个集合。算法将一个连通块当做一个集合。KruskalKruskal首先将所有的边按从小到大首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n n个独立的集合。个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了属于同一集合，就跳过。直到选取了n-1n-1条边为止。条边为止。123452128967310Kruskal算法Kruskal（克鲁斯卡尔）算法是一种14思想讲解：思想讲解：KruskalKruskal（克鲁斯卡尔）算法开始时，认为每一个点都是孤立的，分属于（克鲁斯卡尔）算法开始时，认为每一个点都是孤立的，分属于n n个独立的个独立的集合。集合。1234521289673105 5个集合个集合 1 1，22，33，44，5 5 生成树中没有边生成树中没有边KruskalKruskal每次都选择一条最小的边，而且这条边的两个顶点分属于两个每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。不同的集合。将选取的这条边加入最小生成树，并且合并集合。1234521289673105个集合 1，2，15第一次选择的是第一次选择的是这条边，将这条边加入到生成树中，并且将它的两个顶点这条边，将这条边加入到生成树中，并且将它的两个顶点1 1、2 2合并成一个集合。合并成一个集合。1234521289673104 4个集合个集合 1 1，22，33，44，5 5 生成树中有一条边生成树中有一条边 第二次选择的是第二次选择的是这条边，将这条边加入到生成树中，并且将它的两个顶点这条边，将这条边加入到生成树中，并且将它的两个顶点4 4、5 5合并成一个集合。合并成一个集合。1234521289673103 3个集合个集合 1 1，22，33，44，5 5 生成树中有生成树中有2 2条边条边 ，第一次选择的是这条边，将这条边加入到生成树中，并且16第三次选择的是第三次选择的是这条边，将这条边加入到生成树中，并且将它的两个顶点这条边，将这条边加入到生成树中，并且将它的两个顶点3 3、5 5所在的两个集合合并成一个集合所在的两个集合合并成一个集合1234521289673102 2个集合个集合 1 1，22，33，4 4，5 5 生成树中有生成树中有3 3条边条边 ，35第四次选择的是第四次选择的是这条边，将这条边加入到生成树中，并且将它的两这条边，将这条边加入到生成树中，并且将它的两个顶点个顶点2 2、5 5所在的两个集合合并成一个集合。所在的两个集合合并成一个集合。1234521289673101 1个集合个集合 1 1，2 2，3 3，4 4，5 5 生成树中有生成树中有4 4条边条边 ，35，第三次选择的是这条边，将这条边加入到生成树中，并且17 算法结束，最小生成树权值为算法结束，最小生成树权值为1919。通过上面的模拟能够看到，通过上面的模拟能够看到，KruskalKruskal算法每次都选择一条最小的，且能算法每次都选择一条最小的，且能合并两个不同集合的边，一张合并两个不同集合的边，一张n n个点的图总共选取个点的图总共选取n-1n-1次边。因为每次我们次边。因为每次我们选的都是最小的边，所以最后的生成树一定是最小生成树。每次我们选的选的都是最小的边，所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合，最后边都能够合并两个集合，最后n n个点一定会合并成一个集合。通过这样的贪个点一定会合并成一个集合。通过这样的贪心策略，心策略，KruskalKruskal算法就能得到一棵有算法就能得到一棵有n-1n-1条边，连接着条边，连接着n n个点的最小生成树。个点的最小生成树。Kruskal Kruskal算法的时间复杂度为算法的时间复杂度为O(E*logE)O(E*logE)，E E为边数。为边数。18算法描述算法描述:1.1.初始化并查集。初始化并查集。fatherx=xfatherx=x。2.2.tot=0tot=03.3.将所有边用快排从小到大排序。将所有边用快排从小到大排序。4.4.计数器计数器 k=0;k=0;5.5.for(i=1;i=M;i+)/for(i=1;i=M;i+)/循环所有已从小到大排序的边循环所有已从小到大排序的边 if if 这是一条这是一条u,vu,v不属于同一集合的边不属于同一集合的边(u,v)(u,v)(因为已经排序，所以必为最小因为已经排序，所以必为最小)beginbegin 合并合并u,vu,v所在的集合，相当于把边所在的集合，相当于把边(u,v)(u,v)加入最小生成树。加入最小生成树。tot=tot+W(u,v)tot=tot+W(u,v)k+k+如果如果k=n-1,k=n-1,说明最小生成树已经生成，则说明最小生成树已经生成，则break;break;end;end;6.6.结束，结束，tottot即为最小生成树的总权值之和。即为最小生成树的总权值之和。算法描述:19【例例2 2】、最短网络、最短网络Agri-Net Agri-Net 【问题描述问题描述】农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000100000。【输入格式输入格式】第一行：第一行：农场的个数，农场的个数，N N（3=N=1003=N=100）。）。第二行第二行.结结尾尾后来的行包含了一个后来的行包含了一个N*NN*N的矩阵的矩阵,表示每个农场之间的距离。理论表示每个农场之间的距离。理论上，他们是上，他们是N N行，每行由行，每行由N N个用空格分隔的数组成，实际上，他们个用空格分隔的数组成，实际上，他们限制在限制在8080个字符，因此，某些行会紧接着另一些行。当然，对角个字符，因此，某些行会紧接着另一些行。当然，对角线将会是线将会是0 0，因为不会有线路从第，因为不会有线路从第i i个农场到它本身。个农场到它本身。【输出格式输出格式】只有一个输出，其中包含连接到每个农场的光纤的最小长度。只有一个输出，其中包含连接到每个农场的光纤的最小长度。【输入样例输入样例】agrinet.inagrinet.in 4 4 0 4 9 21 0 4 9 21 4 0 8 17 4 0 8 17 9 8 0 16 9 8 0 16 21 17 16 0 21 17 16 0【输出样例输出样例】agrinet.outagrinet.out2828【例2】、最短网络Agri-Net 第一行：农场的个数，20【参考程序】【参考程序】#include#include#include#include#include /sort()#include /sort()需要用到需要用到库库using namespace std;using namespace std;struct pointstruct point int x;int x;int y;int y;int v;int v;/定义结构类型，表示边定义结构类型，表示边point a9901;point a9901;/存边存边int fat101;int fat101;int n,i,j,x,m,tot,k;int n,i,j,x,m,tot,k;int father(int x)int father(int x)if(fatx!=x)fatx=father(fatx);if(fatx!=x)fatx=father(fatx);return fatx;return fatx;void unionn(int x,int y)void unionn(int x,int y)int fa=father(x);int fa=father(x);int fb=father(y);int fb=father(y);if(fa!=fb)fatfa=fb;if(fa!=fb)fatfa=fb;【参考程序】21int cmp(const point&a,const point&b)/sort()int cmp(const point&a,const point&b)/sort()自定义的比较函数自定义的比较函数 if(a.v b.v)return 1;if(a.v n;cin n;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=n;j+)for(j=1;j x;cin x;if(x!=0)if(x!=0)m+;m+;am.x=i;am.y=j;am.v=x;am.x=i;am.y=j;am.v=x;for(i=1;i=n;i+)fati=i;for(i=1;i=n;i+)fati=i;sort(a+1,a+m+1,cmp);/C+sort(a+1,a+m+1,cmp);/C+标准库中自带的快排标准库中自带的快排 /cmp/cmp为自定义的比较函数。表示为自定义的比较函数。表示a a数组的数组的1-m1-m按规则按规则cmpcmp排序排序int cmp(const point&a,const p22for(i=1;i=m;i+)for(i=1;i=m;i+)if(father(ai.x)!=father(ai.y)if(father(ai.x)!=father(ai.y)unionn(ai.x,ai.y);unionn(ai.x,ai.y);tot+=ai.v;tot+=ai.v;k+;k+;if(k=n-1)break;if(k=n-1)break;cout tot;cout tot;return 0;return 0;最小生成树和拓扑排序课件23上机练习1 1、局域网、局域网 【问题描述问题描述】某个局域网内有某个局域网内有n(n=100)n(n=100)台计算机，由于搭建局域网时工作人员的疏忽，现台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用线不是很畅通，我们用f(i,j)f(i,j)表示表示i,j i,j之间连接的畅通程度之间连接的畅通程度(f(i,j)=1000)(f(i,j)=1000)，f(i,j)f(i,j)值越小值越小表示表示i,j i,j之间连接越通畅，之间连接越通畅，f(i,j)f(i,j)为为0 0表示表示i,j i,j之间无网线连接。现在我们需要解决回路问之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的f(i,j)f(i,j)最大，请最大，请求出这个最大值。求出这个最大值。【输入格式输入格式】第一行两个正整数第一行两个正整数n kn k接下来的接下来的k k行每行三个正整数行每行三个正整数i j mi j m表示表示i,j i,j两台计算机之间有网线联通，通畅程度两台计算机之间有网线联通，通畅程度为为mm。【输出格式输出格式】一个正整数，一个正整数，f(i,j)f(i,j)的最大值的最大值【输入输出样例输入输出样例】【输入样例输入样例】【输出样例输出样例】5 55 51 2 81 2 81 3 11 3 11 5 31 5 32 4 52 4 53 4 23 4 28 8上机练习1、局域网 【输入样例】【输出样例】5 51 5 242 2、繁忙的都市、繁忙的都市 【问题描述问题描述】城市城市C C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市其中的道路进行改造。城市C C的道路是这样分布的：城市中有的道路是这样分布的：城市中有n n个交叉路口，有些交个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：进行改造的道路越少越好，于是他提出下面的要求：改造的那些道路能够把所有的交叉路口直接或间接的连通起来。改造的那些道路能够把所有的交叉路口直接或间接的连通起来。在满足要求在满足要求1 1的情况下，改造的道路尽量少。的情况下，改造的道路尽量少。在满足要求在满足要求1 1、2 2的情况下，改造的那些道路中分值最大值尽量小。的情况下，改造的那些道路中分值最大值尽量小。【编程任务编程任务】作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。【输入格式输入格式】city.incity.in第一行有两个整数第一行有两个整数n,mn,m表示城市有表示城市有n n个交叉路口，个交叉路口，mm条道路。接下来条道路。接下来mm行是对每行是对每条道路的描述，条道路的描述，u,v,cu,v,c表示交叉路口表示交叉路口u u和和v v之间有道路相连，分值为之间有道路相连，分值为c c。(1n300(1n300，1c10000)1c10000)【输出格式输出格式】city.outcity.out两个整数两个整数s,maxs,max，表示你选出了几条道路，分值最大的那条道路的分值是多少。，表示你选出了几条道路，分值最大的那条道路的分值是多少。【输入输出样例输入输出样例】【输入样例输入样例】【输出样例输出样例】4 54 51 2 31 2 31 4 51 4 52 4 72 4 72 3 62 3 63 4 83 4 83 63 62、繁忙的都市 【输入样例】【输出样例】4 52 3 63253 3、联络员、联络员 【问题描述问题描述】TyvjTyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着TyvjTyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为网站的逐步壮大，管理员的数目也越来越多，现在你身为TyvjTyvj管理层的管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。是间接都可以）。TyvjTyvj是一个公益性的网站，没有过多的利润，所以你要尽是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。可能的使费用少才可以。目前你已经知道，目前你已经知道，TyvjTyvj的通信渠道分为两大类，一的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。数据保证给出的通行渠道可以让所有的管理员联通。【输入格式输入格式】第一行第一行n n，mm表示表示TyvjTyvj一共有一共有n n个管理员，有个管理员，有mm个通信渠道第二行到个通信渠道第二行到m+1m+1行，每行四个非负整数，行，每行四个非负整数，p,u,v,w p,u,v,w 当当p=1p=1时，表示这个通信渠道为必选通信渠时，表示这个通信渠道为必选通信渠道；当道；当p=2p=2时，表示这个通信渠道为选择性通信渠道；时，表示这个通信渠道为选择性通信渠道；u,v,wu,v,w表示本条信息描表示本条信息描述的是述的是u u，v v管理员之间的通信渠道，管理员之间的通信渠道，u u可以收到可以收到v v的信息，的信息，v v也可以收到也可以收到u u的的信息，信息，w w表示费用。表示费用。【输出格式输出格式】最小的通信费用最小的通信费用。3、联络员 265 61 1 2 11 2 3 11 3 4 11 4 1 12 2 5 102 2 5 5【输入样例输入样例】【输出样例输出样例】9样例解释：1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通2和5号管理员，选择费用为5的渠道，所以总的费用为9 注意：u,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠道 数据范围：对于30%的数据，n=10 m=100 对于50%的数据,n=200 m=1000 对于100%的数据，n=2000m0)(top0)i.i.栈顶的顶点栈顶的顶点v v出栈；出栈；top-1;top-1;输出输出v v；i+i+；ii.ii.for vfor v的每一个后继顶点的每一个后继顶点u u 1.1.indgru-;uindgru-;u的入度减的入度减1 1 2.2.if if（u u的入度变为的入度变为0 0）顶点顶点u u入栈入栈 f)f)算法结束算法结束这个程序采用栈来找出入度为这个程序采用栈来找出入度为0 0的点，栈里的顶点，都是入度为的点，栈里的顶点，都是入度为0 0的点。的点。算法实现：33我们结合下图详细讲解：我们结合下图详细讲解：ABCD开始时，只有A入度为0，A入栈。栈：ABCD栈顶元素A出栈并输出A，A的后继B、C入度减1，相当于删除A的所有关联边栈：空拓扑序列：A我们结合下图详细讲解：ABCD开始时，只有A入度为0，A入栈34BCDB、C的入度都变成0，依次将B、C入栈。栈：BC（入栈顺序不唯一）拓扑序列：ABD栈顶元素C出栈并输出C，C的后继D入度减1栈：B拓扑序列：ACBCDB、C的入度都变成0，依次将B、C入栈。栈：BC（入栈35D栈顶元素B出栈并输出B，B的后继D入度再减1。这时D入度为0，入栈。栈：D拓扑序列：ACBD栈顶元素D出栈并输出D。栈空，结束栈：空拓扑序列：ACBD（不唯一）简单简单&高效高效&实用的算法。上述实现方法复杂度实用的算法。上述实现方法复杂度O(V+E)O(V+E)。D栈顶元素B出栈并输出B，B的后继D入度再减1。这时D入度为36【例【例3 3】、家谱树】、家谱树【问题描述】【问题描述】有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。给出每个人的孩子的信息。输出一个序列，使得每个人的后辈都比那个人后列出。输出一个序列，使得每个人的后辈都比那个人后列出。【输入格式】【输入格式】第第1 1行一个整数行一个整数N N（1=N=1001=N=100），表示家族的人数。），表示家族的人数。接下来接下来N N行，第行，第I I行描述第行描述第I I个人的儿子。个人的儿子。每行最后是每行最后是0 0表示描述完毕。表示描述完毕。【输出格式】【输出格式】输出一个序列，使得每个人的后辈都比那个人后列出。输出一个序列，使得每个人的后辈都比那个人后列出。如果有多解输出任意一解。如果有多解输出任意一解。【输入样例】【输入样例】5 5 0 0 4 5 1 0 4 5 1 0 1 0 1 0 5 3 0 5 3 0 3 0 3 0【输出样例】【输出样例】2 4 5 3 12 4 5 3 1最小生成树和拓扑排序课件37【参考程序】【参考程序】#include#include#include#includeusing namespace std;using namespace std;int a101101int a101101,c101c101,r101,ans101,r101,ans101;int i,j,tot,temp,num,n,m;int i,j,tot,temp,num,n,m;int main()int main()cin n;cin n;for(i=1;i=n;i+)for(i=1;i j;cin j;if(j!=0)if(j!=0)ci+;/ci ci+;/ci用来存点用来存点i i的出度的出度 aici=j;aici=j;rj+;/ai,-1 rj+;/ai,-1用来存点用来存点i i的入度。的入度。while(j!=0);while(j!=0);【参考程序】38for(i=1;i=n;i+)for(i=1;i=n;i+)if(ri=0)if(ri=0)ans+tot=i;ans+tot=i;/把图中所有入度为把图中所有入度为0 0的点入栈，栈用一维数组的点入栈，栈用一维数组ansans表表示示 do do temp=anstot;temp=anstot;cout temp ;cout temp ;tot-;num+;tot-;num+;/栈顶元素出栈并输出栈顶元素出栈并输出 for(i=1;i=ctemp;i+)for(i=1;i=ctemp;i+)ratempi-;ratempi-;if(ratempi=0)/if(ratempi=0)/如果入度减如果入度减1 1后变成后变成0 0，则将这个后继点入栈，则将这个后继点入栈 ans+tot=atempi;ans+tot=atempi;while(num!=n);while(num!=n);/如果输出的点的数目如果输出的点的数目numnum等于等于n n，说明算法结束，说明算法结束 return 0;return 0;for(i=1;i=n;i+)39【例例4 4】奖金奖金【问题描述问题描述】由于无敌的凡凡在由于无敌的凡凡在20052005年世界英俊帅气男总决选中胜出，年世界英俊帅气男总决选中胜出，Yali CompanyYali Company总经理总经理Mr.ZMr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是来计算他们得到奖金的多少。于是Mr.ZMr.Z下令召开下令召开m m方会谈。每位参加会谈的代表提出方会谈。每位参加会谈的代表提出了自己的意见：了自己的意见：“我认为员工我认为员工a a的奖金应该比的奖金应该比b b高！高！”Mr.ZMr.Z决定要找出一种奖金方案，决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100100元。元。【输入格式输入格式】第一行两个整数第一行两个整数n,mn,m，表示员工总数和代表数；以下，表示员工总数和代表数；以下m m行，每行行，每行2 2个整数个整数a,ba,b，表，表示某个代表认为第示某个代表认为第a a号员工奖金应该比第号员工奖金应该比第b b号员工高。号员工高。【输出格式输出格式】若无法找到合理方案，则输出若无法找到合理方案，则输出“Poor Xed”Poor Xed”；否则输出一个数表示最少总奖金。；否则输出一个数表示最少总奖金。【输入样例输入样例】2 12 11 21 2【输出样例输出样例】201201最小生成树和拓扑排序课件40【数据规模】【数据规模】8080的数据满足的数据满足n=1000n=1000，m=2000m=2000；100100的数据满足的数据满足n=10000n=10000，m=20000m=20000。【算法分析】【算法分析】首先构图，若存在条件首先构图，若存在条件“a a的钱比的钱比b b多多”则从则从b b引一条有向指向引一条有向指向a a；然后拓扑排序，；然后拓扑排序，若无法完成排序则表示问题无解（存在圈）；若可以得到完整的拓扑序列，则按序若无法完成排序则表示问题无解（存在圈）；若可以得到完整的拓扑序列，则按序列顺序进行递推：列顺序进行递推：设设fifi表示第表示第i i个人能拿的最少奖金数；个人能拿的最少奖金数；首先所有首先所有fi=100fi=100（题目中给定的最小值）；（题目中给定的最小值）；然后按照拓扑顺序考察每个点然后按照拓扑顺序考察每个点i i，若存在有向边，若存在有向边(j,i)(j,i)，则表示，则表示fifi必须比必须比fjfj大，因此我们令大，因此我们令fi=Max fi,fj+1 fi=Max fi,fj+1 即可；即可；递推完成之后所有递推完成之后所有fifi的值也就确定了，而答案就等于的值也就确定了，而答案就等于f1+fnf1+fn。最小生成树和拓扑排序课件41【参考程序】【参考程序】#include#includeusing namespace std;using namespace std;int a10001301=0,into10001,ans10001,m,n,money;int a10001301=0,into10001,ans10001,m,n,money;void init()void init()/读入数据，并构建图，统计入度读入数据，并构建图，统计入度 int i,x,y;int i,x,y;cinnm;cinnm;for(i=1;i=m;i+)for(i=1;ixy;cinxy;ay0+;ay0+;/记录由记录由y y引出边的数目引出边的数目 ayay0=x;/ayay0=x;/记录由记录由ay0ay0引出边的顶点引出边的顶点 intox+;/intox+;/统计入度统计入度 bool topsort()/bool topsort()/拓扑排序拓扑排序 int t,tot,k,i,j;int t,tot,k,i,j;tot=0;k=0;tot=0;k=0;while(totn)/tot while(totn)/tot顶点个数顶点个数 t=0;t=0;/用来判断有无环用来判断有无环 for(i=1;i=n;i+)for(i=1;i=n;i+)if(intoi=0)if(intoi=0)【参考程序】42 tot+;t+;money+=100;tot+;t+;money+=100;anst=i;anst=i;intoi=0 xfffffff;intoi=0 xfffffff;if(t=0)return false;/if(t=0)return false;/存在环存在环 money+=k*t;k+;money+=k*t;k+;for(i=1;i=t;i+)/for(i=1;i=t;i+)/去掉相连的边去掉相连的边 for(j=1;j=aansi0;j+)intoaansij-;for(j=1;j=aansi0;j+)intoaansij-;return true;return true;int main()int main()init();money=0;init();money=0;if(topsort()coutmoneyendl;if(topsort()coutmoneyendl;else coutPoor Xedendl;else coutPoor Xedendl;return 0;return 0;43上机练习4 4、烦人的幻灯片、烦人的幻灯片 【问题描述问题描述】李教授将于今天下午作一次非常重要的演讲。不信的事他不是一个非常爱整洁李教授将于今天下午作一次非常重要的演讲。不信的事他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用演讲一共要用n n n n张幻灯片张幻灯片（n=26n=26n=26n=26），这，这n n n n张幻灯片按照演讲要使用的顺序已经用数字张幻灯片按照演讲要使用的顺序已经用数字1n1n1n1n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。灯片。现在我们用大写字母现在我们用大写字母A,B,CA,B,CA,B,CA,B,C再次把幻灯片依次编号。你的任务是编写一个程再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。现的。【输入格式输入格式】文件的第一行只有一个整数文件的第一行只有一个整数n n n n，表示有，表示有n n张幻灯片，接下来的张幻灯片，接下来的n n n n行每行包括行每行包括4 4 4 4个整个整数数xmin,xmax,ymin,ymaxxmin,xmax,ymin,ymaxxmin,xmax,ymin,ymaxxmin,xmax,ymin,ymax（整数之间用空格分开）为幻灯片的坐标，这（整数之间用空格分开）为幻灯片的坐标，这n n n n张幻灯片按张幻灯片按其在文件中出现的顺序从前到后依次编号为其在文件中出现的顺序从前到后依次编号为A,B,CA,B,CA,B,CA,B,C，再接下来的，再接下来的n n行依次为行依次为n n n n个个数字编号的坐标数字编号的坐标x,yx,yx,yx,y，显然在幻灯片之外是不会有数字的。，显然在幻灯片之外是不会有数字的。【输出格式输出格式】若是对应可以实现，输出文件应该包括若是对应可以实现，输出文件应该包括n n行，每一行为一个字母和一个数字，行，每一行为一个字母和一个数字，中间以一个空格隔开，并且每行以字母的升序排列，注意输出的字母要大写并且定中间以一个空格隔开，并且每行以字母的升序排列，注意输出的字母要大写并且定格；反之，若是对应无法实现，在文件的第一行顶格输出格；反之，若是对应无法实现，在文件的第一行顶格输出NoneNoneNoneNone即可。首行末无多余即可。首行末无多余的空格。的空格。上机练习4、烦人的幻灯片 44上机练习【输入输出样例输入输出样例】slides.inslides.inslides.outslides.out4 46 22 10 206 22 10 204 18 6 164 18 6 168 20 2 188 20 2 1810 24 4 810 24 4 89 159 1519 1719 1711 711 721 1121 11A 4A 4B 1B 1C 2C 2D 3D 3上机练习slides.inslides.out4A 4455 5、病毒、病毒【问题描述】【问题描述】有一天，小有一天，小y y突然发现自己的计算机感染了一种病毒！还好，小突然发现自己的计算机感染了一种病毒！还好，小y y发现这种病毒发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。和删除字母。现在怎么恢复原来的文档呢！小现在怎么恢复原来的文档呢！小y y很聪明，他在其他没有感染病毒的机器上，生很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。序性，找到病毒替换字母的规律，再用来恢复其它文档。现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。【输入格式】【输入格式】virus.invirus.in第一行为整数第一行为整数K K（5000050000），表示字典中的单词个数。），表示字典中的单词个数。以下以下K K行，是被病毒感染了的字典，每行一个单词。行，是被病毒感染了的字典，每行一个单词。最后一行是需要你恢复的一串字母。最后一行是需要你恢复的一串字母。所有字母均为小写。所有字母均为小写。【输出格式】【输出格式】virus.outvirus.out输出仅一行，为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典输出仅一行，为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况，这时请输出一个是错的情况，这时请输出一个0 0。最小生成树和拓扑排序课件46【输入样例】【输入样例】6 6cebdbaccebdbaccaccacecdecddcadcaabaababacbaccedabcedab【输出样例】【输出样例】abcdeabcde【输入样例】47