HDU 1151 Air Raid

知识点：二分匹配、贪心、思维

题目

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town’s streets you can never reach the same intersection i.e. the town’s streets form no cycles.

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.

输入

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:

no_of_intersections
no_of_streets
S1 E1
S2 E2
…
Sno_of_streets Eno_of_streets

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town’s streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.

There are no blank lines between consecutive sets of data. Input data are correct.

输出

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.

样例

输入

输出

2
1

题意

在一个DAG图（有向无环图）中放置最少数量的人，使得所有的节点可以被人沿着路径访问到且不被重复访问，求最少数量。

思路

首先题目没看懂，其次若不是在二分匹配专题里根本想不到用二分匹配，而且二分匹配用错思路了。
首先直观考虑，在每个节点放置人，再考虑移除不需要的人。

贪心一个人访问尽可能多的点，发现1->3->4->5

下面证明不会有更优的移除方案：
显然只有一个人通过进入4的边到达4，如果换一条进入4的边到达4，原来到达4的路径减少一个访问点，同时现在到达4的路径增加一个访问点，不能使答案更优；对从4出去的路径也有类似结论。
考虑如何贪心，如果一个人后继有若干人，则这个人可以移除其中一个后继人；如果一个人前驱有若干人且可被这些人中的若干人移除，那么这个人可以选择其中一个前驱移除自己，让其他前驱移除其他的前驱的后继人（有点匹配的意思）。
注意到对一个点选择不同出边只改变了出点，即出点互斥，同理入点互斥，所以可将入点和出点各归为一个集合，两个集合中的点连接表示选择这条边，终于成为二分图匹配。
一条路径的起始点作为出点没有匹配，结束点作为入点没有匹配，如果连接两点就可以完全匹配，说明匹配失败的数量为需要的人数，人数最少即匹配成功数量最多，故答案为节点数量-最大匹配数量。
实现思路见代码。

代码

#include"bits/stdc++.h"
#define ll long long
#define vec vector<ll>
#define pb push_back
#define x first
#define y second
#define mk make_pair
#define min(a,b) (a<b?a:b)
#define max(a,b) (a<b?b:a)
#define db(x) cout<<fixed<<setprecision(15)<<#x<<':'<<x<<endl;
#define double long double
using namespace std;
const double eps=1e-9;
const int N=2e6+10,M=2e3+10,mod=1e9+7,inf=1e9;

ll t,cnt,n,m;
vec hd;
bitset<N> vis;//相当于bool vis[N]
vec to,nxt;
vec pre;
//链式前向星建边
void add(ll u,ll v) {
   
  ++cnt;
  to[cnt]=v;
  nxt[cnt]=hd[u];
  hd[u]=cnt;
}
//初始化数组
void init() {
   
  cnt=0;
  hd.assign(n+10,0);
  to.assign(m+10,0);
  nxt.assign(m+10,0);
  pre.assign(n+10,0);
}
//匈牙利最大二分匹配
bool dfs(ll u) {
   
  for(ll i=hd[u]; i; i=nxt[i]) {
   
    if(vis[to[i]]) continue;
    vis[to[i]]=true;
    if(pre[to[i]]==0||dfs(pre[to[i]])) {
   
      pre[to[i]]=u;
      return true;
    }
  }
  return false;
}

int main() {
   
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>t;
  while(t--) {
   
    cin>>n>>m;
    init();
    //建边
    while(m--) {
   
      ll u,v;
      cin>>u>>v;
      add(u,v);
    }
    ll cnt=0;//当前最大匹配数目
    for(ll i=1; i<=n; ++i) {
   
      vis.reset();//相当于memset(vis,0,sizeof vis)
      cnt+=dfs(i);
    }
    cout<<n-cnt<<endl;//n为节点数
  }

  return 0;
}