基礎實驗6-2.6 最短工期 (25 分)

拓撲排序，AOE網

#include<stdio.h>
#include<string.h>
const int N=1010;
const int inf=0x3f3f3f;
int map[N][N];
int in[N];   
int early[N];
int ret=0;		   
int n,m,ans=0;
void t1()	
{
    for(int k=0;k<n;++k)
	{
        for(int i=0;i<n;i++)
		{
            if(in[i]==0)
			{
                ret++;
                in[i]--;
                for(int j=0;j<n;j++)
				{
                    if(map[i][j]!=-1)
					{
                        in[j]--;
                        if(early[j]<early[i]+map[i][j])
                            early[j]=early[i]+map[i][j];
                        if(ans<early[j])
                            ans=early[j];
                    }
                }
            }
        }
    }
}
int main()
{
    memset(map,-1,sizeof(map)); 
    scanf("%d%d",&n,&m);
    while(m--)
	{
		int x,y,z;
    	scanf("%d%d%d",&x,&y,&z);
        map[x][y]=z;
        in[y]++;
    }
    t1();
   	if(ret==n){
   		printf("%d",ans);
	} 
    else
    	printf("Impossible");
    return 0;
}