首页 > 代码库 > POJ 3020 (二分图+最小路径覆盖）
POJ 3020 (二分图+最小路径覆盖）
题目链接：http://poj.org/problem?id=3020
题目大意：读入一张地图。其中地图中圈圈代表可以布置卫星的空地。*号代表要覆盖的建筑物。一个卫星的覆盖范围是其周围上下左右四个点。问最少需要几个卫星才能覆盖所有建筑物。
解题思路：
有点类似POJ 1328的覆盖题，不过那题比较简单可以贪心。这题你可以YY试试。
覆盖问题其实可以用图论解决。这题就属于最小路径覆盖，手动由一个点出发连一些路径，这样Hungry就能求出最少需要多少这样的中心点，就可以达成目标了。
本题最大的疑问是到底是建有向图，还是无向图。由于Hungry只适用于有向图，所以好像应该建有向图。但是扫描这个图的时候，Hash图上点不算简单，需要对n*m标个号，然后Hash。
建无向图其实也不是很简单，需要拆点，模拟出所谓的“有向图”来Hungry，本点放在X集，影子点放在Y集，如果有边（u，v），则u连v‘(本点连影子点），对邻接矩阵每个城市相邻四个点扫一下加下边，这样自动模拟出"有向图"。
跑一遍Hungry，ans=建筑物数-match/2。（无向图match是两倍）
#include "iostream"#include "cstdio"#include "cstring"#include "string"#include "fstream"using namespace std;int G[401][401],link[401];int map[410][410];bool vis[801];int Case,n,m,pos;void AddEdge(int x,int y){ G[x][y]=1; //本点连影子点}bool dfs(int u){ for(int v=1;v<=pos;v++) { if(G[u][v]&&!vis[v]) { vis[v]=true; if(!link[v]||dfs(link[v])) { link[v]=u; return true; } } } return false;}int main(){ #define fin cin ifstream fin("in.txt"); string line; cin>>Case; while(Case--) { pos=0; int res=0; cin>>n>>m; getline(cin,line); for(int i=1;i<=n;i++) //吸收残留 { getline(cin,line); for(int j=0;j<line.size();j++) if(line[j]==‘*‘) map[i][j+1]=++pos; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(map[i][j]&&map[i-1][j]) AddEdge(map[i][j],map[i-1][j]); if(map[i][j]&&map[i+1][j]) AddEdge(map[i][j],map[i+1][j]); if(map[i][j]&&map[i][j-1]) AddEdge(map[i][j],map[i][j-1]); if(map[i][j]&&map[i][j+1]) AddEdge(map[i][j],map[i][j+1]); } } for(int i=1;i<=pos;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) res++; } res=pos-res/2; cout<<res<<endl; memset(map,0,sizeof(map)); memset(G,0,sizeof(G)); memset(link,0,sizeof(link)); }}
POJ 3020 (二分图+最小路径覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。