图论相关之匈牙利算法

这个本来应该是在大一就掌握的算法，硬生生被我拖到现在。。。

　匈牙利算法是用来求二分图的最大匹配的一种比较简单的算法，最核心的东西就是找增广路径。详情：http://blog.csdn.net/acdreamers/article/details/8621130

　　记住一些常见的结论：

　　(1)二分图的最小顶点覆盖

　　最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。

　　Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。

　　(2)DAG图的最小路径覆盖

　　用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。

　　结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

　　(3)二分图的最大独立集

　　最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值

　　结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

匈牙利算法模板：

bool dfs(int x) {
	for(int j=0; j<n; j++) {
		if( Map[x][j] && !vis[j] ) {
			vis[j] = true;
			if( link[j]==-1 || dfs(link[j]) ) {
				link[j] = x;
				return true;
			}
		}
	}
	return false;
} 

void solve() {
	int res = 0;
	CLS(link, -1);
	for(int i=0; i<n; i++) {
		CLS(vis, false);
		if( dfs(i) ) res ++;
	}
	//这个res便是最大匹配数
}

再加几个模板题吧！http://acm.hdu.edu.cn/showproblem.php?pid=1150

这个是求最小顶点覆盖~

//Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a )  cout << #a << " = "  << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1005;
int n, m, num, T, k, x, y, len, ans;
int endx, endy, t;
int Map[maxn][maxn];
bool vis[maxn];
int link[maxn];

bool dfs(int x) {
    for(int j=0; j<m; j++) {
        if( Map[x][j] && !vis[j] ) {
            vis[j] = true;
            if( link[j]==-1 || dfs(link[j]) ) {
                link[j] = x;
                return true;
            }
        }
    }
    return false;
} 

void solve() {
    int res = 0;
    CLS(link, -1);
    for(int i=0; i<n; i++) {
        CLS(vis, false);
        if( dfs(i) ) res ++;
    }
    prd(res);
}

void input() {
    while( ~srd(n) && n ) {
        srdd(m, num);
        memset(Map, 0, sizeof(Map));
        for(int i=0; i<num; i++) {
            srddd(x, x, y);
            if( x&&y ) Map[x][y] = 1;
        }
        solve();
    }
}

int main(){
    input();
    return 0;
}

第二个：http://acm.hdu.edu.cn/showproblem.php?pid=1068

求最小路径覆盖数。由于本题是双向图，所以最小路径覆盖数等于顶点数n双向图的最大匹配/2

//Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a )  cout << #a << " = "  << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1005;
int n, m, num, T, k, x, y, len, ans;
int Map[maxn][maxn];
bool vis[maxn];
int link[maxn];

bool dfs(int x) {
    for(int j=0; j<n; j++) {
        if( Map[x][j] && !vis[j] ) {
            vis[j] = true;
            if( link[j]==-1 || dfs(link[j]) ) {
                link[j] = x;
                return true;
            }
        }
    }
    return false;
} 

void solve() {
    int res = 0;
    CLS(link, -1);
    for(int i=0; i<n; i++) {
        CLS(vis, false);
        if( dfs(i) ) res ++;
    }
    prd(n-res/2);
}

void input() {
    while( ~srd(n) ) {
        memset(Map, 0, sizeof(Map));
        for(int i=0; i<n; i++) {
            scanf("%d: (%d)", &x, &num);
            for(int j=0; j<num; j++) {
                srd(y);
                Map[x][y] = 1;
            }
        }
        solve();
    }
}

int main(){
    input();
    return 0;
}

再贴一个题。。http://acm.hdu.edu.cn/showproblem.php?pid=1054

但是，很尴尬的是，我不用vector竟然时间超限。。蒙~~~

求最小顶点覆盖。由于本题是双向图，所以最小顶点覆盖等于双向图的最大匹配/2。

//Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a )  cout << #a << " = "  << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1505;
int n, m, num, T, k, x, y, len, ans;
int endx, endy, t;
bool vis[maxn];
int link[maxn];
vector<int> Map[maxn];

bool dfs(int x) {
    int l ;
    for(int j=0; j<Map[x].size(); j++) {
        l = Map[x][j];
        if( !vis[l] ) {
            vis[l] = true;
            if( link[l]==-1 || dfs(link[l]) ) {
                link[l] = x;
                return true;
            }
        }
    }
    return false;
} 

void solve() {
    int res = 0;
    CLS(link, -1);
    for(int i=0; i<n; i++) {
        CLS(vis, false);
        if( dfs(i) ) res ++;
    }
    prd(res/2);
}

void input() {
    while( ~srd(n) ) {
        for(int i=0; i<n; i++) Map[i].clear();
        for(int i=0; i<n; i++) {
            scanf("%d: (%d)", &x, &num);
            for(int j=0; j<num; j++) {
                srd(y);
                Map[x].push_back(y);
                Map[y].push_back(x);
//                Map[x][y] = 1;
//                Map[y][x] = 1;
            }
        }
        solve();
    }
}

int main(){
    input();
    return 0;
}

最后一道~http://acm.hdu.edu.cn/showproblem.php?pid=1151

最小路径覆盖数，双向图，所以res/2。

//Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a )  cout << #a << " = "  << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1005;
int n, m, num, T, k, x, y, len, ans;
int endx, endy, t;
int Map[maxn][maxn];
bool vis[maxn];
int link[maxn];

bool dfs(int x) {
    for(int j=1; j<=n; j++) {
        if( Map[x][j] && !vis[j] ) {
            vis[j] = true;
            if( link[j]==-1 || dfs(link[j]) ) {
                link[j] = x;
                return true;
            }
        }
    }
    return false;
} 

void solve() {
    int res = 0;
    CLS(link, -1);
    for(int i=1; i<=n; i++) {
        CLS(vis, false);
        if( dfs(i) ) res ++;
    }
    prd(n-res);
}

void input() {
    srd(T);
    while( T -- ) {
        srdd(n, num);
        memset(Map, 0, sizeof(Map));
        for(int i=0; i<num; i++) {
            srdd(x, y);
            Map[x][y] = 1;
        }
        solve();
    }
}

int main(){
    input();
    return 0;
}