HDU 1150 Machine Schedule （匈牙利算法详解）

研究了几个小时，终于明白了。说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

嗯、其实不断的寻找增广路、如果能够找到那么匹配数就增加1、关于交换匹配连接那里用DFS还是很有意思的、

分析：这道题其实就是求最大的二分匹配数、图的最小点覆盖数 = 图的最大匹配数、

下面是用邻接矩阵实现的：

#include  
#include  
#define N 105  
int map[N][N];  
int use[N];  
int vis[N];  
int m,n,k;  
int find(int x){  
    for(int j=1;j 
  
 
 
 

再写个邻接表的：

#include  
#include  
#define N 105  
int root[N];  
int use[N];  
int vis[N];  
int m,n,k,ans;  
struct node{  
    int s,e,next;  
}fp[N];  
void add(int s,int e){  
    fp[++ans].e=e;  
    fp[ans].next=root[s];  
    root[s]=ans;  
}  
int find(int x){  
    for(int j=root[x];j!=-1;j=fp[j].next){  
        int e=fp[j].e;  
        if(vis[e]==0){  
            vis[e]=1;  
            if(use[e]==0||find(use[e])==1){  
                use[e]=x;  
                return 1;  
            }  
        }  
    }  
    return 0;  
}  
int main(){  
    while(scanf("%d",&n)!=EOF){  
        if(n==0)break;  
        scanf("%d%d",&m,&k);  
        memset(root,-1,sizeof(root));  
        int s,e,t;  
        while(k--){  
            scanf("%d%d%d",&t,&s,&e);  
            add(s,e);  
        }  
        int count=0;  
        memset(use,0,sizeof(use));  
        for(int i=1;i