SSL 1335 最佳派对#匈牙利算法#

题目

求最大匹配

---

分析

用匈牙利算法
(1)置M为空
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径为止

---

代码

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
struct node{int x,y,next;}e[10001];
int ls[101],cover[101],link[101],ans,n,m;
int in(){
    int ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
void rn(int &a,int &b){a=in(); b=in();}
int find(int x){
    int t=ls[x];
    while (t){
        if (!cover[e[t].y]){
            cover[e[t].y]=1;
            int q=link[e[t].y];//记录指针
            link[e[t].y]=x;//指向这个点
            if (!q||find(q)) return 1;//继续找的到或找不到
            link[e[t].y]=q;
        }
        t=e[t].next;
    }
    return 0;//直接找不到
}
int main(){
    rn(n,m);
    for (int i=1;i<=m;i++){
        rn(e[i].x,e[i].y);
        e[i].next=ls[e[i].x];
        ls[e[i].x]=i;
    }
    for (int i=1;i<=n;i++){
        memset(cover,0,sizeof(cover));//清0，每次重新找（指针不变）
        if (find(i)) ans++;//能找到
    }
    if (!ans) puts("NO SOLUTION");
    else printf("%d",ans);
    return 0;
}