題意：一個出租車公司有M個預約，每個預約的信息占據一行：(如下例) 08:23 a b c d (a,b)表示這個預約的起點，(c,d)表示這個任務的終點，前面的時間便是開始的時間，那這個任務結束的時間是|a-c|+|b-d| + 開始的時間，那麼對於這M個預約，問最少派多少輛車就可以全部完成？ 分析：開始我想到的是貪心算法中的時間調度問題，但是後面發現錯啦，這裡我們應該是用到二分匹配的最小邊覆蓋，對於最小邊覆蓋有如下： 最小路徑覆蓋=|P|－最大匹配數(|P|為定點數) 其中最大匹配數的求法是把P中的每個頂點pi分成兩個頂點pi'與pj''，如果在p中存在一條pi到pj的邊，那麼在二分圖P'中就有一條連接pi'與pj''的無向邊；這裡pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊； 對於公式：最小路徑覆蓋=|P|－最大匹配數；可以這麼來理解； 如果匹配數為零，那麼P中不存在有向邊，於是顯然有： 最小路徑覆蓋=|P|－最大匹配數=|P|－0=|P|；即P的最小路徑覆蓋數為|P|； P'中不在於匹配邊時，路徑覆蓋數為|P|； 如果在P'中增加一條匹配邊pi'－－>pj''，那麼在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說pi與pj 在一條路徑上，於是路徑覆蓋數就可以減少一個； 那麼可以這樣解決： 我們把所有的任務看成點，那麼如果完成第 i 個任務還能完成第 j 個任務，我們就加一條邊 i-->j，那麼有一個地方值得注意的是：在計算完成i 能否完成j的時候，我們應該是這樣的判斷條件： [cpp] if(node[i].st >= node[j].end + 1+ abs(node[i].a-node[j].c) + abs(node[i].b-node[j].d) ) { add(i,j); } 對於判斷條件解釋為：完成第 i 個任務，我們所在地點是 (node[i].c,node[i].d)這個地點，那麼我們到達 j 任務的起點處的時間為： [cpp] abs(node[i].a-node[j].c) + abs(node[i].b-node[j].d) 那麼整個題目就分析完畢,上馬： [cpp] // 265MS 996K #include<stdio.h> #include<math.h> #include<string.h> #define MAX 505 int N; struct Node { int st,end; int a,b,c,d; }node[MAX]; struct Edge { int to,nxet; }edge[MAX*MAX]; int head[MAX],tol; void add(int a,int b) { edge[tol].to = b; edge[tol].nxet = head[a]; head[a] = tol ++; } int link[MAX],vis[MAX]; bool dfs(int u) { for(int j = head[u]; j != -1; j=edge[j].nxet) { int v = edge[j].to; if(vis[v]) continue; vis[v] = true; if( link[v] == -1 || dfs(link[v])) { link[v] = u;return true; } } return false; } int match() { int ans=0; memset(link,-1,sizeof(link)); for(int i = 1; i <= N; i ++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } return ans; } int main () { int T; int h,m; scanf("%d",&T); while(T -- ) { tol = 0; memset(head,-1,sizeof(head)); scanf("%d",&N); for(int i = 1; i <= N; i ++) { scanf("%d:%d",&h,&m); scanf("%d%d%d%d",&node[i].a,&node[i].b,&node[i].c,&node[i].d); node[i].st = h*60+m; node[i].end = node[i].st+abs(node[i].a-node[i].c)+abs(node[i].b-node[i].d); for(int j = i-1; j > 0 ; j --) { if(node[i].st >= node[j].end + 1+ abs(node[i].a-node[j].c) + abs(node[i].b-node[j].d) ) { add(i,j); } } } printf("%d\n",N-match()); } return 0; } 個人愚昧觀點，歡迎指正與討論
