POJ 3249 Test for Job

题目传送门

题目中文翻译:

Description

杜格先生被他的公司解雇了。为了支持他的家庭，他必须尽快找到一份新工作。现在，很难找到工作，因为失业人数不断增加。所以有些公司经常在招聘时使用严格的测试。

测试是这样的：从一个源城市开始，你可以通过一些定向道路到达另一个城市。每次到达城市，您都可以赚取一定的利润或支付一定的费用，让这个过程继续下去，直到您到达目标城市。老板会计算你在旅行中花费的费用和你刚刚获得的利润。最后，他会决定你是否可以被雇用。

为了得到这份工作，杜尔先生设法获得了他可能达到的所有城市的净利润Vi的知识（负的Vi表示钱花费而不是增加）以及城市之间的联系。没有通往它的道路的城市是一个源城市，没有通往其他城市的道路的城市是一个目标城市。 Dog先生的使命是从一个源城市开始，选择一条通往目标城市的路线，通过这条路线他可以获得最大的利润。

Input

输入文件包含几个测试用例。

每个测试用例的第一行包含2个整数n和m（1≤n≤100000，0≤m≤1000000），表示城市和道路的数量。

接下来的n行包含一个整数。第i行描述城市i的净利润Vi（0≤| Vi |≤20000）

接下来的m行包含两个整数x，y，表示从城市x到城市y有一条公路通往。 保证每条道路只出现一次，并且无法返回到以前的城市。

Output

输出文件包含每个测试用例的一行，其中包含一个整数，指示杜格先生能够获得的最大利润（或花费的最小支出）

Sample Input

6 5

1 2

1 3

2 4

3 4

5 6

Sample Output

解题思路:

对于那些没有入度的点,我们新建一个超级源点,并指向所有入度为0的点,求超级源点到目标点的距离,使用拓扑排序序列更新答案.

还有,记住一句话,不开long long见祖宗.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define MAX 1000007
 5 #define MAXN 100007
 6 #define MAXM 2000007
 7 #define MOD 1000000007
 8 
 9 using namespace std;
10 
11 struct kkk {
12     int to,w,next;
13 }e[MAXM];
14 int head[MAXN],tot,ind[MAXN],n,m,s,v[MAXN],outd[MAXN];
15 long long dis[MAXN],ans;
16 
17 inline void chushihua() {
18     memset(head,-1,sizeof(head));
19     memset(ind,0,sizeof(ind));
20     memset(outd,0,sizeof(outd));
21     ans = 0xc0c0c0c0c0c0c0c0;
22     tot = 0;
23 }
24 
25 inline void add(int x,int y,int value) {
26     e[++tot].to = y;
27     e[tot].w = value;
28     e[tot].next = head[x];
29     head[x] = tot;
30     ind[y]++;
31     outd[x]++;
32 }
33 
34 inline void tuopu() {
35     int q[MAXN],p = 0;
36     for(int i = 0;i <= n; i++)
37         if(ind[i] == 0) q[p++] = i;
38     for(int i = 0;i < p; i++) {
39         for(int k = head[q[i]];k != -1;k = e[k].next) {
40             int t = e[k].to;
41             ind[t]--;
42             if(ind[t] == 0) q[p++] = t;
43         }
44     }
45     memset(dis,0xc0,sizeof(dis));
46     dis[0] = 0;
47     for(int i = 0;i < p; i++)
48         for(int k = head[q[i]];k != -1;k = e[k].next) {
49             int t = e[k].to;
50             dis[t] = max(dis[t],dis[q[i]] + e[k].w);
51         }
52 } 
53 
54 int main()
55 {
56     while(scanf("%d%d",&n,&m) == 2) {
57         chushihua();
58         for(int i = 1;i <= n; i++)
59             scanf("%d",&v[i]);
60         for(int i = 1;i <= m; i++) {
61             int x,y;
62             scanf("%d%d",&x,&y);
63             add(x,y,v[y]);
64         }
65         for(int i = 1;i <= n; i++) {
66             if(ind[i] == 0)
67                 add(0,i,v[i]);
68         }
69         tuopu();
70         for(int i = 1;i <= n; i++)
71             if(outd[i] == 0)
72                 ans = max(ans,dis[i]);
73         printf("%lld
",ans);    
74     }
75     return 0;
76 }