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] = INF;

while(1)

{

memset(visx, false, sizeof(visx));

memset(visy, false, sizeof(visy));

if(dfs(i)) break;

int d = INF;

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

if(!visy[j] &&

d > slack[j])

d = slack[j];

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

{

if(visx[j]) lx[j] -= d;

if(visy[j]) ly[j] += d;

else slack[j] -= d;

}

}

}

int ans = 0;

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

{

if(pre[i] != -1)

ans -= g[pre[i]][i];

}

return ans;

}

int main(){

int h,v,mf,mm;

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

scanf("%d%d",&h,&v);

while(h!=0||v!=0){

mm=mf=0;

for(int i=0;i<h;i++)

for(int j=0;j<v;j++){

char c;

scanf("%c",&c);

while(c!='.'&&c!='H'&&c!='m')

scanf("%c",&c);

if(c=='H'){

ff[mf][0]=i;

ff[mf][1]=j;

mf++;

}

if(c=='m'){

man[mm][0]=i;

man[mm][1]=j;

mm++;

}

}

N=mm;

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

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

g[i][j]=-(abs(man[i][0]-ff[j][0])+abs(man[i][1]-ff[j][1]));

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

scanf("%d%d",&h,&v);

}

}

POJ 2446 Chessboard

算法：

很囧的题，本来打算用搜索过的，发现深搜肯定超时，试了一下，果然超时。然后想到bfs，但是怎么判断状态是否被扩展，hash太麻烦了，并且也不保证不超时，于是又放弃。但是dfs还是有可行的剪枝的，但是实现起来又麻烦，无奈一下，看题解。太佩服牛人了，这样都想到，其实类似的题好像我做过一题，但是忘记了。其实这题的正解是：二分图的匹配。至于怎样匹配，其实很简单，就是一个1*2的方块，其实只能覆盖行和列之和要么为奇数要么为偶数的两个点，那么我们就把各个点划分成这两种，相邻的两边，然后如果存在完全匹配，则输出YES。

代码：

#include<cstdio>

#include<string>

using namespace std;

#define MAX 35

bool a[35][35];

int m,n,k;

int l[MAX*MAX];

int sl;

int root[MAX*MAX];

bool use[MAX*MAX];

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

inline bool can(int i,int j){

return i>=1&&i<=n&&j>=1&&j<=m;

}

bool find(int k){

int x=k/MAX,y=k%MAX;

int i;

for(i=0;i<4;i++){

int sx=x+dir[i][0],sy=y+dir[i][1];

if(can(sx,sy)&&!a[sx][sy]){

int sk=sx*MAX+sy;

if(!use[sk]){

use[sk]=true;

if(root[sk]==-1||find(root[sk])){

root[sk]=k;

return true;

}

}

}

}

return false;

}

void solve(){

int i,j;

sl=0;

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

for(j=1;j<=m;j++){

if(!a[i][j]&&((i+j)%2==0))l[sl++]=i*MAX+j;

}

}

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

int ans=0;

for(i=0;i<sl;i++){

memset(use,false,sizeof(use));

if(find(l[i]))ans++;

}

if(ans==sl)printf("YES\n");

else printf("NO\n");

}

int main(){

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

int i;

for(i=0;i<k;i++){

int x,y;

scanf("%d%d",&x,&y);

a[x][y]=true;

}

solve();

return 0;

}

poj 1422 Air Raid 最小路径覆盖 模板题

题意：

一个镇里所有的路都是单向路且不会组成回路。

派一些伞兵去那个镇里，要到达所有的路口，有一些或者没有伞兵可以不去那些路口，只要其他人能完成这个任务。每个在一个路口着陆了的伞兵可以沿着街去到其他路口。我们的任务是求出去执行任务的伞兵最少可以是多少个。

思路：

这个题就是个最小路径覆盖问题。

路径覆盖的定义是：在有向图中找一些路径，使之覆盖了图中的所有顶点，就是任意一个顶点都跟那些路径中的某一条相关联，且任何一个顶点有且只有一条路径与之关联，一个单独的顶点是一条路径.最小路径覆盖就是最少的路径覆盖数。

有定理： 最小路径覆盖 = 图的顶点数 – 最大匹配数。

总结：

1.用匈牙利算法求二分匹配，利用最小路径覆盖=顶点总数-最大匹配

2.把每个点拆点为出点和入点

#include<iostream>

using namespace std;

int g[121][121],match[121],mark[121];

int n,m;

int dfs(int i)

{

int j;

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

if(g[i][j] && !mark[j])

{

mark[j]=1;

if(match[j]==-1 || dfs(match[j]))

{

match[j]=i;

return 1;

}

}

return 0;

}

int main()

{

int s,i,sum,v1,v2;

scanf("%d",&s);

while(s--)

{

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

memset(g,0,sizeof(g));

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

{

scanf("%d%d",&v1,&v2);

g[v1][v2]=1;

}

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

sum=0;

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

{

memset(mark,0,sizeof(mark));

if(dfs(i)) sum++;

}

printf("%d\n",(n-sum));

}

system("pause");

}

POJ 2594* Treasure Exploration 2分匹配

跟1422类似 都是求最小路径覆盖

区别在于这题一个点可以走多次 即建图时要使用可达关系

之前先做一次Floyd再建图即可

#include <iostream>

using namespace std;

bool isconnect[2000][2000]; //邻接矩阵 n m 从1 -- n 1 -- m int mat[2000]; //T中顶点匹配到S中哪个 为匹配时为0 bool ismat[2000]; //T中顶点此次是否已增广

int n,m; //n=|S| m=|T|

bool find(int x)

{

for(int i=1;i<=m;i++)

{

if(isconnect[x][i] && !ismat[i])

{

ismat[i]=1;

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

{

mat[i]=x;

return 1;

}

}

}

return 0;

}

int biMatch()

{

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

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

{

memset(ismat,0,sizeof(ismat));

result+=find(i);

}

return result;

}

bool adj[600][600];

int main()

{

int rn,st,ed;

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

{

memset(adj,0,sizeof(adj));

if(!(n||rn)) break;

for(int i=1;i<=rn;i++)

{

scanf("%d%d",&st,&ed);

adj[st][ed]=1;

}

for(int k=1;k<=n;k++)

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

for(int j=1;j<=n;j++)

adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]); m=n;

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

for(int j=1;j<=n;j++)

isconnect[i][j] = adj[i][j];

printf("%d\n",n-biMatch());

}

return 0;

}