貌似是道水题。TLE了几次。把所有的输入输出改成scanf 和 printf ，有吧队列改成了数组模拟。然后就AC 了。2333333....
Description:
MR.DOG 在找工作的过程中呢。遇见了这样一个问题。有n个城市，m条小道。然后要从入度为0的点出发，出度为0的点结束，中途经过的城市呢，都是要付费的。负数表示花费。正数表示收益。然后让你求收益最大或者说花费最少的总值。
貌似。BFS和DFS都会超时。不妨一试。附代码：
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#define maxn 100005
#define maxm 1000005
#define inf 2100000000
using namespace std;
struct Arc
{
int point;
int next_arc;
};
//node 存储每个顶点，arc存储每条边。node[i]表示第i个顶点指向的第一条边在arc中的位置。next_arc表示和这条边同样出发点的下一条边在arc中的位置。
Arc arc[maxm];
int node[maxn], val[maxn];
//ind 和 outd 数组表示顶点的入度和出度 dp数组表示到达每个点的的最大收益
int ind[maxn], outd[maxn], dp[maxn];
// 数组模拟队列 tot表示总共加入的边的数量
int tot, front, rear;
int q[maxn];
void insert(int u, int v) // 加入从u指向v的一条边
{
arc[tot].next_arc = node[u];
arc[tot].point = v;
node[u] = tot++;
}
void init()
{
tot = 0;
memset(node, -1, sizeof(node));
memset(ind, 0, sizeof(ind));
memset(outd, 0, sizeof(outd));
}
void topsort() // 拓扑排序+DP
{
while(front <= rear)
{
int x = q[front++];
for (int e=node[x]; e!=-1; e=arc[e].next_arc)
{
int temp = arc[e].point;
ind[temp]--;
dp[temp] = max(dp[temp], dp[x] + val[temp]);
if (ind[temp] == 0)
{
q[++rear] = temp;
}
}
}
}
int main()
{
int n, m, x, y;
while(~scanf("%d%d", &n, &m))
{
init();
front = 0, rear = -1;
for (int i=1; i<=n; ++i)
{
scanf("%d", &val[i]);
}
for (int i=0; i<m; ++i)
{
scanf("%d%d", &x, &y);
insert(x, y);
ind[y]++;
outd[x]++;
}
for (int i=1; i<=n; ++i)
{
dp[i] = -inf;
}
for (int i=1; i<=n; ++i)
{
if (ind[i] == 0)
{
q[++rear] = i;
dp[i] = val[i];
}
}
topsort();
int ans = -inf;
for (int i=1; i<=n; ++i)
{
if (outd[i] == 0)
ans = max(ans, dp[i]);
}
printf("%d
", ans);
}
return 0;
}