zoj1654

参考《算法艺术与信息学竞赛》P334 皇家卫士

把每个横向线段当作集合A 每个纵向线段当作集合B

如果是空地则A，B中的点有一条边，最大二分匹配

如o***

就对应了一条横向线段A1，和4条纵向线段B1，B2，B3，B4

其中A1和B1的交点是空地，所以他们之间有一条边，所以每个边都会对应一个点，这个点为一个横向线段和纵向线段的交点

#include
#include
#include
#define MAX 100
using namespace std;
int n,p;
int map[MAX*26][MAX*26];
bool visit[MAX*26];
int match[MAX*26];
bool find(int k)
{int i,j;for(i=1;i<=n;i++){if(map[k][i]&&visit[i]==false){visit[i]=true;if(match[i]==0||find(match[i])){match[i]=k;return true;}}}return false;
}
int hungary() 
{memset(match,0,sizeof(match));int sum=0;for(int i=1;i<=p;i++){memset(visit,0,sizeof(visit));if(find(i))sum++;}return sum;
}
struct node
{int x;int y;
}point[MAX][MAX];
int main()
{int i,j,k,t;int r,c;char str[MAX][MAX]; scanf("%d",&t);for(k=1;k<=t;k++){memset(map,0,sizeof(map));n=0;p=0;scanf("%d%d",&r,&c);for(i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！