自己做网站排名,产品经理网站开发需求,《新闻联播》 今天,网络营销方式优缺点将所有点分成两个集合#xff0c;使得所有边只出现在集合之间#xff0c;就是二分图
二分图#xff1a;一定不含有奇数个点数的环#xff1b;可能包含长度为偶数的环#xff0c; 不一定是连通图
二分图的最大匹配#xff1a;
#includeiostream
#includecs…将所有点分成两个集合使得所有边只出现在集合之间就是二分图
二分图一定不含有奇数个点数的环可能包含长度为偶数的环 不一定是连通图
二分图的最大匹配
#includeiostream
#includecstring
using namespace std;
const int N 510 , M 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;//邻接表
bool st[N];
int match[N];void add(int a , int b)
{//头插法//如图 如1与2之间要有一条线让2的ne为1再让h[1]为2的索引。//这样h[1]就是1节点存的最后一个相连的点如图就是7节点。//而在索引表内部通过头插法的方式(即每次ne指向上一个点(h存的就是上一个点))索引表为7-4-2e[idx] b, ne[idx] h[a], h[a] idx;
}int find(int x)
{//遍历自己喜欢的女孩for(int i h[x] ; i ! -1 ;i ne[i]){int j e[i];if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定{st[j] true;//那x就预定这个女孩了这里预定是防止她男朋友找其他喜欢的女孩时不重复找这个//如果女孩j没有男朋友或者她原来的男朋友能够预定其它喜欢的女孩。配对成功if(!match[j]||find(match[j])){match[j] x;return true;}}}//自己中意的全部都被预定了。配对失败。return false;
}int main()
{memset(h,-1,sizeof h);scanf(%d%d%d,n1,n2,m);while(m--){int a,b;scanf(%d%d,a,b);add(a,b);}int res 0;for(int i 1; i n1 ;i ){ //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化memset(st,false,sizeof st);if(find(i)) res;//找到一条边则res} printf(%d\n,res);
}
