hihoCoder 1394 : 网络流四·最小路径覆盖
题目链接：https://hihocoder.com/problemset/problem/1394
题目说是网络流，但是其实就是求有向无环图的最小路径覆盖。
不会网络流，只好用二分匹配了。
把每个点，拆成入点，和出点，一条路径就是在B块一定是匹配了的，也就是说要求的最小路径覆盖，就是那些没有匹配的点，经过最大匹配后，B块剩下没有匹配的点是最少的，也就对应了最小需要的路径数。
所以： 最小路径覆盖 = N -最大匹配
//Asimple #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define INF 0xffffff #define CLS(a, v) memset(a, v, sizeof(a)) #define debug(a) cout<<#a<<" = "<<a<<endl typedef long long ll ; const int maxn = 1005; //const int dx[]= {1,-1,0,0}, dy[]= {0,0,1,-1}; int dx[]={0,0,-1,-1,-1,1,1,1}; int dy[]={-1,1,-1,0,1,-1,0,1}; ll n, T, num, cnt, x, y, t, m; //ll dp[maxn][maxn]; bool Map[maxn][maxn]; bool vis[maxn]; int link[maxn], in[maxn], out[maxn]; bool dfs(int x) { for(int i=1; i<=n; i++) { if( !vis[i] && Map[x][i] ) { vis[i] = true; if( link[i]==-1 || dfs(link[i])) { link[i] = x; return true; } } } return false; } void input() { ios_base::sync_with_stdio(false); while( cin >> n >> m ) { CLS(Map, false); CLS(link, -1); while( m -- ) { cin >> x >> y; Map[x][y] = true; } cnt = 0; for(int i=1; i<=n; i++) { CLS(vis, false); if( dfs(i) ) cnt ++; } cout << n-cnt << endl; } } int main() { input(); return 0; }
