Bipartite graph matching example code and collation
- 2020-05-26 09:50:27
- OfStack
2. Sample code matching and sorting
1. Hungarian algorithm
HDU 1150
#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 algorithm
HDU 2255
Read a lot of materials are not very understand, the first post others' template
#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) // Hungarian algorithm
{
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)); // Initializes the header
memset(ly, 0, sizeof(ly)); //ly[i] for 0
for(int i = 0; i < n; ++i) //lx[i] Is the edge with the largest weight
for(int j = 0; j < n; ++j)
lx[i] = max(lx[i], map[i][j]);
for(int i = 0; i < n; ++i) // right n A point matching
{
while(1)
{
memset(visitx, false, sizeof(visitx));
memset(visity, false, sizeof(visity));
if(Hungary(i)) // The match is successful
break;
else // The match failed. Find the minimum
{
temp = INT_MAX;
for(int j = 0; j < n; ++j) //x In a staggered tree
if(visitx[j])
for(int k = 0; k < n; ++k) //y Outside the staggered tree
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) // Update the top mark
{
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) // A weight added
ans += map[match[i]][i];
printf("%d\n", ans);
}
return 0;
}
3. Multiple matching
HDU 3605 Escape
#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])// Meet the conditions
{
dp[i][use[i]++]=x;
return 1;
}
// If you're not satisfied, look for an augmented path
for(int j=0;j<use[i];j++)// See if you can go back 1 A go out
{
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;
}
The above is 2 sub map matching code, if you have questions please leave a message, or to the site community exchange discussion, thank you for reading, hope to help you, thank you for the support of the site!