No.30 - POJ1325 - 匈牙利算法-白红宇

No.30 - POJ1325 - 匈牙利算法

阅读量：4059 次

发布时间：2019-05-25

本文共 2403 字，大约阅读时间需要 8 分钟。

首先题目是求二部图的最小点覆盖集。

$\red{最小点覆盖：}$ 取最少的点使图没有孤立边

有个转化定理： $\green{二部图}$ 的 $\blue{最小点覆盖集}$ = $\blue{最大匹配}$

很好理解，倘若最小点覆盖集之外，还有一对儿匹配，则该边是孤立边，该边中点任意一点应该划入最小点覆盖集。

相反，若最大匹配所包含的点之外，还有边没有连接到这些点，则这条边及其两点可以再形成一个匹配。

$\green{再说说匈牙利算法：}$

实质上是一种暴力搜索算法，

对于一个x，按任意顺序找一个y，如果能匹配上，则找下一对儿。

若不能，递归处理之前匹配到y的x能不能再换个对象。

如果换所有y都不能，那当前x匹配失败。

// ShellDawn// POJ1325// No.30#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;//#define maxn 220int N,M,K;int E[maxn][maxn];int V[maxn];int Match[maxn];bool dfs(int x){ for(int i=1;i<=M;i++){ if(E[x][i] == 1&&V[i] == 0){ V[i] = 1; if(Match[i] == -1 || dfs(Match[i])){ Match[i] = x; return true; } } } return false;}int main(){ while(~scanf("%d",&N)&&N){ scanf("%d%d",&M,&K); MM(E,0);MM(Match,-1); while(K--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); E[b][c] = 1; } int ans = 0; for(int i=1;i

网络流也可以解最大匹配：

$\red{不过代码长}$

// ShellDawn// POJ1325// No.30#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;//#define maxn 210int N,M,K;int S,T;struct Edge{ int to; int v; int rvs; int pre;};Edge E[2019+maxn+maxn];int pre[maxn];int cnt;int V[maxn];void add(int from,int to,int v){ E[cnt].to = to; E[cnt].v = v; E[cnt].rvs = cnt+1; E[cnt].pre = pre[from]; pre[from] = cnt++; E[cnt].to = from; E[cnt].v = 0; E[cnt].rvs = cnt-1; E[cnt].pre = pre[to]; pre[to] = cnt++;}bool BFS(int s){ MM(V,0); queue
         
           q; q.push(s); V[s] = 1; while(!q.empty()){ int now = q.front(); q.pop(); for(int i=pre[now];i!=0;i=E[i].pre){ if(E[i].v > 0 && V[E[i].to] == 0){ V[E[i].to] = V[now] + 1; q.push(E[i].to); } } } if(V[T] > 0) return true; return false;}int DFS(int now,int minflow){ if(now == T) return minflow; int flow = 0; for(int i=pre[now];i!=0 && minflow; i=E[i].pre){ if(E[i].v > 0 && V[E[i].to] == V[now]+1){ int f = DFS(E[i].to,min(minflow,E[i].v)); minflow -= f; flow += f; E[i].v -= f; E[E[i].rvs].v += f; } } if(flow == 0) V[now] = 0; return flow;}int main(){ while(~scanf("%d",&N)&&N){ scanf("%d%d",&M,&K); S = N+M+1 ; T = N+M+2; cnt = 1; MM(pre,0); for(int i=0;i