「专题训练」Air|「专题训练」Air Raid（HDU-1151）「专题训练」AirRaid（HDU-1151）

题目在一个城市里有\(n\)个地点和\(k\)条道路，道路是无环的（也就是说一定可以二分染色——回路长度为偶数0），现在伞兵需要去n个地点视察，只能沿着路的方向走，问最少需要多少伞兵。
分析 【「专题训练」Air|「专题训练」Air Raid（HDU-1151）】这是什么问题？找出最少的边，访问所有的点——二分图的的最小路径覆盖。
那么对于一个最大匹配，它能覆盖（2*最大匹配）个点，剩下的点都需要单独一条边覆盖，从而设匹配数为\(k\)，覆盖数为\(p\)，有\[n-2*k+k=p\]，也就是\(n-k=p\)。
代码

#include #include #include #define MP make_pair #define PB push_back #define fi first #define se second #define ZERO(x) memset((x), 0, sizeof(x)) #define ALL(x) (x).begin(),(x).end() #define rep(i, a, b) for (int i = (a); i <= (b); ++i) #define per(i, a, b) for (int i = (a); i >= (b); --i) #define QUICKIO\ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define MS(x,y) memset(x,y,sizeof(x)) using namespace std; bool mat[125][125],vis[125]; int n,m; int link[125]; bool dfs(int x) { rep(i,1,n) { if(mat[x][i] && !vis[i]) { vis[i]=true; if(link[i]==-1 || dfs(link[i])) { link[i]=x; return true; } } } return false; }int hungary() { int ans=0; rep(i,1,n) { ZERO(vis); if(dfs(i)) ans++; } return ans; }int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); ZERO(mat); ZERO(vis); MS(link,-1); rep(i,1,m) { int a,b; scanf("%d%d", &a, &b); if(a && b) mat[a][b]=1; } printf("%d\n", n-hungary()); } return 0; }

转载于:https://www.cnblogs.com/samhx/p/HDU-1151.html