【二分図マッチング】zoj 1002 Fire Net
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002 タイトルの説明:与えられたn*nの地図に対して、砲塔を入れて、それらの間に衝突しないようにします.それらが同じ行または同じ列にある場合、その間に障害物がなく、衝突します.最大でどれだけの砲塔を入れることができることを求めます.
二分図は古典モデルに一致する.各行の連通ブロック縮点をx集合,各列の連通ブロック縮点をy集合とする.インターコネクトブロックの間に交点がある場合は、エッジが接続されます.その後、最大マッチングを1回すれば解くことができます.
もちろんnの範囲が小さいので、直接検索できます.
二分図は古典モデルに一致する.各行の連通ブロック縮点をx集合,各列の連通ブロック縮点をy集合とする.インターコネクトブロックの間に交点がある場合は、エッジが接続されます.その後、最大マッチングを1回すれば解くことができます.
もちろんnの範囲が小さいので、直接検索できます.
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 125
using namespace std;
int n ,cntx ,cnty ,cx[MAXN] ,cy[MAXN] ,tmp[15][15] ;
char map[15][15] ;
bool vis[MAXN<<1] ,flag[MAXN][MAXN];
void build()
{
memset(flag,0,sizeof flag);
memset(tmp,0,sizeof tmp);
cntx=1;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
if(map[i][j]=='X')++cntx;
else tmp[i][j]=cntx;
if(map[i][n-1]!='X')++cntx;
}
cnty=1;
for(int j=0;j<n;++j)
{
for(int i=0;i<n;++i)
if(map[i][j]=='X')++cnty;
else flag[tmp[i][j]][cnty]=1;
if(map[n-1][j]!='X')++cnty;
}
}
bool dfs(int u)
{
for(int v=1;v<=cnty;++v)
if(!vis[v]&&flag[u][v])
{
vis[v]=1;
if(!cy[v]||dfs(cy[v]))
{
cx[u]=v ,cy[v]=u ;
return 1;
}
}
return 0;
}
void solve()
{
memset(cx,0,sizeof cx);
memset(cy,0,sizeof cy);
int ans=0;
for(int i=1;i<=cntx;++i)
if(!cx[i])
{
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
printf("%d
",ans);
}
int main()
{
while(~scanf("%d",&n)&&n)
{
for(int i=0;i<n;++i)
scanf("%s",map[i]);
build();
solve();
}
return 0;
}