匈牙利算法的样例程序
发布网友
发布时间：2023-09-11 08:49
共1个回答
热心网友
时间：2024-10-15 04:38
格式说明
输入格式：
第1行3个整数，V1,V2的节点数目n1,n2,G的边数m
第2-m+1行，每行两个整数t1,t2，代表V1中编号为t1的点和V2中编号为t2的点之间有边相连
输出格式：
1个整数ans，代表最大匹配数
邻接矩阵-C #include<stdio.h>#include<string.h>intn1, n2, m, ans;int result[101];//记录V2中的点匹配的点的编号bool state[101];//记录V2中的每个点是否被搜索过bool data[101][101];//邻接矩阵true代表有边相连void init(){ int t1, t2; memset(data, 0, sizeof(data)); memset(result, 0, sizeof(result)); ans = 0; scanf(%d%d%d, &n1, &n2, &m); for(int i = 1; i <= m; i++) { scanf(%d%d, &t1, &t2); data[t1][t2] = true; } return;}bool find(inta){ for(int i = 1; i <= n2; i++) { if(data[a][i] == 1 && !state[i]) //如果节点i与a相邻并且未被查找过 { state[i] = true; //标记i为已查找过 if(result[i] == 0 //如果i未在前一个匹配M中 || find(result[i])) //i在匹配M中，但是从与i相邻的节点出发可以有增广路 { result[i] = a; //记录查找成功记录 result[a] = i; returntrue;//返回查找成功 } } } return false;}int main(){ init(); for(int i = 1; i <= n1; i++) { memset(state, 0, sizeof(state)); //清空上次搜索时的标记 if(find(i)) { ans++; //从节点i尝试扩展 } } printf(%d\n, ans); return 0;}邻接矩阵-pascal Programhungary;Constmax=100;Vardata:array[1..max,1..max]ofboolean;{邻接矩阵}result:array[1..max]ofinteger;{记录当前连接方式}state:array[1..max]ofboolean;{记录是否遍历过，防止死循环}m,n1,n2,i,t1,t2,ans:integer;Functiondfs(p:integer):boolean;vari:integer;beginfori:=1ton2doifdata[p,i]andnot(state[i])then{有边存在且没有被搜索过}beginstate[i]:=true;if(result[i]=0)ordfs(result[i])then{没有被连过或寻找到增广路}beginresult[i]:=p;exit(true);end;end;exit(false);end;beginreadln(n1,n2,m);fillchar(data,sizeof(data),0);fori:=1tomdobeginreadln(t1,t2）；data[t1,t2]:=true;end;fillchar(result,sizeof(result),0);ans:=0;fori:=1ton1dobeginfillchar(state,sizeof(state),0);ifdfs(i)theninc(ans);end;writeln(ans);end.邻接表-C++ #include<iostream>#include<cstring>usingnamespacestd;//定义链表structlink{intdata;//存放数据link*next;//指向下一个节点link(int=0);};link::link(intn){data=n;next=NULL;}intn1,n2,m,ans=0;intresult[101];//记录n1中的点匹配的点的编号boolstate[101];//记录n1中的每个点是否被搜索过link*head[101];//记录n2中的点的邻接节点link*last[101];//邻接表的终止位置记录//判断能否找到从节点n开始的增广路boolfind(constintn){link*t=head[n];while(t!=NULL){//n仍有未查找的邻接节点时if(!(state[t->data])){//如果邻接点t->data未被查找过state[t->data]=true;//标记t->data为已经被找过if((result[t->data]==0)||//如果t->data不属于前一个匹配M(find(result[t->data]))){//如果t->data匹配到的节点可以寻找到增广路result[t->data]=n;//那么可以更新匹配M'，其中n1中的点t->data匹配nreturntrue;//返回匹配成功的标志}}t=t->next;//继续查找下一个n的邻接节点}returnfalse;}intmain(){intt1=0,t2=0;cin>>n1>>n2>>m;for(inti=0;i<m;i++){cin>>t1>>t2;if(last[t1]==NULL)last[t1]=head[t1]=newlink(t2);elselast[t1]=last[t1]->next=newlink(t2）；}for(inti=1;i<=n1;i++){memset(state,0,sizeof(state));if(find(i))ans++;}cout<<ans<<endl;return0;}邻接矩阵-C++ #include<iostream>#include<cstring>using namespace std;int map[105][105];int visit[105],flag[105];int n,m;bool dfs(int a){ for(int i=1; i<=n; i++) { if(map[a][i]&&!visit[i]) { visit[i]=1; if(flag[i]==0||dfs(flag[i])) { flag[i]=a; return true; } } } return false;}int main(){ while(cin>>n1 >>n2 >>m) { memset(map,0,sizeof(map)); for(int i=1; i<=m; i++) { int x,y; cin>>x>>y; map[x][y]=1; } memset(flag,0,sizeof(flag)); int result=0; for(int i=1; i<=n1; i++) { memset(visit,0,sizeof(visit)); if(dfs(i))result++; } cout<<result<<endl; } return 0;}邻接表-pascal（使用动态链表）
（方法基于之前的邻接矩阵-pascal） programhungarian_algorithm;//匈牙利算法typenode=^link;//链表定义link=recordg:longint;//指向节点next:node;end;varn1,n2,m,a,v1,v2,ans:longint;flag:array[1..1000000]ofboolean;//记录在main递归过程中是否已访问过，防止死循环nd:array[1..1000000]ofnode;//邻接表resultt:array[1..1000000]oflongint;//记录v2中节点的最终匹配于v1中的几号节点functionmain(wei:longint):boolean;varp:node;beginp:=nd[wei];whilep<>nildobeginifflag[p^.g]{没有被搜索过}thenbeginflag[p^.g]:=false;if(resultt[p^.g]=0)or(main(resultt[p^.g])){没有被连过或原来指向的节点寻找到新的增广路}thenbeginresultt[p^.g]:=wei;exit(true);end;end;p:=p^.next;end;exit(false)end;procereaddd(v1,v2:longint);//建立邻接表过程varp:node;beginnew(p);p^.g:=v2;p^.next:=nd[v1];nd[v1]:=p;end;beginreadln(n1,n2,m);fora:=1tomdobeginreadln(v1,v2);addd(v1,v2);end;ans:=0;fillchar(resultt,sizeof(resultt),0);fora:=1ton1dobeginfillchar(flag,sizeof(flag),true);ifmain(a)theninc(ans);end;writeln(ans);fora:=1ton2doifresultt[a]<>0thenwriteln(resultt[a],'---',a);end.
