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

题目

求最大匹配

分析

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

代码

#include 
#include 
#include 
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;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！