首页 > 代码库 > POJ 3249 Test for Job 拓扑排序+DP

POJ 3249 Test for Job 拓扑排序+DP

2024-07-15 18:55:17   220人阅读

http://poj.org/problem?id=3249

题意：

给一个有向无环图DAG(不一定联通)，每个点有权值，入度为0的点为起点，出度为0的点为终点，选择一个起点走到一个终点，使得路上的权和最大。

分析：

dp[to] = max(dp[from]) + value[to]，然后先拓扑排序保证状态正确转移即可，终点做标记，如果是终点则尝试更新答案。

update:因为点权可以为负，所以程序里用dp[i] == -1表示未访问过该点是有问题的，不过没有遇上会卡掉这种情况的数据＝。＝

 

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6  7 int n, m, esize, x, y; 8 int a[100100], en[100100], in[100100], bfn[100100], dp[100100]; 9 bool ed[100100];10 struct edge{11     int v, n;12 } e[1000100];13 void addedge(int u, int v)14 {15     e[esize].v = v;;16     e[esize].n = en[u];17     en[u] = esize ++;18 }19 queue<int> q;20 int main()21 {22     while(scanf("%d%d", &n, &m) != EOF)23     {24         for (int i = 1; i <= n; i++)25             scanf("%d", a+i);26         memset(en, -1, sizeof(en));27         memset(in, 0, sizeof(0));28         memset(ed, true, sizeof(ed));29         esize = 0;30         for (int i = 0; i < m; i++){31             scanf("%d %d", &x, &y);32             addedge(x, y);33             in[y]++;34             ed[x] = 0;35         }36         for (int i = 1; i <= n; i++)37             if (!in[i]) q.push(i);38         int ans = -2147483640;39         int cnt = 0;40         while(!q.empty())41         {42             int u = q.front(); q.pop();43             bfn[cnt++] = u;44             for (int t = en[u]; t != -1; t = e[t].n){45                 int v = e[t].v;46                 in[v] --;47                 if (in[v] == 0)    q.push(v);48             }49         }50         memset(dp, -1, sizeof(dp));51         for (int i = 0; i < n; i++){52             int u = bfn[i];53             if (dp[u] == -1) dp[u] = a[u];54             if (ed[u]) ans = max(ans, dp[u]);55             for (int t = en[u]; t != -1; t = e[t].n){56                 int v = e[t].v;57                 if (dp[v] == -1 || dp[v] < dp[u] + a[v])58                     dp[v] = dp[u] + a[v];59             }60         }61         printf("%d\n", ans);62     }63     return 0;64 }

 


联系
我们