参考:https://vjudge.net/solution/10901249
可是比赛的时候我没有看出来..
感觉好裸…都不想敲了…
但是这个地方为什么和缩点有关系呢..
题目:https://vjudge.net/contest/188571#problem/G
给你一个地图，L表示陆地，W表示水，C表示你可以任意安排，问最多有多少个陆地联通块。心得:这道题比赛的时候也想过把一开始的陆地旁边的C变为W.然后可能就是二分图匹配.但不知道会不会对,,而且水题还没过…
现在看来就是这样..感觉都是可以做的,只要敢做..
然后看了看,关键是要把”最大独立集问题”弄懂,,把各个名词弄好,应该就知道原因了..
可以参考http://blog.csdn.net/whosemario/article/details/8513836
这个地方的最后几行的原因:
二分图的最大独立集
如果一个图是二分图，那么它的最大独立集就是多项式时间可以解决的问题了 |最大独立集| = |V|-|最大匹配数|顺便补充的:(如果把概念弄好了,就更快上手)
二分图的最小顶点覆盖
定义：
寻找一个点集，使得图上任意一条边至少一个端点位于这个点集内部。二分图的|最小点集|=|最大匹配|
最大独立集就是其补图的最大团
最小路径覆盖
定义：
一个有向无环图，要求用尽量少的不相交的简单路径覆盖所有的节点。
构图：
建立一个二分图，把原图中的所有节点分成两份（X集合为i，Y集合为i'），如果原来图中有i->j的有向边，则在二分图中建立i->j'的有向边。最终|最小路径覆盖|=|V|-|M|
别人的代码:
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=65,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
int match[maxn*maxn];
int p[maxn][maxn],head[maxn*maxn];
bool visit[maxn][maxn],v[maxn*maxn];
char s[maxn][maxn];
int dir[4][2];
int n,m,num;
struct Edge {
int from,to,pre;
};
Edge edge[maxn*maxn*2];
void addedge(int from,int to) {
edge[num]=(Edge){from,to,head[from]};
head[from]=num++;
edge[num]=(Edge){to,from,head[to]};
head[to]=num++;
}
void dfs(int i,int j) {
visit[i][j]=1;
for (int k=0;k<4;k++) {
int x=i+dir[k][0],y=j+dir[k][1];
if (x>0&&y>0&&x<=n&&y<=m)
if (!visit[x][y]&&s[x][y]=='L') dfs(x,y);
if (s[x][y]=='C') s[x][y]='W';
}
}
bool hungary(int now) {
for (int i=head[now];i!=-1;i=edge[i].pre) {
int to=edge[i].to;
if (!v[to]) {
v[to]=1;
if (!match[to]||hungary(match[to])) {
match[to]=now;match[now]=to;
return true;
}
}
}
return false;
}
int main() {
dir[0][0]=dir[1][0]=dir[2][1]=dir[3][1]=0;
dir[0][1]=dir[2][0]=1;dir[1][1]=dir[3][0]=-1;
int i,j,k,ans=0;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) {
scanf("%s",s[i]+1);
}
mem0(visit);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (!visit[i][j]&&s[i][j]=='L') dfs(i,j),ans++;
int cnt=0;
memset(head,-1,sizeof(head));
num=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (s[i][j]=='C')
p[i][j]=++cnt;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (s[i][j]=='C'&&(i+j)%2==0)
for (k=0;k<4;k++) {
int x=i+dir[k][0],y=j+dir[k][1];
if (x>0&&y>0&&x<=n&&y<=m)
if (s[x][y]=='C') addedge(p[i][j],p[x][y]);
}
int sum=0;
mem0(match);
for (i=1;i<=cnt;i++)
if (!match[i]) {
mem0(v);v[i]=1;
if (hungary(i)) sum++;
}
ans+=cnt-sum;
printf("%d\n",ans);
return 0;
}