首页 > 代码库 > 06-5. 关键活动（30） 关键路径 和输出关键路径

06-5. 关键活动（30） 关键路径 和输出关键路径

2024-10-29 06:23:38   206人阅读

06-5. 关键活动（30）

时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard

本实验项目是实验项目6-06的深化。任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此延误，这种任务就叫“关键活动”。

请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计算完成整个工程项目需要的最短时间，并输出所有的关键活动。

输入格式说明：

输入第1行给出两个正整数N(<=100)和M，其中N是任务交接点（即衔接相互依赖的两个子任务的节点，例如：若任务2要在任务1完成后才开始，则两任务之间必有一个交接点）的数量，交接点按1~N编号，M是子任务的数量，依次编号为1~M。随后M行，每行给出了3个正整数，分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间，整数间用空格分隔。

输出格式说明：

如果任务调度不可行，则输出0；否则第1行输出完成整个工程项目需要的时间，第2行开始输出所有关键活动，每个关键活动占一行，按格式“V->W”输出，其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是：任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序相反。如下面测试用例2中，任务<5,7>先于任务<5,8>输入，而作为关键活动输出时则次序相反。

样例输入与输出：

序号输入输出
1
7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

17
1->2
2->4
4->6
6->7
2
9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4

18
1->2
2->5
5->8
5->7
7->9
8->9
3
11 14
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2
8 3 7
9 3 7
9 10 6
4 10 2
10 6 5
6 11 4

21
3->4
4->10
6->11
8->3
9->3
10->6
4
4 5
1 2 4
2 3 5
3 4 6
4 2 3
4 1 2

0

提交代码


求关键路径 其实还是挺简单的  就是利用突破排序

但是 这个奇怪的输出  关键的路径 有点头疼  自己的代码写的是相当的乱 还好一次过了。。。

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lson rt<<1,l,MID
#define rson rt<<1|1,MID+1,r
//#define lson root<<1
//#define rson root<<1|1
#define MID ((l+r)>>1)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=3005;
const int base=1000;
const int inf=9999999999;
const double eps=1e-5;
int n,m;
struct node
{
    int to,cost;
};
vector<node> G[maxn];//图的邻接表
vector<node> g[maxn];//图的逆邻接表
int d[maxn];//每个点的入度

int earlist[maxn];//每个点最早的发生时间
int last[maxn];//每个点的最迟发生时间
stack<int> ss;//拓扑排序的 逆序

bool tupo_sort()
{
    stack<int> s;
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)s.push(i);
    }
    int cnt=0;
    while(!s.empty())
    {
        int m=s.top();
        ss.push(m);
        cnt++;s.pop();
        for(int i=0;i<G[m].size();i++)
        {
            node tmp=G[m][i];
            if(--d[tmp.to]==0)s.push(tmp.to);
            if(earlist[m]+tmp.cost>earlist[tmp.to])
            {
                earlist[tmp.to]=earlist[m]+tmp.cost;
            }
        }
    }
    if(cnt<n)return false;
    return true;
}

void solve_last()//求最迟的发生时间
{
    int i;
    fill(last+1,last+n+1,*max_element(earlist+1,earlist+n+1));
    while(!ss.empty())
    {
        int m=ss.top();
        ss.pop();
        for(i=0;i<g[m].size();i++)
        {
            node k=g[m][i];
            if(last[m]-k.cost<last[k.to])
            {
                last[k.to]=last[m]-k.cost;
            }
        }
    }
}

struct acm//记录边  我这里是因为对付那个奇怪的输出的顺序
{
    int a,b;
    int order;
    int cost;
}p[maxn],pp[maxn];

struct key//关键的节点  由关键节点找关键的边
{
    int node;
    int time;
    friend bool operator<(key a,key b)
    {
        return a.time<b.time;
    }
}a[maxn];


bool cmp(acm a,acm b)//对付 输出的排序
{
   if(a.a!=b.a)
       return a.a<b.a;
    else
        return a.order>b.order;
}
int num=0;
void find(key a,key b)//查找关键的边
{
    for(int i=0;i<m;i++)
    {
        if(p[i].a==a.node&&p[i].b==b.node&&last[p[i].a]+p[i].cost==last[p[i].b])
        {
            pp[num++]=p[i];
        }
    }
}
int main()
{
    int i,j,k,t;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        node e;
        int s;
        cin>>s>>e.to>>e.cost;
        p[i].a=s;
        p[i].b=e.to;
        p[i].order=i;
        p[i].cost=e.cost;
        G[s].push_back(e);
        node kk;
        kk.to=s;
        kk.cost=e.cost;
        g[e.to].push_back(kk);
        d[e.to]++;
    }
    if(!tupo_sort())
        puts("0");
    else
    {
        solve_last();
        printf("%d\n",*max_element(earlist+1,earlist+n+1));
        for(i=1,j=0;i<=n;i++)
        {
            if(last[i]==earlist[i])
            {
                a[j].node=i;
                a[j++].time=last[i];
            }
        }
        sort(a,a+j);
        for(i=0;i<j;i++)
        {
            for(k=i+1;k<j;k++)
                 find(a[i],a[k]);
        }
        sort(pp,pp+num,cmp);
        for(j=0;j<num;j++)
            printf("%d->%d\n",pp[j].a,pp[j].b);
    }
    return 0;
}


06-5. 关键活动（30） 关键路径 和输出关键路径


联系
我们