sdut 2498【aoe 网上的关键路径】

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2498
代码超时怎么破：
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<stack>
  8 using namespace std;
  9 int mapx[10000][10000],ve[10001],vl[10001],h[10001],m,k;
 10 stack<int>zhan;
 11 queue<int>e;
 12 queue<int>l;
 13 void tuopu();
 14 void gengxin();
 15 int main()
 16 {
 17     while(cin>>m>>k)
 18     {
 19         memset(mapx,0,sizeof(mapx));
 20         memset(h,0,sizeof(h));
 21         memset(ve,0,sizeof(ve));
 22         memset(vl,0,sizeof(vl));
 23         int i,u,v,countx;
 24         for(i=1; i<=k; i++)
 25         {
 26             cin>>u>>v>>countx;
 27             mapx[u][v]=countx;
 28             h[v]++;
 29         }
 30         tuopu();
 31         gengxin();
 32     }
 33 }
 34 void tuopu()
 35 {
 36     int i,flag=0,j;
 37     while(flag=!flag)
 38     {
 39         for(i=1; i<=m; i++)
 40         {
 41             if(h[i]==0)
 42             {
 43                 flag=0;
 44                 h[i]=-1;
 45                 zhan.push(i);
 46                 for(j=1; j<=m; j++)
 47                     if(mapx[i][j]!=0)
 48                         h[j]--;
 49                 //更新 ve数组
 50                 int y=0;
 51                 for(j=1; j<=m; j++)
 52                 {
 53                     if(mapx[j][i]!=0)
 54                     {
 55                         if(mapx[j][i]+ve[j]>y)
 56                         {
 57                             y=mapx[j][i]+ve[j];
 58                         }
 59                     }
 60                 }
 61                 ve[i]=y;
 62             }
 63         }
 64     }
 65     /*while(!zhan.empty())
 66     {
 67         cout<<zhan.top()<<" ";
 68         zhan.pop();
 69     }
 70     cout<<endl;*/
 71     //输出ve 数组
 72     /*for(i=1;i<=m;i++)
 73         cout<<ve[i]<<" ";
 74     cout<<endl;*/
 75 }
 76 void gengxin()
 77 {
 78     //更新 vl数组和v数组，e数组
 79     int i,j;
 80     int x=ve[m];
 81     for(i=1; i<=m; i++)
 82         vl[i]=x;
 83     int maxx=x,z[1000],top=-1,z1[1000];
 84     while(!zhan.empty())
 85     {
 86         x=zhan.top();
 87         int y=maxx;
 88         for(i=1; i<=m; i++)
 89         {
 90             if(mapx[x][i]!=0)
 91             {
 92                 if(y>vl[i]-mapx[x][i])
 93                     y=vl[i]-mapx[x][i];
 94             }
 95         }
 96         vl[x]=y;
 97         zhan.pop();
 98     }
 99     //验证输出vl数组
100     /*for(i=1;i<=m;i++)
101         cout<<vl[i]<<" ";
102     cout<<endl;*/
103     int countx=0,q1=0;
104     for(i=1; i<=m; i++)
105     {
106         for(j=1; j<=m; j++)
107         {
108             if(mapx[i][j]!=0)
109             {
110                 //e.push(ve[i]);
111                 //l.push(vl[j]-mapx[i][j]);
112                 if(ve[i]==vl[j]-mapx[i][j])
113                 {
114                     if(j==m)
115                         q1=1;
116                     countx=countx+mapx[i][j];
117                     z[++top]=i;
118                     z1[top]=j;
119                     break;
120                 }
121             }
122         }
123         if(q1==1)break;
124     }
125     cout<<countx<<endl;
126     for(i=0; i<=top; i++)
127         cout<<z[i]<<" "<<z1[i]<<endl;
128     //验证输出
129     /*
130     while(!e.empty())
131     {
132         cout<<e.front()<<" ";
133         e.pop();
134     }
135     cout<<endl;
136     while(!l.empty())
137     {
138         cout<<l.front()<<" ";
139         l.pop();
140     }
141     cout<<endl;*/
142 }
143 /*测试数据
144 9 11
145 1 2 6
146 1 3 4
147 1 4 5
148 2 5 1
149 3 5 1
150 4 6 2
151 5 7 8
152 5 8 7
153 6 8 4
154 7 9 2
155 8 9 4
156 */
View Code