首页 > ACM题库 > HDU-杭电 > hdu 2324 Catch the Bus!-最短路径-[解题报告]hoj
2014
01-05

hdu 2324 Catch the Bus!-最短路径-[解题报告]hoj

Catch the Bus!

问题描述 :

ACM needs to deliver marketing materials to one of their clients. Both ACM and the client employ students to make such deliveries. And these students use public buses to move throughout the city. Sometimes, it is necessary to pass the materials as fast as possible.

You are given bus timetables and your task is to find the fastest way for two students to meet at some stop. The place of the meeting is not important, they only need to meet as early as possible.

Students may change between any two bus routes at stops that are common for both routes. At least two minutes are needed for every such change. No additional time is necessary to get on the first bus or to meet the other student in the target stop.

输入:

The input contains a sequence of several scenarios, the sequence is terminated by a line containing negative number.

Each scenario begins with a non-negative integer L, the number of bus routes that operate in the city (L ≤ 1000). Every route is then described by two lines. The first line contains names of stops that the bus runs through. Between each consecutive stops, there is a non-negative integer specifying the number of minutes required to travel between these stops with the given bus. The last stop is followed by a negative number.

The second line of each bus route contains non-negative integers separated with spaces. The first integer H gives the number of buses that depart the initial stop in every hour (H ≤ 60). The remaining H integers are always distinct and sorted ascendingly, they list the minutes of departure (between 0 and 59). The timetable repeats every hour. For example, if the second line says “2 00 30”, the buses leave the initial stop at 12:00, 12:30, 13:00, 13:30, 14:00, etc.

After the description of routes, there are two lines that specify the initial position of students. Each of them will contain time in a standard 24-hour format (one or two digits for hours, colon, and two digits for minutes) and a stop name.

All numbers, times, and stop names will be separated with a single space. Stop names are case-sensitive and may be composed only from lower-case and upper-case letters, their length will not exceed 30 characters. The total number of stops will be at most 1000, the number of stops on a single route will not exceed 100. The time between any two consecutive stops will be at most one hour. The routes are considered one-way, if they operate in both directions, they will be given as two separate routes. A route may run through the same stop several times.

输出:

The input contains a sequence of several scenarios, the sequence is terminated by a line containing negative number.

Each scenario begins with a non-negative integer L, the number of bus routes that operate in the city (L ≤ 1000). Every route is then described by two lines. The first line contains names of stops that the bus runs through. Between each consecutive stops, there is a non-negative integer specifying the number of minutes required to travel between these stops with the given bus. The last stop is followed by a negative number.

The second line of each bus route contains non-negative integers separated with spaces. The first integer H gives the number of buses that depart the initial stop in every hour (H ≤ 60). The remaining H integers are always distinct and sorted ascendingly, they list the minutes of departure (between 0 and 59). The timetable repeats every hour. For example, if the second line says “2 00 30”, the buses leave the initial stop at 12:00, 12:30, 13:00, 13:30, 14:00, etc.

After the description of routes, there are two lines that specify the initial position of students. Each of them will contain time in a standard 24-hour format (one or two digits for hours, colon, and two digits for minutes) and a stop name.

All numbers, times, and stop names will be separated with a single space. Stop names are case-sensitive and may be composed only from lower-case and upper-case letters, their length will not exceed 30 characters. The total number of stops will be at most 1000, the number of stops on a single route will not exceed 100. The time between any two consecutive stops will be at most one hour. The routes are considered one-way, if they operate in both directions, they will be given as two separate routes. A route may run through the same stop several times.

样例输入:

