2319620_re.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 92 行

#include <iostream>
#include <stack>
using namespace std;
struct Vex
{
   int v;
   Vex* next;    
};
struct AdjVex
{
   long value;      //节点的值 
   long maxvalue;   //达到此节点的最大值 
   int indegree;   //入度 
   int outdegree;  //出度 
   Vex* head;    
}adjvex[100001];
int n,m;
long maxvalue;
stack<int> s;
void read() //读入数据 
{
   int i,v1,v2;
   for(i=1;i<=n;++i)
   {
       scanf("%ld",&adjvex[i].value);
       adjvex[i].maxvalue=0;
       adjvex[i].indegree=0;
       adjvex[i].outdegree=0;
       adjvex[i].head=NULL;             
   }
   for(i=1;i<=m;++i)
   {
      scanf("%d%d",&v1,&v2);

      Vex* newVex = new Vex();
      newVex->v=v2;
      newVex->next = adjvex[v1].head;
      adjvex[v1].head = newVex;

      adjvex[v1].outdegree++;
      adjvex[v2].indegree++;             
   }
}
void init() //初始化 
{
    while(!s.empty()) s.pop();
    for(int i=1;i<=n;++i)
    if(adjvex[i].indegree==0)
    {
      adjvex[i].maxvalue+=adjvex[i].value;                       
      s.push(i);
    }
    maxvalue=0; 
}
void calc() //计算最大值 
{ 
    while(!s.empty())
    {         
       int v = s.top();
       s.pop();
       if(adjvex[v].outdegree==0) //此点为终点,计算可能的最大值 
       {
          if(adjvex[v].maxvalue > maxvalue)
          maxvalue = adjvex[v].maxvalue;                       
          continue;                       
       }
       Vex* tVex = adjvex[v].head;
       while(tVex!=NULL)
       {
          adjvex[tVex->v].indegree--;
          if(adjvex[v].maxvalue > adjvex[tVex->v].maxvalue)
          adjvex[tVex->v].maxvalue=adjvex[v].maxvalue;
          if(adjvex[tVex->v].indegree==0)
          {
              adjvex[tVex->v].maxvalue+=adjvex[tVex->v].value; 
              s.push(tVex->v);                          
          }
          tVex = tVex->next;             
       }                 
    }
}
int main()
{
    while(scanf("%d%d",&n ,&m))
    {
       read();
       init();
       calc();
       printf("%ld\n",maxvalue);             
    }
    return 0;
}