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

首先分析一下匈牙利算法的原理：（引用matrix67大牛的一段話）   研究了幾個小時，終於明白了。說穿了，就是你從二分圖中找出一條路徑來，讓路徑的起點和終點都是還沒有匹配過的點，並且路徑經過的連線是一條沒被匹配、一條已經匹配過，再下一條又沒匹配這樣交替地出現。找到這樣的路徑後，顯然路徑裡沒被匹配的連線比已經匹配了的連線多一條，於是修改匹配圖，把路徑裡所有匹配過的連線去掉匹配關系，把沒有匹配的連線變成匹配的，這樣匹配數就比原來多1個。不斷執行上述操作，直到找不到這樣的路徑為止。 嗯、其實不斷的尋找增廣路、如果能夠找到那麼匹配數就增加1、關於交換匹配連接那裡用DFS還是很有意思的、 分析：這道題其實就是求最大的二分匹配數、圖的最小點覆蓋數 = 圖的最大匹配數、 下面是用鄰接矩陣實現的：  

#include<stdio.h>  
#include<string.h>  
#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<m;j++){  
        if(map[x][j]==1&&vis[j]==0){  
            vis[j]=1;  
            if(use[j]==0||find(use[j])==1){  
                use[j]=x;  
                return 1;  
            }  
        }  
    }  
    return 0;  
}  
int main(){  
    while(scanf("%d",&n)!=EOF){  
        if(n==0)break;  
        scanf("%d%d",&m,&k);  
        memset(map,0,sizeof(map));  
        int s,e,t;  
        while(k--){  
            scanf("%d%d%d",&t,&s,&e);  
            map[s][e]=1;  
        }  
        int count=0;  
        memset(use,0,sizeof(use));  
        for(int i=1;i<n;i++){  
            memset(vis,0,sizeof(vis));  
            if(find(i))count++;  
        }  
        printf("%d\n",count);  
    }  
    return 0;  
}  

#include<stdio.h>  
#include<string.h>  
#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<n;i++){  
            memset(vis,0,sizeof(vis));  
            if(find(i))count++;  
        }  
        printf("%d\n",count);  
    }  
    return 0;  
}