4
Hradcanska 2 Malostranska 2 Staromestska 2 Mustek 1 Muzeum -1
10 00 06 12 18 24 30 36 42 48 54
Muzeum 1 Mustek 2 Staromestska 2 Malostranska 2 Hradcanska -1
10 03 09 15 21 27 33 39 45 51 57
Andel 2 Karlovo 1 Narodni 2 Mustek 2 Florenc -1
6 00 10 20 30 40 50
Florenc 2 Mustek 2 Narodni 3 Karlovo 1 Andel -1
6 02 12 22 32 42 52
12:00 Hradcanska
12:11 Andel
1
Hradcanska 2 Malostranska 2 Staromestska 2 Mustek 1 Muzeum 2 Hradcanska -1
10 00 06 12 18 24 30 36 42 48 54
12:00 Mustek
12:00 Andel
-1

样例输出:

12:20
No connection


最小费用最大流 标签: 代码库 分类: xq 2007-10-08 20:42liuctic的代码库,我加的主函数,刚过了joj2324里面的实现依然没看懂,只能是贴上去用。若算最大费用的话只需稍加改动/* Min Cost Max Flow * 最小费用最大流 Algo : 最短路径扩充 + Ford负圈消除 * main()里要做的事: * 1) 定义类MincostGraph 的实例G。 * 2) 给边容量矩阵G.cap[][]赋值,若无边,赋为0 * 3) 给代价矩阵G.cost[]赋值, *    须满足G.cost[i][j]+G.cost[j][i]=0,若无代价,赋为0, * 3) 把顶点的个数赋给G.V。 * 4) 调用G.Maxflow(s, t),返回最大流值。同时由G.flow[][]可知流值分配。 * 5) 调用G.MinCost(), 返回最小费用值,同时由G.flow[][]可知流值分配。 * 注:G.cap会被改变,所以若要知maxflow是否为满流,最好事先确定满流值。 *****************************************************************/const int MaxVertex = 50;#include<queue>using namespace std;class Graph{public:    int cap[MaxVertex][MaxVertex];      //边容量矩阵,若无边,则为0    int flow[MaxVertex][MaxVertex];     //流矩阵    int V;                              //图结点个数    int maxflow;                        //最大流值    int MaxFlow(int ss, int tt);        //求图中最大流,并返回流值protected://private:    int s, t;                           //源点,汇点    int father[MaxVertex];              //记录增广路径和负环用    bool pfs();    void augment(int, int);};int Graph::MaxFlow(int ss, int tt){    s = ss, t = tt;    memset(flow, 0, sizeof(flow));    maxflow = 0;    while(pfs())        augment(s, t);    return maxflow;}bool Graph::pfs(){    int v, j; queue<int> myque;    memset(father, 0xff, sizeof(int)*V);    while(!myque.empty()) myque.pop();    father[s] = s;    myque.push(s);    while(!myque.empty())    {        v = myque.front(); myque.pop();        for(j = 0; j < V; ++j)            if(cap[v][j]>0 && father[j]<0)            {                father[j] = v;                if(j == t)                    return 1;                myque.push(j);            }    }    return 0;}void Graph::augment(int ss, int tt){    int tiny(INT_MAX);    int v(tt), w(father[v]);    do{        if(tiny > cap[w][v]) tiny = cap[w][v];        v = w, w = father[v];    }while(v != ss);    v = tt, w = father[v];    do{        flow[w][v] += tiny;        flow[v][w] -= tiny;        cap[w][v] -= tiny;        cap[v][w] += tiny;        v = w, w = father[v];    }while(v != ss);    maxflow += tiny;}class MincostGraph : public Graph{public:    int cost[MaxVertex][MaxVertex];     //成本矩阵, 对称位置元素之和为0    int mincost;    int MinCost();protected:struct EdgeNode{   int v, w;   EdgeNode *next, *front;   EdgeNode(int vv=0, int ww=0, EdgeNode *nn=NULL, EdgeNode *ff=NULL) :      v(vv), w(ww), next(nn), front(ff) {}};   EdgeNode * lst;   EdgeNode * p2edge[MaxVertex][MaxVertex];   int negcyc();   int findcyc();   void Augment(int, int);   EdgeNode* Insert(EdgeNode *);   void Delete(EdgeNode *);   void Destroy();};void MincostGraph::Destroy(){   EdgeNode *p, *q;   for(p = lst; p; p = q)   {      q = p->next;     delete p;   }   lst = NULL;}int MincostGraph::MinCost(){ mincost = 0; int x, i, j; lst = NULL; for(i = 0; i < V; ++i) for(j = 0; j < V; ++j)   if(cap[i][j] > 0)    p2edge[i][j] = Insert(new EdgeNode(i, j));   else p2edge[i][j] = 0; while((x=negcyc())!=-1)   Augment(x, x); for(i = 0; i < V; ++i)   for(j = 0; j < V; ++j)    if(flow[i][j]>0) mincost += flow[i][j]*cost[i][j]; Destroy(); return mincost;}MincostGraph:: EdgeNode* MincostGraph::Insert(EdgeNode * p){ if(lst) p->next = lst, lst->front = p; lst = p; return p;}void MincostGraph::Delete(EdgeNode *p){   if(!p) return;   if(p == lst)   {      lst = p->next;      lst->front = NULL;      delete p;   }else   {      p->front->next = p->next;      p->next->front = p->front;      delete p;   }}void MincostGraph::Augment(int ss, int tt){    int tiny(INT_MAX);    int v(tt), w(father[v]);    do{        if(tiny > cap[w][v]) tiny = cap[w][v];        v = w, w = father[v];    }while(v != ss);    v = tt, w = father[v];    do{       flow[w][v] += tiny;        flow[v][w] -= tiny;        cap[w][v] -= tiny;      if(cap[w][v] == 0)      {         Delete(p2edge[w][v]);         p2edge[w][v] = 0;      }        cap[v][w] += tiny;      if(cap[v][w] == tiny)         p2edge[v][w] = Insert(new EdgeNode(v, w));        v = w, w = father[v];    }while(v != ss);    maxflow += tiny;}int MincostGraph::negcyc(){    int k, i, j;    int D[MaxVertex] = {0};    bool flag;    D[s] = 0;    memset(father, 0xff, sizeof(int) * V);   EdgeNode *itr;    for(k = 0; k <= V; ++k)    {        flag = 0;      for(itr = lst; itr; itr = itr->next)      {         i = itr->v, j = itr->w;            if(D[j] > D[i]+cost[i][j])            {                D[j] = D[i] + cost[i][j];                father[j] = i; flag = 1;            if(k == V)               return findcyc();            }      }        if(!flag) break;    }   return -1;}int MincostGraph::findcyc(){   int used[MaxVertex] = {0};   int i, j, k = 0;   for(i = 0; i < V; ++i)   {      if(used[i]) continue;      ++ k;      for(j = i; j >= 0; j = father[j])      {         if(used[j] == k)            return j;         used[j] = k;      }   }}int main(){ int i,j,n; while(scanf("%d",&n)!=EOF){   MincostGraph G;   G.V = 2*n+2;//////////////////////////////////////////////   for(i=0;i<G.V;++i)    for(j=0;j<G.V;++j){     G.cap[i][j]=0;     G.cost[i][j]=0;    }   for(i=1;i<=n;++i)    G.cap[0][i]=1;   for(i=n+1;i<=2*n;++i)    G.cap[i][2*n+1]=1;   for(i=1;i<=n;++i)    for(j=n+1;j<=2*n;++j)     G.cap[i][j]=1;//////////////////////////////////////////////   for(i=1;i<=n;++i)    for(j=n+1;j<=2*n;++j){     scanf("%d",&G.cost[i][j]);     G.cost[j][i]=-G.cost[i][j];    }   G.MaxFlow(0,2*n+1);   int value=G.MinCost();   printf("%d\n",value); } return 0;}
解题参考:http://hi.baidu.com/sncmcjzbjubnpzq/item/6ff54719ceefb203b98a1a81


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”