POJ 1422 Air Raid(DAG最小路径覆盖)
http://poj.org/problem?id=1422
题意:
城市里通过交点->交点(有向)标示一条街道(不存在回路)。问空袭时,需要如何降下最少的伞兵(放到交点路口上),使得伞兵能在不重复走同样交点的条件下,所有的伞兵遍历完整个城市的交叉路口。分析:
其实每个伞兵走的就是一条有向的简单路径.我们要求的就是该DAG图的最少可以用多少条简单路径覆盖所有节点且任意两条路径不会有重复的节点. 这就是DAG的最小路径覆盖问题.
DAG最小路径覆盖问题的解 = 节点数-二分图的最大匹配.
首先要把DAG中的每个点在二分图的左右点集都保存一遍,然后对于DAG中的边i->j, 那么就在二分图中添加边左i->右j. 之后求该二分图的最大匹配边数即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=120+5;
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;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
MM.init(n);
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
MM.g[u].push_back(v);
}
printf("%d\n",n-MM.solve());
}
return 0;
}
分享到:
相关推荐
poj2516代码最小费用最大流
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类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
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解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案