POJ 3249-Test for Job(拓扑排序&&DP)

Love The Way You Lie 2022-08-21 13:42 24阅读 0赞

# Test for Job #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 10339</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 2405</td> 
  </tr> 
 </tbody> 
</table>

Description

Mr.Dog was fired by his company. In order to support his family, he must find a new job as soon as possible. Nowadays, It's hard to have a job, since there are swelling numbers of the unemployed. So some companies often use hard tests for their recruitment.

The test is like this: starting from a source-city, you may pass through some directed roads to reach another city. Each time you reach a city, you can earn some profit or pay some fee, Let this process continue until you reach a target-city. The boss will compute the expense you spent for your trip and the profit you have just obtained. Finally, he will decide whether you can be hired.

In order to get the job, Mr.Dog managed to obtain the knowledge of the net profit *Vi* of all cities he may reach (a negative *Vi* indicates that money is spent rather than gained) and the connection between cities. A city with no roads leading to it is a source-city and a city with no roads leading to other cities is a target-city. The mission of Mr.Dog is to start from a source-city and choose a route leading to a target-city through which he can get the maximum profit.

Input

The input file includes several test cases.  
The first line of each test case contains 2 integers *n* and *m*(1 ≤ *n* ≤ 100000, 0 ≤ *m* ≤ 1000000) indicating the number of cities and roads.  
The next *n* lines each contain a single integer. The *i*th line describes the net profit of the city *i*, *Vi* (0 ≤ | *Vi*| ≤ 20000)  
The next m lines each contain two integers *x*, *y* indicating that there is a road leads from city *x* to city *y*. It is guaranteed that each road appears exactly once, and there is no way to return to a previous city.

Output

The output file contains one line for each test cases, in which contains an integer indicating the maximum profit Dog is able to obtain (or the minimum expenditure to spend)

Sample Input

6 5
    1
    2
    2
    3
    3
    4
    1 2
    1 3
    2 4
    3 4
    5 6

Sample Output

Hint

![3249_1.gif][]

Source

[POJ Monthly--2007.07.08][], 落叶飞雪

## 题目意思： ##

一个人去找工作，面试官给了他这道题：  
给出一些城市与城市之间的道路，每到达一个城市，就会获得一些收益或是损失，求最大收益。

## 解题思路： ##

数据量巨大！  
用链式前向星方式保存路径，拓扑排序后，再使用用DAG单源最短路算法。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    #define inf 2000000010
    #define Maxn 100010
    #define Maxm 1000010
    using namespace std;
    int n,i,j,e,num,Max;
    int dist[Maxn],head[Maxn];//存储保存描述点vi边信息的链的起点在Edges数组的位置
    int value[Maxn],indegree[Maxn],outdegree[Maxn];//点值和入度出度
    int ans[Maxn];//拓扑序列
    struct Edge
    {
        //链式前向星 将新加入的节点链在对应链的最开始并修改head数组的对应位置的值
        int to;//终点
        int val;//权值
        int next;//指向下一条边
    } edge[Maxm];
    
    void init()//初始化
    {
        memset(indegree,0,sizeof(indegree));
        memset(outdegree,0,sizeof(outdegree));
        memset(head,-1,sizeof(head));
        memset(ans,0,sizeof(ans));
        for(int i=0; i<=100010; i++)
            dist[i]=-inf;
        Max=-inf;
        e=0;
        num=1;
    }
    
    void addedge(int from,int to,int val)
    {
        edge[e].to=to;
        edge[e].val=val;
        edge[e].next=head[from];
        head[from]=e++;
    }
    
    void Topsort()//拓扑排序
    {
        queue<int> q;
        int now,adj;
        for(i=1; i<=n; i++)
        {
            if(indegree[i]==0)
            {
                q.push(i);
                dist[i]=value[i];
            }
        }
        while(!q.empty())
        {
            now=q.front();
            ans[num++]=now;
            q.pop();
            for(i=head[now]; i!=-1; i=edge[i].next)
            {
                adj=edge[i].to;
                indegree[adj]--;
                if(!indegree[adj])
                    q.push(adj);
            }
        }
    }
    
    void DAG()//DAG单源最短路
    {
        for(i=1; i<num; i++)
        {
            for(j=head[ans[i]]; j!=-1; j=edge[j].next)
            {
                dist[edge[j].to]=max(dist[edge[j].to],dist[ans[i]]+edge[j].val);
            }
            if(outdegree[ans[i]]==0)
            {
                if(dist[ans[i]]>Max)
                    Max=dist[ans[i]];
            }
        }
    }
    
    int main()
    {
        int m,i,a,b;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            init();
            for(i=1; i<=n; i++)
                scanf("%d",&value[i]);
            for(i=1; i<=m; i++)
            {
                scanf("%d%d",&a,&b);
                addedge(a,b,value[b]);
                indegree[b]++,outdegree[a]++;
            }
            Topsort();
            DAG();
            printf("%d\n",Max);
        }
        return 0;
    }

[3249_1.gif]: /images/20220724/96b01d97bbd1492080c17a0c49b0cc92.png
[POJ Monthly--2007.07.08]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.07.08