# HDU_2255 二分图最佳完美匹配 KM匈牙利算法

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
using namespace std;
int w[N][N],n,lx[N],ly[N],lefts[N];
bool S[N],T[N];
bool dfs(int u)
{
S[u]=1;
for (int v=1;v<=n;v++)
if (lx[u]+ly[v]==w[u][v] && !T[v]){
T[v]=true;
if (!lefts[v] || dfs(lefts[v])){
lefts[v]=u;
return true;
}
}
return false;
}
void update()
{
int a=1<<30;
for (int i=1;i<=n;i++) if (S[i])
for (int j=1;j<=n;j++) if (!T[j]){
a=min(a,lx[i]+ly[j]-w[i][j]);
}
for (int i=1;i<=n;i++){
if (S[i]) lx[i]-=a;
if (T[i]) ly[i]+=a;
}
}
void KM()
{
int i,j;
for (i=1;i<=n;i++){
lefts[i]=lx[i]=ly[i]=0;
for (j=1;j<=n;j++){
lx[i]=max(lx[i],w[i][j]);
}
}
for (i=1;i<=n;i++){
for (;;){
memset(S,0,sizeof S);
memset(T,0,sizeof T);
if (dfs(i)) break;
else update();
}
}
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) scanf("%d",&w[i][j]);
memset(lefts,-1,sizeof lefts);
KM();
int ans=0;
for (int i=1;i<=n;i++){
ans+=lx[i];
ans+=ly[i];
}
printf("%d\n",ans);
}
return 0;
}```

HDU_2255 二分图最佳完美匹配 KM匈牙利算法,布布扣,bubuko.com

## HDU 1150：Machine Schedule（二分匹配，匈牙利算法）

Machine Schedule Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5371    Accepted Submission(s): 2658 Problem Description As we all know, machine scheduling is a very classical problem in compu

## POJ 3014：Asteroids（二分匹配，匈牙利算法）

Asteroids Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 14399   Accepted: 7836 Description Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K as