做海报图片的网站,网页设计规范怎么写,网站建设与管理培训总结,天堂 在线最新版天堂中文匈牙利算法#xff0c;他可以在比较快的时间复杂度之内告诉我们左边和右边成功匹配的最大数是多少
匹配指的是边的数量#xff0c;成功的匹配指的是两个未被使用的点之间存在一条边(就不存在两条边共用了一个点的)。
匈牙利算法可以返回成功匹配的最大匹配数是多少。 #incl…匈牙利算法他可以在比较快的时间复杂度之内告诉我们左边和右边成功匹配的最大数是多少
匹配指的是边的数量成功的匹配指的是两个未被使用的点之间存在一条边(就不存在两条边共用了一个点的)。
匈牙利算法可以返回成功匹配的最大匹配数是多少。 #includeiostream
#includealgorithm
#includecstring
using namespace std;const int N510,M1e510;
int h[N],e[M],ne[M],idx;
int match[N];//match表示的是这个妹子匹配的男生是谁0代表没有匹配。
bool st[N];//表示这个女生是否考虑过
int n1,n2,m;void add(int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;
}bool find(int x){for(int ih[x];i!-1;ine[i]){//枚举看上妹子的集合int je[i];if(!st[j]){//如果这个妹子没有考虑过st[j]true;//表示这个妹子已经被考虑了if(match[j] 0 || find(match[j])){//妹子没有匹配的男生 或 这个男生可以找到其他的妹子代替//如果这个被替换妹子的男生的其他相连的女生被匹配了的话会让匹配的那个男生再去找其他妹子就是套娃牵一发动所有有关系的人。每个男生进入find都会对已经被考虑的妹子变为true不会造成重复考虑。match[j]x;return true; }}}return false;
}int main(){cinn1n2m;memset(h,-1,sizeof h);while(m--){int a,b;cinab;add(a,b);//虽然是无向边但只会找一下左边点的所有出边只需要存左边指向右边就可以了。}int res0;//匹配数量//就依次来分析一下每个男生该找哪个妹子。for(int i1;in1;i){memset(st,false,sizeof st);//每一次分析之前清空所有妹子表示这些妹子都还没考虑过保证每个妹子我只考虑一遍。if(find(i)) res;//判断是否能找到妹子}coutresendl;return 0;
}
