ACM必做50题的解题-二分图

poj 1325 Machine Schedule(最小点覆盖->二分图最大匹

配)

题意：

有两台机器A和B，分别有n种和m种不同的模式，有k个工作，每个工作都可以在那两个机器的某种特定的模式下处理。如job0既可以在A机器的3好模式下处理，也可以在B机器的4号模式下处理。

机器的工作模式改变只能通过人工来重启。通过改变工作的顺序，和分配每个工作给合适的机器可以减少重启机器的次数达到最小。任务就是计算那个最小的次数。初始时两台机器都运行在0号模式下。

思路：

把每个任务化为一条线，假设任务i在A机器上处理的模式为A［x]点，在B机器上为B［y]点，连接A[x]和B[y],用A机器和B机器中最少的点覆盖所有的边（用最少的模式完成所有的任务）。这是最小点覆盖问题，根据König定理（一个二分图中的最大匹配数等于这个图中的最小点覆盖数）就是求的二分图的最大匹配，然后再用匈牙利算法直接就算出最大匹配数了，要注意的是初始是在0号模式下，所以如果A或B机器其中至少有个在0号模式下时就不用重启机器了，所以建图的时候没有把0建进去。

关于二分匹配在http:///u3/102624/showart.php?id=2060232

#include <stdio.h>

#include <string.h>

#define N 105

#define M 1005

int g[N][N];

int used[N], mat[N], flag[N];

int min, n, m;

/*寻找增广路径*/

int find(int k)

{

int i, j;

for(i=1; i<=g[k][0]; i++)

{

j = g[k][i];

if(!used[j])

{

used[j] = 1;

if(mat[j]==-1 || find(mat[j]))

{

mat[j] = k;

return 1;

}

}

}

return 0;

}

/*匈牙利算法*/

void hungary()

{

int i;

for(i=1; i<=n-1; i++)

{

min += find(i);

memset(used, 0, sizeof(used));

}

printf("%d\n", min);

}

int main()

{

int i, j;

int k, a, b, c;

while(scanf("%d", &n) && n)

{

scanf("%d%d", &m, &k);

memset(mat, -1, sizeof(mat));

memset(g, 0, sizeof(g)); //一开始这个没有初始化，wa了好多次，搞好久 ==! for(i=0; i<k; i++)

{

scanf("%d%d%d", &a, &b, &c);

if(b != 0 && c != 0)

{

g[b][++g[b][0]] = c; //邻接表

}

}

min = 0;

hungary();

}

}

poj 1469 COURSES

二分匹配问题：匈牙利算法实现（可以作为模板）

//二分匹配中，两个集合不能存在交集

#include <iostream>

#include <string.h>

#include <stdio.h>

using namespace std;

#define array1 101

#define array2 301

bool map[array1][array2]; //定义临界矩阵

int final[array2];

int match[array2];

int p,n; //两个集合分别存储p个元素和 n个元素

int DFS(int p) //p为课程

{

int i;

int t;

//遍历所有的学生

for(i=1;i<n+1;++i)

{

if(map[p][i] && !final[i])

{

final[i] = 1;

t= match[i];

match[i]= p; //路径取反操作 (原来在匹配中的边变成不在匹配中，不在的变成在每一次)

if(t==0 || DFS(t)) return 1; //找到了一条增广路径

match[i] = t;

}

}

return 0; //没有找到增广路径

}

int mat()

{

int matchmax = 0; //matchmax为最大匹配数

//遍历所有的课程

for(i=1;i<p+1;++i)

{

memset(final,0,sizeof(final)); //重新标记未访问,此处要注意

if(DFS(i)) matchmax++;

}

return matchmax;

}

int main()

{

//freopen("1.txt","r",stdin);

int t;

int i,j,k;

int temptcount;

int stu;

scanf("%d",&t);

for(i=0;i<t;++i)

{

memset(map,0,sizeof(map)); //对临界矩阵进行初始化

memset(match,0,sizeof(match));

scanf("%d%d",&p,&n);

for(j=1;j<p+1;++j)

{

scanf("%d",&temptcount);

for(k=0;k<temptcount;++k)

{

scanf("%d",&stu);

map[j][stu] = 1;

}

}

if(mat()==p) printf("YES\n");

else printf("NO\n");

}

return 0;

}

POJ 2195 Going Home

二分图最佳匹配，经典的KM算法

#include <stdio.h>

#include <string.h>

const int MAXN = 200+5;

const int INF = 1000000000;

int N;

int g[MAXN][MAXN];

int pre[MAXN];

int lx[MAXN], ly[MAXN], slack[MAXN],man[MAXN][2],ff[MAXN][2];

bool visx[MAXN], visy[MAXN];

int abs(int a){

if(a<0)

return -a;

return a;

}

bool dfs(int t)

{

int i;

visx[t] = true;

for(i = 0; i < N; i++)

{

if(visy[i]) continue;

int tmp = lx[t]+ly[i]-g[t][i];

if(tmp == 0)

{

visy[i] = true;

if(pre[i] == -1 || dfs(pre[i]))

{

pre[i] = t;

return true;

}

}

else if(slack[i] > tmp)

{

slack[i] = tmp;

}

}

return false;

}

int KM()

{

int i, j, k;

for(i = 0; i < N; i++)

lx[i] = -INF;

memset(ly, 0, sizeof(ly));

memset(pre, -1, sizeof(pre));

for(i = 0; i < N; i++)

for(j = 0; j < N; j++)

if(lx[i] < g[i][j])

lx[i] = g[i][j];

for(i = 0; i < N; i++)

{

for(j = 0; j < N; j++) slack[j] …… 此处隐藏：4969字，全部文档内容请下载后查看。喜欢就下载吧 ……