学步园

题意：给你一些机器指令，某些有先后顺序（若A->B,C->B则必须A、C执行完才能执行B），且有安全距离（若A->B 距离n）那么必须在从A执行算起n时间，才能执行B，一次可以运行多个指令，指令的完成只花费1,最后求执行完所有指令所需的最短的时间。

思想：求到达各点的最大值（所有能到达该点的花费的最大值）的最大值（即所有点的最大值）。

解法：①纯递归搜索：这是最简单直观的做法，从入度为0点开始搜索，记录每点的最大值，最后求所有点的最大值即可。

            ② “最短路算法”求解：你可以直接求所有点的最长路或者是反向建图求最短路 ，最后找最长的或者最短的（注意负数）。

            ③用拓扑排序的思想也可求解。

 这么所方法其实都一样，代码的实现可能与叙述有所不同，但思想绝对一样！

①的代码：

#include <stdio.h>
#include <string.h>

#define N 1002
#define M 10002

int nodev[N];
int nodeu[M],value[M],next[M];
int indegree[N];

void Build_Graph(int m)
{
    int i,v,u,val,ind;

    memset(indegree,0,sizeof(indegree));
    memset(nodev,-1,sizeof(nodev)); ind=0;
    for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&v,&u,&val);
        
        indegree[u]++;
        nodeu[ind]=u;
        value[ind]=val;
        next[ind]=nodev[v];
        nodev[v]=ind;
        ind++;
    }
}

int record[N];
int DFS(int v)
{
    int i,u,val;
    
    if(record[v]!=0)
    {
        return record[v];
    }
    
    for(i=nodev[v];i!=-1;i=next[i])
    {
        u=nodeu[i];
            
        val=DFS(u);
        if(val+value[i]>record[v])
            record[v]=val+value[i];
    }
    return record[v];
}

void solve()
{
    int v,n,m,temp,max;

    while(scanf("%d %d",&n,&m)!=EOF)
    {
        Build_Graph(m);

        memset(record,0,sizeof(record)); max=0;
        for(v=0;v<n;v++)
        {
            if(indegree[v]==0)
            {
                temp=DFS(v);
                if(temp>max) max=temp;
            }
        }
        printf("%d\n",max+1);
    }
}

int main()
{
    solve();
    return 0;
}

②思想的代码：

#include <stdio.h>
#include <string.h>

#define N 1002
#define M 10002
#define MOVE(x) (x=(x+1)%N)
#define MAXVAL 0xfffffff

int S,E; //添加的源点，终点

int nodev[N];
int nodeu[M+N*2],value[M+N*2],next[M+N*2],ind;
void addedge(int v,int u,int val)
{
	nodeu[ind]=u;
	value[ind]=val;
	next[ind]=nodev[v];
	nodev[v]=ind;
	ind++;
}
void Build_Graph(int n,int m)
{
	int i,v,u,val;
	
	memset(nodev,-1,sizeof(nodev)); 
	S=0; E=n+1; ind=0;

	for(i=0;i<m;i++)
	{
		scanf("%d %d %d",&v,&u,&val);
		v++;	u++;	val=-val;
		addedge(u,v,val);
	}
	for(i=1;i<=n;i++)
	{
		addedge(S,i,0);
		addedge(i,E,0);
	}
}

int queue[N],dist[N];
bool flag[N];
void SPFA(int s,int n)
{
	int i,v,u,val;
	int front,rear;

	for(i=1;i<=n+1;i++)	dist[i]=MAXVAL; 
	dist[s]=0;//当S加入队列时，一定有负环，但有负环，不一定是S一定要进队列!!
	memset(flag,false,sizeof(flag));
	front=-1;	rear=-1;
	queue[MOVE(rear)]=s;	flag[s]=true;
	//可不要
//	for(i=nodev[s];i!=-1;i=next[i])
//	{
//		u=nodeu[i];	val=value[i];
//		dist[u]=val;	
//		queue[MOVE(rear)]=u; flag[u]=true;
//	}

	while(front!=rear)
	{
		v=queue[MOVE(front)]; flag[v]=false;
		for(i=nodev[v];i!=-1;i=next[i])
		{
			u=nodeu[i]; val=value[i];
			if(dist[v]+val<dist[u])
			{
				dist[u]=dist[v]+val;
				if(!flag[u])
				{
					queue[MOVE(rear)]=u;
					flag[u]=true;
				}
			}
		}
	}
}

void solve()
{
	int n,m;
	
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		Build_Graph(n,m);
		SPFA(S,n);
		printf("%d\n",1-dist[E]);
	}
}

int main()
{
	solve();
	return 0;
}