数据结构与算法题目集(中文) - 7-11 关键活动(30 分)

简介: 数据结构与算法题目集(中文) - 7-11 关键活动(30 分)

题目链接:点击打开链接

 

题目大意:

解题思路


关键路径(最长路径):AOE网中,顶点被称为事件,而边(或弧)才是活动的描述,边的权值代表活动所花费的时间,因此,事件就是一个活动结束,另一个活动开始的标志,那么要完成整项工程就需要将前面的活动全部完成,所以选最长的路径作为关键路径才能确保工程被完成。


关键路径,注意最后的输出规则。

Ps:关键路径的注意:

* 关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素。

* 关键路径并不唯一。对于有几条关键路径的网,只提高一条关键路径上的关键活动并不能缩短整个工程的工期,只有加快那些包括所有关键路径上的关键活动才能达到缩短工期的目的。



image.png


AC 代码1(传统版)


#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=200;
int n,m,rs,ans;
int dfn[maxn][maxn], dis[maxn][maxn], mp[maxn][maxn]; // 这里 mp[][] 可以用 dfn[][] 替代
int vl[maxn], ve[maxn], in[maxn], out[maxn]; // ve:vearly  vl:vlate
vector<int> ge[maxn], gl[maxn];
struct node
{
    int s,e,dfn;
}nds[maxn];
void init()
{
    rs=ans=0;
    mem(in,0); mem(out,0); mem(mp,0); mem(vl,INF); mem(ve,0);
    for(int i=0;i<maxn;i++) ge[i].clear(), gl[i].clear();
}
int cmp(node n1,node n2)
{
    if(n1.s==n2.s) return n1.dfn>n2.dfn;
    return n1.s<n2.s;
}
void bfs_e()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!in[i]) q.push(i), ans++;
    while(!q.empty())
    {
        int cur=q.front(); q.pop();
        for(int i=0;i<ge[cur].size();i++)
        {
            int v=ge[cur][i];
            ve[v]=max(ve[v],ve[cur]+dis[cur][v]);
            in[v]--;
            if(!in[v])
            {
                q.push(v);
                ans++;
            }
        }
    }
}
void bfs_l()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!out[i]) q.push(i), vl[i]=rs; // 确保了非最大值的关键路径的除去(技巧)
    while(!q.empty())
    {
        int cur=q.front(); q.pop();
        for(int i=0;i<gl[cur].size();i++)
        {
            int v=gl[cur][i];
            vl[v]=min(vl[v],vl[cur]-dis[cur][v]);
            out[v]--;
            if(!out[v]) q.push(v);
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        int s,e,w;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&s,&e,&w);
            ge[s].push_back(e);
            gl[e].push_back(s);
            mp[s][e]=1;
            dis[s][e]=dis[e][s]=w;
            in[e]++, out[s]++;
            dfn[s][e]=i; // 编号第i条数据,为了解决下面反过来输出
        }
        bfs_e();
        if(ans!=n) puts("0");
        else
        {
            for(int i=1;i<=n;i++)
                if(!out[i]) rs=max(rs,ve[i]); // 为了破除多个关键路径取最大(确保)的关键路径
            bfs_l();
            printf("%d\n",rs);
            int k=0;
            for(int i=1;i<=n;i++)
            {
                if(vl[i]==ve[i])
                {
                    for(int j=1;j<=n;j++)
                    {
                        // 这里 mp[][] 可以用 dfn[][] 替代  
                        // vl[j]-dis[i][j]==ve[i] 作用?
                        // 如图所示,此时,1、2、3都是关键结点,但是1->3并不是关键活动,所以如果去了这一条条件代码则是求关键结点;而求关键活动必须要加上这一条
                        if(dfn[i][j] && vl[j]==ve[j] && vl[j]-dis[i][j]==ve[i])
                            nds[k].s=i, nds[k].e=j, nds[k++].dfn=dfn[i][j];
                    }
                }
            }
            sort(nds,nds+k,cmp);
            for(int i=0;i<k;i++)
                printf("%d->%d\n",nds[i].s,nds[i].e);
        }
    }
    return 0;
}

AC 代码2(最短路径版)


#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a)
#define ssclr(ss) ss.clear(), ss.str("")
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
const int maxm=1e4+10, maxn=110;
struct node
{
    int u,v,w;
}es[maxm];
struct nd
{
    int u,v;
}nds[maxm];
int n,m,l,dismax=0;
int dis[maxn], in[maxn], out[maxn], g[maxn][maxn], vis[maxn][maxn];
vector<int> pre[maxn], dv;
int dijkstra()
{
    int f,u,v,w;
    for(int i=1;i<=n;i++) // 最多需要(n-1)条边更新,所以i不能从2开始,要从1开始,多检测一次才知道是否有环
    {
        f=0;
        for(int j=1;j<=m;j++)
        {
            u=es[j].u, v=es[j].v, w=es[j].w;
            if(dis[u]+w>dis[v])
            {
                dis[v]=dis[u]+w;
                dismax=max(dis[v],dismax);
                pre[v].clear();
                pre[v].push_back(u);
                f=1;
            }
            else if(dis[u]+w==dis[v] && find(pre[v].begin(),pre[v].end(),u)==pre[v].end())
                pre[v].push_back(u);
        }
        if(!f) return 1;
    }
    return 0;
}
int cmp(nd n1, nd n2)
{
    if(n1.u==n2.u)
        return g[n1.u][n1.v]>g[n2.u][n2.v];
    return n1.u<n2.u;
}
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        s=q.front(); q.pop();
        for(int i=0;i<pre[s].size();i++)
        {
            if(vis[pre[s][i]][s]==0) // 多个出口存在,避免有重复的边
            {
                vis[pre[s][i]][s]=1;
                nds[l].u=pre[s][i], nds[l].v=s;
                q.push(nds[l].u);
                l++;
            }
        }
    }
}
int main()
{
    int u,v,w,s,d;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        es[i].u=u, es[i].v=v, es[i].w=w;
        g[u][v]=i;
        in[v]++, out[u]++;
    }
    for(int i=1;i<=n;i++)
    {
//        if(in[i]==0) s=i;
        if(out[i]==0) dv.push_back(i); // 可能有多个出口存在
    }
    if(dijkstra())
    {
        printf("%d\n",dismax);
        for(int i=0;i<dv.size();i++)
            if(dismax==dis[dv[i]]) bfs(dv[i]);
        sort(nds,nds+l,cmp);
        for(int i=0;i<l;i++)
            printf("%d->%d\n",nds[i].u,nds[i].v);
    }
    else puts("0");
    return 0;
}
目录
相关文章
|
5月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
20天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
13 0
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
5月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表