http://poj.org/problem?id=3020

求最小路徑覆蓋問題 ，對于有向圖最小路徑覆蓋 = 一邊的點數 （x集或y集）- 最大匹配

無向圖最小路徑覆蓋 = 一邊的點數 （x集或y集）- 最大匹配/2

注意建圖的細節實現。。。還有注意轉化點后的取值。。

View Code #include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 45
using namespace std;

int map[maxn*15][maxn*15],num[maxn][15];//注意這里的map坐標的取值。。。
//考慮不全，整死我了。。
bool vt[maxn*15];
int link[maxn*15];
char str[maxn][15];
int h,w,ct;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

bool dfs(int rpos)
{
int i;
for (i = 1; i <= ct; ++i)
{
if (!vt[i] && map[rpos][i])
{
vt[i] = true;
if (link[i] == -1 || dfs(link[i]))
{
link[i] = rpos;
return true;
}
}
}
return false;
}
int H()
{
int i;
int count = 0;
memset(link,-1,sizeof(link));
for (i = 1; i <= ct; ++i)
{
memset(vt,false,sizeof(vt));
if (dfs(i)) count++;
}
return (ct - count/2);
}
int main()
{
int i,j,k,t;
cin>>t;
while (t--)
{
cin>>h>>w;
ct = 0;
for (i = 0; i < h; ++i)
{
cin>>str[i];
for (j = 0; j < w; ++j)
{
if (str[i][j] == '*')
num[i][j] = ++ct;
}
}
memset(map,0,sizeof(map));
for (i = 0; i < h; ++i)
{
for (j = 0; j < w; ++j)
{
if (str[i][j] == '*')
{
for (k = 0; k < 4; ++k)
{
int x = i + dir[k][0];
int y = j + dir[k][1];
if (x >= 0 && x < h && y >= 0 && y <w && str[x][y] == '*')
map[num[i][j]][num[x][y]] = 1;
}
}
}
}
printf("%d\n",H());
}
return 0;
}

轉載于:https://www.cnblogs.com/E-star/archive/2012/03/15/2398387.html

總結

以上是生活随笔為你收集整理的pku 3020 Antenna Placement的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。