唔真是个可爱的算法啊
因为太可爱不知道怎么讲好了 (啊喂
所以先看看二分图的定义吧
对于一个图 G=(V,E), 若能将其点集分为两个互不相交的两个子集 X,Y, 使得 X∩Y=?, 且对于 G 的边集 V, 若其所有边的顶点全部一侧属于 X, 一侧属于 Y, 则称图 G 为一个二分图.
长这个样子
然后
如何求最大匹配有个算法叫做
匈牙利算法
(哇听起来就好有异地风情 [滚开啊
具体怎么求呢
让我们形象的比喻一下
先看一哈题
对这个例子就是
找对象!(大概就是相亲吧 www
就是男方, 女方
有几对有好感的
然后找对象, 凑越多越好
就以这个图为例吧
算法的思路就是
A 先找 a
B 也找 a, 但是 a 已经被 A 占了
B 可以去找 b
C 找 c
D 找 b
b 被 B 占了, B 把 b 让给 D
B 抢走 A 的 a
E 找 d
(总的来说 A 好惨
emmmm 就是这样一种协商 [完全不公平
看看代码吧
- #include<cstdio>
- #include<cstring>
- using namespace std;
- #define maxn 1010
- int n,m,e;
- int www[maxn][maxn];
- int flag[maxn],follow[maxn];
- int qwq(int x) {
- for(int i = 1; i <= m; i++)
- if(www[x][i] && !flag[i]) {// 如果有心仪的并且心仪的还单身
- flag[i] = 1;// 占了
- if(qwq(follow[i]) || !follow[i]) {//follow 记录与他匹配的
- follow[i] = x;
- return 1;
- }
- }
- return 0;
- }
- int main() {
- scanf("%d%d%d",&n,&m,&e);
- for(int i = 1; i <= e; i++) {
- int u,v;
- scanf("%d%d",&u,&v);
- if(u> n || v> m)
- continue;
- www[u][v] = 1;
- }
- int ans = 0;
- for(int i = 1; i <= n; i++) {
- memset(flag,0,sizeof(flag));// 每次清零, 用来记录每次的匹配中某点是否被匹配
- if(qwq(i))
- ans++;
- }
- printf("%d",ans);
- return 0;
- }
- emmmm
突然发现被我讲的一点没有意思
[趴
来源: http://www.bubuko.com/infodetail-2930460.html