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

本文主要是介绍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;
} 

这篇关于SSL 1335 最佳派对#匈牙利算法#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---