这两道题都是有关于二分图的最大匹配问题。
二分图：给定的两个点集。一些边，如果所有的边的两个顶点都分别属于那两个点集的话，这个图就是二分图。
二分图的最大匹配：
给定一个二分图G，在G的一个子图的边集中的任意两条边都不依附于同一个顶点，则称此子图是一个匹配。
选择这样的边数最大的子集称为图的最大匹配。
定理：
1，最大匹配数=最小覆盖数
2，最小路径覆盖 = 顶点数 – 最大二分匹配数
对于3020这道题目，把所有的城市都看成两个点，两个子集一边一个。
然后边就是相邻的城市。然后对这个二分图求最大匹配。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int map[501][501];
int city[501][501];
int visit[501];
int f[501];
int number;
int find(int x)
{int i;for(i=1;i<number;i++){if(city[x][i]&&!visit[i]){visit[i]=1;if(f[i]==0||find(f[i])){f[i]=x;return 1;}}}return 0;
}
int main()
{int T;int n,m,i,j,k;char c;scanf("%d",&T);while(T--){memset(map,0,sizeof(map));number=1;scanf("%d%d%*c",&n,&m);memset(f,0,sizeof(f));memset(city,0,sizeof(city));for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%c",&c);if(c=='o')continue;map[i][j]=number;for(k=0;k<4;k++){if(map[i-1][j]!=0){city[map[i-1][j]][number]=1;city[number][map[i-1][j]]=1;}if(map[i][j-1]!=0){city[map[i][j-1]][number]=1;city[number][map[i][j-1]]=1;}}number++;}getchar();}int sum=0;for(i=1;i<number;i++){memset(visit,0,sizeof(visit));if(find(i))sum++;}printf("%d\n",number-1-sum/2);//因为是复制的城市，所以二分图中实际上有2n个城市，所以最小路径覆盖 = 顶点数 – 最大二分匹配数/2；}return 0;
}