浙大数据结构：08-图8 How Long Does It Take

这道题算是较为简单的拓扑排序题，难度不大
机翻

1、条件准备

n,m为n个结点，m条边。
tim数组存到该结点完成的最早时间，会一点点更新
graph存有向边的时间
indegree数组存每个结点的入度

#include <iostream>
#include <vector>
#include<string.h>
using namespace std;
#define endl '\n'

int n,m;
int tim[105];
int graph[105][105];
int indegree[105];

2、主函数

初始化graph为-1，表示没有路径。
输入有向边的数据，存到graph数组中，更新入度
最后进行拓扑排序即可

int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
memset(graph,-1,sizeof(graph));
while(m--)
{
  int s,e,l;
  cin>>s>>e>>l;
  indegree[e]++;
  graph[s][e]=l;
}
tuopu();
  return 0;
}

3、tuopu函数

还是用数组模拟队列存储入度为0的结点。
先遍历一遍把入度为0的结点加入队列
遍历队列，取队头元素，看它到其它结点有没有路径，
有的话更新tim，可达结点的tim变为当前结点的完成时间和本身的较大值，–入度，如果为0就加入队列。
最后如果入队的元素不为结点数量输出Impossible
否则遍历一遍timm数组，输出最大值

void tuopu()
{
  int q[105];int hh=0,tt=-1;//数组模拟队列
  for(int i=0;i<n;i++)
  if(indegree[i]==0)q[++tt]=i;

  while(hh<=tt)
  {
    int cur=q[hh++];
    for(int i=0;i<n;i++)
    {
      if(graph[cur][i]<0)continue;
      tim[i]=max(tim[i],tim[cur]+graph[cur][i]);
      if(--indegree[i]==0)q[++tt]=i;
    }
  }
  int answer=0;
  if(tt!=n-1)
  {
    cout<<"Impossible";return ;
  }
  for(int i=0;i<n;i++)
   answer=max(answer,tim[i]);
   cout<<answer;
}

4、总结

这道题算是拓扑排序较易题，难度不大
完整代码如下

#include <iostream>
#include <vector>
#include<string.h>
using namespace std;
#define endl '\n'

int n,m;
int tim[105];
int graph[105][105];
int indegree[105];
void tuopu()
{
  int q[105];int hh=0,tt=-1;//数组模拟队列
  for(int i=0;i<n;i++)
  if(indegree[i]==0)q[++tt]=i;

  while(hh<=tt)
  {
    int cur=q[hh++];
    for(int i=0;i<n;i++)
    {
      if(graph[cur][i]<0)continue;
      tim[i]=max(tim[i],tim[cur]+graph[cur][i]);
      if(--indegree[i]==0)q[++tt]=i;
    }
  }
  int answer=0;
  if(tt!=n-1)
  {
    cout<<"Impossible";return ;
  }
  for(int i=0;i<n;i++)
   answer=max(answer,tim[i]);
   cout<<answer;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
memset(graph,-1,sizeof(graph));
while(m--)
{
  int s,e,l;
  cin>>s>>e>>l;
  indegree[e]++;
  graph[s][e]=l;
}
tuopu();
  return 0;
}

原文地址：https://blog.csdn.net/qq_74924951/article/details/142792448

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！