图论杂算法

图论杂算法•强连通分量和双连通分量•最大团•稳定婚配问题有向图强连通分量•问题引入•Hdu1827SummerHoliday•题意：听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？[有向图强连通分量]在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。[Tarjan算法]•Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出Low(u)=Min{DFN(u),Low(v),(u,v)为树枝边，u为v的父节点DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)}当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量！！可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。tarjan(u){DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值Stack.push(u)//将节点u压入栈中foreach(u,v)inE//枚举每一条边if(visnotvisted)//如果节点v未被访问过tarjan(v)//继续向下找Low[u]=min(Low[u],Low[v])elseif(vinS)//如果节点v还在栈内Low[u]=min(Low[u],DFN[v])if(DFN[u]==Low[u])//如果节点u是强连通分量的根repeatv=S.pop//将v退栈，为该强连通分量中一个顶点printvuntil(u==v)}伪代码：双连通分量如果一个无向连通图的点连通度大于1，则称该图是点双连通的，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点，又叫关节点。如果一个无向连通图的边连通度大于1，则称该图是边双连通的，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥，又叫关节边。如何求割点和桥？？？一个顶点u是割点，当且仅当满足(1)或(2)(1)u为树根，且u有多于一个子树。(2)u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)=Low(v)。[求割点与桥]一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)Low(v)。[求双连通分支]下面要分开讨论点双连通分支与边双连通分支的求法。•对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFN(u)=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。最大团问题•问题描述给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。•这是一个很典型的NP问题•一般搜索：•设其包含顶点0,1,2,3,4,5·····n-1。从0开始搜索，依次搜索所有与其相邻的点······典型的指数时间搜索缺陷：每一次都是从头开始！换一种方法：搜索+dp•它不是采用我们惯用的从0节点开始搜索的方法，而是反了过来，从n-1开始走，当然，走的时候还是只向前走（5开始，就只搜6,7······n-1）这样做有什么好处呢？设dp[i]表示从第i个点到n-1个点组成的点集的最大团数那么dp[i-1]=dp[i]||dp[i]+1提供了强有力的剪枝条件#includeiostream#includealgorithmusingnamespacestd;constintN=55;intdp[N];boolinset[N],g[N][N];intn,best;boolfound;voidMemcpy(bool*d,bool*s){for(inti=0;in;i++)d[i]=s[i];}intfind(intstart,bool*s){for(inti=start+1;in;i++)if(s[i])returni;return-1;}voidclique(bool*s,intstart,intlen){intfirst=find(start,s),i;if(first==-1){if(lenbest){best=len;found=true;}return;}booltmp[N];while(first!=-1){if(len+n-start=best||len+dp[first]=best)//已选择的点的个数+剩余点的个数=最大可能值//已选择的点的个数+后面的最大团数=最大可能值return;tmp[first]=false;for(i=first+1;in;i++)//i之后与当前集合重叠的点，只有重叠的点才有可能与已选择的点关联tmp[i]=s[i]&g[first][i];clique(tmp,first,len+1);if(found)return;first=find(first,s);}}intmain(){while(scanf(%d,&n)==1&&n){for(inti=0;in;i++)for(intj=0;jn;j++)scanf(%d,&g[i][j]);best=0;dp[n-1]=1;for(inti=n-2;i=0;i--){Memcpy(inset,g[i]);found=false;clique(inset,i,1);dp[i]=best;}printf(%d\n,dp[0]);}return0;}hdu1530MaximumClique•模板题•。。。。。。Hdu1045FireNet•题意：给定一个n*n的矩阵，‘.’表示空白区，‘X’表示墙壁，求在该矩阵的空白区上放置碉堡的数量的最大值，使得所有碉堡不能相互攻击（墙壁可以挡住攻击）面对这种题，我们通常想到的是用二分匹配，建图，求最大匹配数图G的最大独立集=G的补图（G'）的最大团值分析：将矩阵上的所有点重新标号，0~n*n-1,同时，将所有可以直接攻击到的点连接起来，这样，题目就转变成了求一个图的最大独立集。最大独立数=补图的最大团数Hdu3585maximumshortestdistance•题意：给定坐标内的n个点，从中选k个点，使得这k个点中的最小距离值最大“求最小的最大值，一般可用二分来找，再用某种方法判其是否可行”二分+最大团稳定婚配问题•问题来自于一场“3分钟相亲”活动，参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流，并为她们打分，然后按照喜欢程度，对每一位女士进行排序；同样的，每位女士也要对所有男士进行打分和排序。•作为活动的组织者，当你拿到这些数据后，该如何为男，女士们配对，才能使大家皆大欢喜，组成稳定的婚姻呢？所谓稳定的婚姻，就是指男女结婚后，双方都不会发生出轨行为。那怎样才能做到双方都不出轨呢？如果双方都是对方的最爱，自然不会出轨；如果有一方或双方都不是对方的最爱，则必须保证想出轨的人找不到出轨的对象简言之，只要满足“除妻子（丈夫）外，我爱的人不爱我，爱我的人我不爱”条件，就可形成稳定的婚姻。•延迟认可算法（Gale-Shapley算法）是解决稳定婚姻问题的经典算法男士主动出击先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：①每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；②每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。③若某男士被其女友抛弃，重新变成自由男。在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。hdu1914TheStableMarriageProblemhdu1435StableMatch都是赤裸裸的模板题题目列表：强连通分量：hdu3639Hawk-and-Chicken（强连通+反图+缩点）hdu1827SummerHolidayhdu1269迷宫城堡hdu3072IntelligenceSystem双连通分量：hdu2242考研路茫茫——空调教室Tarjan算法应用：hdu3594Cactus最大团hdu1530MaximumCliquepku1419GraphColoringpku1129ChannelAllocationhdu1045FireNet稳定婚配问题hdu1914TheStableMarriageProblemhdu1435StableMatch