当前位置:编程学习 > C/C++ >>

hdu1350解题报告-最小边覆盖

题意:一个出租车公司有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;  
}  
个人愚昧观点,欢迎指正与讨论
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,