首页 > 代码库 > POJ 1442 Air Raid（DAG图的最小路径覆盖）
POJ 1442 Air Raid（DAG图的最小路径覆盖）
题意：
有一个城镇，它的所有街道都是单行（即有向）的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。
可以在任意一个路口放置一个伞兵，这个伞兵会顺着街道走，依次经过若干个路口。
问最少需要投放几个伞兵，使得每个路口都被伞兵拜访过。并且要满足每个路口只能被一个伞兵拜访过。
思路：
裸DAG图的最小路径覆盖。
DAG图的最小路径覆盖数 = 节点数 - 二分图最大匹配
代码：
vector<int> graph[125];int cx[125],cy[125];bool bmask[125];int n,m;int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,n) cx[i]=cy[i]=-1; rep(i,1,n) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int T;int main(){ cin>>T; while(T--){ scanf("%d",&n); rep(i,1,n) graph[i].clear(); scanf("%d",&m); while(m--){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); } int dd=MaxMatch(); printf("%d\n",n-dd); }}
POJ 1442 Air Raid（DAG图的最小路径覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。