HDU OJ 1350 Taxi Cab Scheme 【二分图匹配之最小路径覆盖】
原题连接：点击打开链接
题意：……
思路：二分匹配的最小路径覆盖；在一个有向图无环图里面，寻找最少的路径去覆盖所有的节点，每个节点仅能覆盖一次。
用尽量少的不相交简单路径覆盖有向无环(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m
记住一个重要的结论： DAC图的最小路径覆盖数=节点数(n)-最大匹配数
代码：
#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<cmath>#include<iostream>#include<algorithm>using namespace std;vector<int>V[1000];int link[1000],use[1000];void init(int n){ int i; for(i=0;i<=n;i++) V[i].clear();}bool Dfs(int v){ int i,j,k; for(i=0;i<V[v].size();i++) { k=V[v][i]; if(!use[k]) { use[k]=1; if(!link[k]||Dfs(link[k])) { link[k]=v; return true; } } } return false;}struct hh{ int x; int y; int x1,x2,y1,y2;}map[1000];int MaxMatch(int n){ int i,j,ans=0; memset(link,0,sizeof(link)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(Dfs(i)) ans++; } return ans;}int Find(int i,int j,int x,int y){ return abs(i-j)+abs(x-y);}int main(){ int i,j,n,m,k,t; scanf("%d",&t); while(t--) { int x1,y1,x2,y2; scanf("%d",&n); init(n); for(i=1;i<=n;i++) { scanf("%d:%d %d%d%d%d",&m,&k,&map[i].x1,&map[i].y1,&map[i].x2,&map[i].y2); map[i].x=m*60+k; map[i].y=map[i].x+Find(map[i].x1,map[i].x2,map[i].y1,map[i].y2); } for(i=1;i<n;i++) { for(j=i+1;j<=n;j++) if(map[i].y+Find(map[i].x2,map[j].x1,map[i].y2,map[j].y1)<map[j].x) V[i].push_back(j); } int ans=MaxMatch(n); printf("%d\n",n-ans); }}