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!