二分图匹配,头痛难题
如题, 如果 有左半图和右半图, 可以理解为 左边图是用户 右半图是会议
只有一个用户申请了这个会议才能够匹配,如果没申请则不能匹配, 请问这样带匹配条件的图怎么样才能找到最大匹配数量?
如果同时左边的用户还带有优先级,优先级高的优先获得匹配又该怎么匹配呢?
[解决办法]
发生冲突时,优先级高的人优先获得匹配
如果是这样的话，直接用贪心就可以了，先找最高优先级的用户，对应的教室，再找其次的，以此类推。
但这样排出来的结果，恐怕会造成很多资源的浪费，更好的方法就是转化为二分图，
并且应该正好可以用最大流来做，求二分图的最大匹配。
假设有一个公共的源S，连接到所有用户，而用户到教室的权值不同，而所有的教室都通向一个共同的汇T。
求S到T的最大流，应该就差不多，这样的话求出的解，要比完全依照用户优先级得出的结果更有效。
#include <iostream>#define N 6#define L 3#define R 3using namespace std;bool RToL(int);int map[N][N] = {{0,0,0,1,1,1}, {0,0,0,0,0,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0}, {0,0,0,0,0,0}, {0,0,0,0,0,0}};int lien[N] = {-1};int matched[N] = {0};bool LToR(int curPoint)//左边的点找右边可以连接的点{ for(int i=L; i<N; i++)//对每个右边的点 { if(map[curPoint][i] && lien[i] == -1)//如果未进入链里 { lien[curPoint] = i;//这个点连接到右边的点i号 if(RToL(i))//如果找到了增广链 return true; else//如果没找到，那就试下下个链路 { lien[curPoint] = -1; continue; } } } return false;}bool RToL(int curPoint){ for(int i=0; i<L; i++)//对每个左边的点 { if(map[i][curPoint] && lien[i] == -1) { lien[curPoint] = i; if(LToR(i)) return true; else { lien[curPoint] = -1; continue; } } } //右边寻找的话是有特殊情况的，那就是如果没找到接下去的点的 //而右边的点本身没匹配过那么就说明这条增广链到次为止 for(int i=0; i<L; i++) if(matched[i] == curPoint+1) return false; return true;}//唉，其实二分图最大匹配很简单，网络上好多都搞的很麻烦，结果我也迷糊了一镇，//说什么要有奇数条边，而且选好后要对边进行"异或"操作把新链里的奇数边加进去偶数边拿出来阿啥啥的//搞得人比较混乱，让人把注意力放到边上面。。。实际上根本不需要注意什么边，只需注意顶点就可以了//首先从左边的未配对的顶点开始，一个个试过来，如果找到一条链，那根本不用管找到的链是奇数还是偶数，//只需注意找到的增广链的头和尾都必须是未配对的就够了，然后对这条增广链里所有左边的顶点进行刷新，//就是在这条增广链里不管左边的顶点是否配对过，都把它们的配对改成这条增广链里找到的相对应的右边的点//然后继续找下条增广链直到试过所有左边的点就可以了，右边的点只在找增广链的时候有用，其他时候不用管//---------------------------------//解释：不过为什么这样就可以了呢？ 其实就是把网络上的方法简化了，本来所谓的找到奇数边然后偶数边去掉奇数边加进去//的意思就是只对左边的顶点进行更新，把左边的顶点可能已经配对过的点交换下它们的配对而已，比如有左3右3个图：//本来有1配5,2配6.这时候点3和点4未配对，然后如果点3经过3-6-2-5-1-4，//然后如果对所有左边的点更新，根据路径将变成：3配6，2配5，1配4。。。。。//仔细看看，不就是把左边点1和点2原本的配对"往上抬"了下么。然后原本和点2配对的点6会空出来。正好留给点3//而且只要起点和终点都是为配对的点就可以保证不会出现重复配对的情况//就像是原本有几个人做板凳上，然后突然来了个人，叫大家让出个位置，把某人原本做的地方让给刚来的人.void match(){ for(int i=0; i<L; i++) { memset(lien, -1, sizeof(lien)); if(matched[i]==0)//左边的开始节点必须为未配对的 if(LToR(i))//寻找 { for(int g=0; g<L; g++)//只对每个左边的点查看 { if(lien[g]!=-1 && matched[lien[g]] == 0)//如果左边的点有连接 { matched[matched[g]-1] = 0;//把原本右边可能已经配对的去掉配对 matched[g] = lien[g]+1;//然后从新连接左边到右边 matched[lien[g]] = g+1;//然后把右边的连接到左边 } } } } for(int i=0; i<N; i++) cout<<"第"<<i+1<<"号顶点配:"<<matched[i]<<"号顶点 "<<endl;}int main(){ match(); return 0;}
[解决办法]