二分图匹配

匈牙利算法
腾，有机会上，没机会创造机会也要上；

hduoj2063

经典，求最大匹配；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int girls[505];//存放男孩的匹配女孩
bool flag[505];//存放标记
bool relation[505][505];//存放关系
int k,m,n;

//第x个女孩找匹配对象
bool f(int x)
{
    for(int j=1;j<=n;j++){
        if(relation[x][j]&&!flag[j]){
            flag[j]=1;
            if(girls[j]==0||f(girls[j])){
                girls[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    while(scanf("%d",&k)!=EOF&&k!=0)
    {
        scanf("%d%d",&m,&n);
        int x,y;
        memset(relation,0,sizeof(relation));
        memset(girls,0,sizeof(girls));
        for(int i=0;i<k;i++){
            cin>>x>>y;
            relation[x][y]=1;
        }
        int sum=0;
        for(int i=0;i<m;i++){
            memset(flag,0,sizeof(flag));
            if(f(i+1))sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

hduoj1068

求没有关系的最大子集：总数-最大匹配数/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int maze[1010][1010];
bool vis[1010];
int flag[1010];
int num;

bool f(int x)
{
    for(int j=0;j<num;j++){
        if(maze[x][j]==1&&!vis[j]){
            vis[j]=1;
            if(flag[j]==-1||f(flag[j])){
                flag[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    while(scanf("%d",&num)!=EOF){
        memset(maze,0,sizeof(maze));
        int a,b;
        for(int i=0;i<num;i++){
            scanf("%d: (%d)",&a,&b);
            int tmp=0;
            for(int j=0;j<b;j++){
                scanf("%d",&tmp);//使用cin超时
                maze[i][tmp]=1;
            }
        }
        int sum=0;
        memset(flag,-1,sizeof(flag));
        //第i个学生的是否可配对
        for(int i=0;i<num;i++){
            memset(vis,0,sizeof(vis));
            if(f(i))sum++;
        }
        //学生总数-最大匹配数/2
        cout<<num-sum/2<<endl;
    }
    return 0;
}