二分图匹配实例代码及整理
1、匈牙利算法
HDU 1150
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<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int m,n,k;
int vis[105];
int mpt[105][105];
int use[105];
int hungary( int x)
{
for ( int i=1;i<m;i++)
{
if (vis[i]==0&&mpt[x][i]==1)
{
vis[i]=1;
if (use[i]==-1||hungary(use[i]))
{
use[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
while ( scanf ( "%d" ,&n)!=EOF,n)
{
scanf ( "%d%d" ,&m,&k);
int a,b,c;
memset (mpt,0, sizeof (mpt));
for ( int i=1;i<=k;i++)
{
scanf ( "%d%d%d" ,&c,&a,&b);
mpt[a][b]=1;
}
int ans=0;
memset (use,-1, sizeof (use));
for ( int i=1;i<n;i++)
{
if (hungary(i))
{
ans++;
}
memset (vis,0, sizeof (vis));
}
printf ( "%d\n" ,ans);
}
return 0;
}
|
2、KM算法
HDU 2255
看了很多资料都还不是很懂、、先贴别人的模板
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
#define N 310
int map[N][N];
bool visitx[N], visity[N];
int lx[N], ly[N];
int match[N];
int n;
bool Hungary( int u) //匈牙利算法
{
visitx[u] = true ;
for ( int i = 0; i < n; ++i)
{
if (!visity[i] && lx[u] + ly[i] == map[u][i])
{
visity[i] = true ;
if (match[i] == -1 || Hungary(match[i]))
{
match[i] = u;
return true ;
}
}
}
return false ;
}
void KM_perfect_match()
{
int temp;
memset (lx, 0, sizeof (lx)); //初始化顶标
memset (ly, 0, sizeof (ly)); //ly[i]为0
for ( int i = 0; i < n; ++i) //lx[i]为权值最大的边
for ( int j = 0; j < n; ++j)
lx[i] = max(lx[i], map[i][j]);
for ( int i = 0; i < n; ++i) //对n个点匹配
{
while (1)
{
memset (visitx, false , sizeof (visitx));
memset (visity, false , sizeof (visity));
if (Hungary(i)) //匹配成功
break ;
else //匹配失败,找最小值
{
temp = INT_MAX;
for ( int j = 0; j < n; ++j) //x在交错树中
if (visitx[j])
for ( int k = 0; k < n; ++k) //y在交错树外
if (!visity[k] && temp > lx[j] + ly[k] - map[j][k])
temp = lx[j] + ly[k] - map[j][k];
for ( int j = 0; j < n; ++j) //更新顶标
{
if (visitx[j])
lx[j] -= temp;
if (visity[j])
ly[j] += temp;
}
}
}
}
}
int main()
{
int ans;
while ( scanf ( "%d" , &n) != EOF)
{
ans = 0;
memset (match, -1, sizeof (match));
for ( int i = 0; i < n; ++i)
for ( int j = 0; j < n; ++j)
scanf ( "%d" , &map[i][j]);
KM_perfect_match();
for ( int i = 0; i < n; ++i) //权值相加
ans += map[match[i]][i];
printf ( "%d\n" , ans);
}
return 0;
}
|
3、多重匹配
HDU 3605 Escape
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
int num[15];
int mpt[100005][15];
int vis[15];
int use[15];
int dp[15][100005];
int hungary( int x)
{
for ( int i=1;i<=m;i++)
{
if (vis[i]==0&&mpt[x][i]==1)
{
vis[i]=1;
if (use[i]<num[i]) //满足条件
{
dp[i][use[i]++]=x;
return 1;
}
//不满足则寻找增广路
for ( int j=0;j<use[i];j++) //看能否回溯一个出去
{
if (hungary(dp[i][j]))
{
dp[i][j]=x;
return 1;
}
}
}
}
return 0;
}
int main()
{
while ( scanf ( "%d%d" ,&n,&m)!=EOF)
{
for ( int i=1;i<=n;i++)
{
for ( int j=1;j<=m;j++)
{
scanf ( "%d" ,&mpt[i][j]);
}
}
for ( int i=1;i<=m;i++)
scanf ( "%d" ,&num[i]);
int ans=0;
memset (use,0, sizeof (use));
for ( int i=1;i<=n;i++)
{
memset (vis,0, sizeof (vis));
if (!hungary(i))
{
ans=1;
break ;
}
}
if (ans==0)
{
printf ( "YES\n" );
}
else printf ( "NO\n" );
}
return 0;
}
|
以上就是二分图匹配的实现代码,如有疑问请留言,或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
原文链接:http://blog.csdn.net/a1dark/article/details/24251353