How Long Does It Take

2022-11-10 07:37:16

好长时间没写博客了，真心惭愧啊！

废话少说，原题链接：https://pta.patest.cn/pta/test/1342/exam/4/question/24939

题目如下：

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers NNN (≤100\le 100≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1N-1N−1), and MMM, the number of activities. Then MMM lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

Impossible

这道题不难，本质上就是一道拓扑排序的问题，只不过增加了权重，成为了一道关键路径的问题，此类拓扑排序问题的核心思想就是先在图中找到入度为0的点，对其进行操作，然后将于该点相邻的边删除，继续对剩下的图重复这一过程。为了提高算法的效率，陈越老师讲过可以在每次删除边时，检查其它顶点是否入度为0，如果为0就将其放在一个容器里面（我用的是队列），下次用的时候就可以直接从容器里面取出。拓扑排序一般是较为稀疏的图，应该用邻接表存储图合适，但我为了写起来简单，就用了邻接矩阵。以下是我的代码：

 #include<stdio.h>

 #include<stdlib.h>

 #include<stdbool.h>

 #define Max 105

 #define INFINITY 65535

 typedef struct QNode{

     int front,rear;

     int Data[Max];

     int Maxsize;

 }Quenue;

 Quenue *CreateQ(int N)

 {

     Quenue *Q=(Quenue *)malloc(sizeof(struct QNode));

     Q->front=Q->rear=;

     Q->Maxsize=N+;

     return Q;

 }

 bool IsFull(Quenue *Q)

 {

     return ((Q->front+)%Q->Maxsize == Q->rear);

 }

 void Push(Quenue *Q,int v)

 {

     if (!IsFull(Q))

     {

         Q->front=(Q->front+)%Q->Maxsize;

         Q->Data[Q->front]=v;

     }

 }

 bool IsEmpty(Quenue *Q)

 {

     return (Q->front==Q->rear);

 }

 int Pop(Quenue *Q)

 {

     if (!IsEmpty(Q))

     {

         Q->rear=(Q->rear+)%Q->Maxsize;

         return (Q->Data[Q->rear]);

     }

 }

 int G[Max][Max];

 int N,M;

 void TopSort()

 {

     int Indegree[Max]={};

     int v,w,weight,cnt=;

     int endcnt=; //有多个终点是，用来记录是否为终点的变量

     int dist[Max]={};

     Quenue *Q=CreateQ(N);

    /* 初始化各顶点的入度值 */

     for (v=;v<N;v++)

     {

         for (w=;w<N;w++)

         {

             if ( G[w][v]<INFINITY)Indegree[v]++;

         }

     }

     /*入度为0的顶点入队 */

     for (v=;v<N;v++)

     {

         if (Indegree[v]==){Push(Q,v);}

     }

     /*拓扑排序*/

     weight=;

     while (!IsEmpty(Q))

     {

         v=Pop(Q);

         cnt++;

         for (w=;w<N;w++)

         {

             if (G[v][w]<INFINITY)

             {

                 if (dist[v]+G[v][w]>dist[w])dist[w]=dist[v]+G[v][w];

                 if (--Indegree[w]==)Push(Q,w);

                 endcnt++;

             }

         }

         if (endcnt==)  //此时v为终点

         {

             if (dist[v]>weight)weight=dist[v];

         }

         endcnt=;

     }

     if (cnt!=N)printf("Impossible");

     else printf("%d",weight);

     return ;

 }

 int main()

 {

     scanf("%d %d",&N, &M);

     int i,j,v,w,weight;

     for (i=;i<N;i++){

     for (j=;j<N;j++){G[i][j]=INFINITY;}}

     for (i=;i<M;i++)

     {

         scanf("%d %d %d",&v, &w, &weight);

         G[v][w]=weight;

     }

     TopSort();

     return ;

 }

随机推荐

WCF Data Service 使用小结（二） —— 使用WCF Data Service 创建OData服务
在上一章中,介绍了如何通过 OData 协议来访问 OData 服务提供的资源.下面来介绍如何创建一个 OData 服务.在这篇文章中,主要说明在.NET的环境下,如何使用 WCF Data Se ...
springMVC之annotation优化
1.在之前配置的spring配置文件中会有这样的代码:  <bean class="org.springframework.web.servle ...
windows下安装nginx (转载自：http&colon;//blog&period;163&period;com/njut&lowbar;wangjian/blog/static/1657964252013327103716818/)
1. 到nginx官网上下载相应的安装包,http://nginx.org/en/download.html:下载进行解压,将解压后的文件放到自己心仪的目录下,我的解压文件放在了d盘根目录下,如下图 ...
c&num; 设置IE浏览器版本运行程序-设置webBrowser对应的IE内核版本来运行
//通常情况下,我们直接调用C#的webBrowser控件,默认的浏览器内核是IE7. 那么如何修改控件调用的默认浏览器版本呢?using System; using System.Collecti ...
HTML中include file的用法
语法  参数 PathType 路径类型路径可为以下某种类型: 文件该文件名是带有 ...
[Cqoi2014]数三角形——组合数
Description: 给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个.下图为4x4的网格上的一个三角形. 注意三角形的三点不能共线. Hint: 1<=m,n<=1000 ...
jquery on事件jquery on实现绑定多个事件
API上jquery on介绍 on(events,[selector],[data],fn) 概述在选择元素上绑定一个或多个事件的事件处理函数. on()方法绑定事件处理程序到当前选定的jQuer ...
Android程序员眼中世界上最遥远的距离
世界上最遥远的距离,是我在if里你在else里,似乎一直相伴又永远分离: 世界上最痴心的等待,是我当case你是switch,或许永远都选不上自己: 世界上最真情的相依,是你在try我在catch. ...
pip 安装指定版本的python包
pip install -v package_name==2.3
unity开发android游戏
环境搭建: Unity+JDK+Android Studio+Android SDK(+NDK) 教程:unity开发android游戏(一)搭建Unity安卓开发环境注意“Build System ...

码农公寓