热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

POJ3160FatherChristmasflymouse

FatherChristmasflymouseTimeLimit:1000msMemoryLimit:131072KBThisproblemwillbejudgedonPKU.Or

Father Christmas flymouse

Time Limit: 1000ms
Memory Limit: 131072KB
This problem will be judged on PKU. Original ID: 3160
64-bit integer IO format: %lld      Java class name: Main
 

After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.

During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.

Input

The input contains several test cases. Each test cases start with two integers N and M not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were N team members living in N distinct rooms and M direct paths. On the next N lines there are N integers, one on each line, the i-th of which gives the comfort index of the words of the team member in the i-th room. Then follow M lines, each containing two integers i and j indicating a directed path from the i-th room to the j-th one. Process to end of file.

 

Output

For each test case, output one line with only the maximized sum of accumulated comfort indices.

 

Sample Input

2 2
14
21
0 1
1 0

Sample Output

35

Source

POJ Monthly--2006.12.31
 
解题:强连通缩点+最长路
,,
  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include <string>
 11 #include <set>
 12 #include 
 13 #define LL long long
 14 #define pii pair
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 30010;
 18 struct arc{
 19     int to,next;
 20     arc(int x = 0,int y = -1){
 21         to = x;
 22         next = y;
 23     }
 24 };
 25 arc e[maxn*10];
 26 vector<int>g[maxn];
 27 int tot,head[maxn],d[maxn],dfn[maxn],low[maxn],belong[maxn];
 28 int hv[maxn],thv[maxn],scc,idx;
 29 int my[maxn],in[maxn],out[maxn],top,n,m;
 30 bool instack[maxn],inq[maxn];
 31 void add(int u,int v){
 32     e[tot] = arc(v,head[u]);
 33     head[u] = tot++;
 34 }
 35 void tarjan(int u){
 36     dfn[u] = low[u] = ++idx;
 37     my[top++] = u;
 38     instack[u] = true;
 39     for(int i = head[u]; ~i; i = e[i].next){
 40         if(!dfn[e[i].to]){
 41             tarjan(e[i].to);
 42             low[u] = min(low[u],low[e[i].to]);
 43         }else if(instack[e[i].to]) low[u] = min(low[u],dfn[e[i].to]);
 44     }
 45     if(low[u] == dfn[u]){
 46         int v;
 47         scc++;
 48         do{
 49             v = my[--top];
 50             instack[v] = false;
 51             belong[v] = scc;
 52         }while(v != u);
 53     }
 54 }
 55 void init(){
 56     for(int i = 0; i <= n; ++i){
 57         head[i] = -1;
 58         dfn[i] = low[i] = 0;
 59         out[i] = belong[i] = 0;
 60         inq[i] = instack[i] = false;
 61         g[i].clear();
 62         hv[i] = thv[i] = 0;
 63         in[i] = d[i] = 0;
 64     }
 65     tot = idx = scc = 0;
 66 }
 67 void spfa(){
 68     queue<int>q;
 69     q.push(0);
 70     while(!q.empty()){
 71         int u = q.front();
 72         q.pop();
 73         inq[u] = false;
 74         for(int i = g[u].size()-1; i >= 0; --i){
 75             if(d[g[u][i]]  thv[g[u][i]]){
 76                 d[g[u][i]] = d[u] + thv[g[u][i]];
 77                 if(!inq[g[u][i]]){
 78                     inq[g[u][i]] = true;
 79                     q.push(g[u][i]);
 80                 }
 81             }
 82         }
 83     }
 84 }
 85 int main() {
 86     int u,v,w;
 87     while(~scanf("%d %d",&n,&m)){
 88         init();
 89         for(int i = 0; i i)
 90             scanf("%d",hv+i);
 91         for(int i = 0; i i){
 92             scanf("%d %d",&u,&v);
 93             add(u,v);
 94         }
 95         for(int i = 0; i i)
 96             if(!dfn[i]) tarjan(i);
 97         for(int i = 0; i i)
 98             if(hv[i] > 0) thv[belong[i]] += hv[i];
 99         for(int i = 0; i i){
100             for(int j = head[i]; ~j; j = e[j].next){
101                 if(belong[i] == belong[e[j].to]) continue;
102                 g[belong[i]].push_back(belong[e[j].to]);
103                 in[belong[e[j].to]]++;
104                 out[belong[i]]++;
105             }
106         }
107         for(int i = 1; i <= scc; ++i)
108             if(!in[i]) g[0].push_back(i);
109         int ans = 0;
110         spfa();
111         for(int i = 1; i <= scc; ++i)
112             if(!out[i]) ans = max(ans,d[i]);
113         printf("%d\n",ans);
114     }
115     return 0;
116 }
View Code

POJ 3160 Father Christmas flymouse


推荐阅读
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准,旨在为第三方应用提供安全的用户资源访问授权,同时确保用户的账户信息(如用户名和密码)不会暴露给第三方。 ... [详细]
  • CSS 布局:液态三栏混合宽度布局
    本文介绍了如何使用 CSS 实现液态的三栏布局,其中各栏具有不同的宽度设置。通过调整容器和内容区域的属性,可以实现灵活且响应式的网页设计。 ... [详细]
  • 本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建,还处理了系统服务的配置和启动,确保在多种 Linux 发行版上都能顺利运行。 ... [详细]
  • MySQL中枚举类型的所有可能值获取方法
    本文介绍了一种在MySQL数据库中查询枚举(ENUM)类型字段所有可能取值的方法,帮助开发者更好地理解和利用这一数据类型。 ... [详细]
  • 国内BI工具迎战国际巨头Tableau,稳步崛起
    尽管商业智能(BI)工具在中国的普及程度尚不及国际市场,但近年来,随着本土企业的持续创新和市场推广,国内主流BI工具正逐渐崭露头角。面对国际品牌如Tableau的强大竞争,国内BI工具通过不断优化产品和技术,赢得了越来越多用户的认可。 ... [详细]
  • 深入理解 Oracle 存储函数:计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程,并提供完整的代码示例。 ... [详细]
  • 本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进,包括右缩进和左缩进的具体操作方法。 ... [详细]
  • 在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ,包括端口开放及防火墙设置。通过本文,您可以掌握完整的ActiveMQ部署流程,确保其在网络环境中正常运行。 ... [详细]
  • 如何在WPS Office for Mac中调整Word文档的文字排列方向
    本文将详细介绍如何使用最新版WPS Office for Mac调整Word文档中的文字排列方向。通过这些步骤,用户可以轻松更改文本的水平或垂直排列方式,以满足不同的排版需求。 ... [详细]
  • 理解存储器的层次结构有助于程序员优化程序性能,通过合理安排数据在不同层级的存储位置,提升CPU的数据访问速度。本文详细探讨了静态随机访问存储器(SRAM)和动态随机访问存储器(DRAM)的工作原理及其应用场景,并介绍了存储器模块中的数据存取过程及局部性原理。 ... [详细]
  • 几何画板展示电场线与等势面的交互关系
    几何画板是一款功能强大的物理教学软件,具备丰富的绘图和度量工具。它不仅能够模拟物理实验过程,还能通过定量分析揭示物理现象背后的规律,尤其适用于难以在实际实验中展示的内容。本文将介绍如何使用几何画板演示电场线与等势面之间的关系。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 本文介绍如何在应用程序中使用文本输入框创建密码输入框,并通过设置掩码来隐藏用户输入的内容。我们将详细解释代码实现,并提供专业的补充说明。 ... [详细]
  • 本文介绍如何通过SQL查询从JDE(JD Edwards)系统中提取所有字典数据,涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
author-avatar
倩倩
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有