本文主要是介绍hdu 1151 Air Raid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
主题思想： DAG 有向无环图，最少路径覆盖
本质二分图最大匹配问题
二分图最大匹配数=最小点覆盖数DAG最少路径覆盖数=DAG顶点数-二分图最大匹配数。
特别的 无向图的最大匹配数需要除以2。且顶点是全体。AC代码：
#include <iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;const int maxn=125;
vector<int> g[maxn];
int n,k;
bool visited[maxn];
int matched[maxn];
bool dfs(int v){for(vector<int>::iterator it=g[v].begin();it!=g[v].end();it++){int w=*it;if(!visited[w]){visited[w]=true;if(matched[w]==-1||dfs(matched[w])){matched[w]=v;return true;}}}return false;
}
int hungarian(){// only 0 ,-1 can use memset// if the array is not char array(single byte)memset(matched,-1,sizeof(matched));int total=0;for(int i=1;i<=n;i++){memset(visited,false,sizeof(visited));if(dfs(i)) total++;}return total;
}
int main()
{int T;scanf("%d",&T);int ans=0;while(T--){scanf("%d%d",&n,&k);//initfor(int i=1;i<=n;i++)g[i].clear();int s,e;for(int i=0;i<k;i++){scanf("%d%d",&s,&e);g[s].push_back(e);}ans=n-hungarian();printf("%d\n",ans);}return 0;
}
这篇关于hdu 1151 Air Raid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
