本文共 1043 字，大约阅读时间需要 3 分钟。
题目大意：
有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。
你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。
像这样建二分图，最后由定理
DAG图的最小路径覆盖数=节点数（n）- 最大匹配数（m）
这样也就只需要求最大匹配数
上诉结论的证明见：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std;15 #define eps 1e-1516 #define MAXN 12517 #define INF 100000000718 #define MAX(a,b) (a > b ? a : b)19 #define MIN(a,b) (a < b ? a : b)20 #define mem(a) memset(a,0,sizeof(a))21 22 bool G[MAXN][MAXN],vis[MAXN];23 int Left[MAXN],N,M,T;24 25 bool DFS(int u)26 {27 for(int v=0;v<=N;v++) if(G[u][v] && !vis[v])28 {29 vis[v] = true;30 if(!Left[v] || DFS(Left[v]))31 {32 Left[v] = u;33 return true;34 }35 }36 return false;37 }38 39 int main()40 {41 while(~scanf("%d", &T))while(T--)42 {43 mem(G); mem(Left);44 scanf("%d%d", &N, &M);45 int x,y;46 for(int i=0;i
转载于:https://www.cnblogs.com/gj-Acit/p/3265087.html
