传送门：hdu1151 Air Raid
题意：在一个城镇，有m个路口，和n条路，这些路都是单向的，而且路不会形成环，现在要弄一些伞兵去巡查这个城镇，伞兵只能沿着路的方向走，问最少需要多少伞兵才能把所有的路口搜一遍。
分析：有向无环图不相交最小路径覆盖数，等于节点数减去二分图的最大匹配数，对于每条弧，弧头作为X部，弧尾作为Y部。最后在求得最大匹配的基础上，没有被匹配的Y部的点就是简单路径的起点。其个数刚好就是节点数减去二分图的最大匹配数。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 200 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; int match[N],vis[N],n,m; vector<int>g[N]; int dfs(int u) {for(int i=0,sz=g[u].size();i<sz;i++){int v=g[u][i];if(!vis[v]){vis[v]=1;if(match[v]==-1||dfs(match[v])){match[v]=u;return 1;}}}return 0; } int hungary() {FILL(match,-1);int ans=0;for(int i=1;i<=n;i++){FILL(vis,0);if(dfs(i))ans++;}return ans; }int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);}int res=hungary();printf("%d\n",n-res);} }
传送门：poj2594 Treasure Exploration
题意：在一个有向图上，至少放多少个机器人可以遍历整个图(每个顶点可以重复遍历)。
分析：有向无环图可相交最小路径覆盖数，得先跑一遍Floyd，然后再进行最大匹配。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 510 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; int match[N],vis[N],n,m; int g[N][N],mat[N][N]; char s[N][N]; int dfs(int u) {for(int i=1;i<=n;i++){if(!vis[i]&&g[u][i]){vis[i]=1;if(match[i]==-1||dfs(match[i])){match[i]=u;return 1;}}}return 0; } int hungary() {FILL(match,-1);int ans=0;for(int i=1;i<=n;i++){FILL(vis,0);if(dfs(i))ans++;}return ans; } void floyd() {for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(g[i][k]&&g[k][j])g[i][j]=1;} } int main() {while(scanf("%d%d",&n,&m)>0){if(n+m==0)break;FILL(g,0);while(m--){int u,v;scanf("%d%d",&u,&v);g[u][v]=1;}floyd();int res=hungary();printf("%d\n",n-res);} }