POJ 1548 Robots(DAG最小路径覆盖)
http://poj.org/problem?id=1548
题意:
给出一个矩阵,派机器人从最左上点到最右下点走,并且每个机器人只能往下走或往右走,在矩阵中的一些格子中有含有一个‘G’,问最少需要多少机器人,才能把所有的G都走到
分析:
仔细分析一下,其实本题就是DAG的最小路径覆盖.
对于矩阵中的任意两个Gi和Gj. 如果i点的行和列号都<=j点的行和列号,那么就有一条从i到j的边(表示从i点能走到j点). 那么最终肯定会形成一个DAG图.
现在的问题是我们需要在DAG中选择最少的简单路径来覆盖所有的节点. 这个问题就是DAG的最小路径覆盖 = n-二分图最大匹配数.
直接建图求匹配数即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=24*24+10;
struct Max_Match
{
int n;
vector<int> g[maxn];
bool vis[maxn];
int left[maxn];
void init(int n)
{
this->n=n;
for(int i=1;i<=n;i++) g[i].clear();
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=true;
if(left[v]==-1 || match(left[v]))
{
left[v]=u;
return true;
}
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ++ans;
}
return ans;
}
}MM;
struct Node
{
int x,y;
Node(){}
Node(int x,int y):x(x),y(y){}
bool link(Node& rhs)
{
if(x<=rhs.x && y<=rhs.y) return true;
return false;
}
}nodes[maxn];
int main()
{
int num,x,y;
while(scanf("%d%d",&x,&y)==2)
{
if(x==-1 && y==-1) break;
if(x==0 && y==0) continue;
num=1;
nodes[num]=Node(x,y);
while(scanf("%d%d",&x,&y)==2 && x)
{
nodes[++num]=Node(x,y);
}
MM.init(num);
for(int i=1;i<=num;i++)
for(int j=1;j<=num;j++)if(i!=j)
if(nodes[i].link(nodes[j]))
MM.g[i].push_back(j);
printf("%d\n",num-MM.solve());
}
return 0;
}
分享到:
相关推荐
北大POJ2632-Crashing Robots 解题报告+AC代码
poj2516代码最小费用最大流
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类