热门标签 | 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


推荐阅读
  • Docker的安全基准
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准,旨在为第三方应用提供安全的用户资源访问授权,同时确保用户的账户信息(如用户名和密码)不会暴露给第三方。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法,提供了多个代码示例及应用场景,帮助开发者更好地理解和使用该方法。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 在 Windows 10 中,F1 至 F12 键默认设置为快捷功能键。本文将介绍几种有效方法来禁用这些快捷键,并恢复其标准功能键的作用。请注意,部分笔记本电脑的快捷键可能无法完全关闭。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 本文介绍了如何利用JavaScript或jQuery来判断网页中的文本框是否处于焦点状态,以及如何检测鼠标是否悬停在指定的HTML元素上。 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先,通过change事件监听用户选择的省份,并动态加载对应的城市列表。其次,详细讲解了使用Validation插件进行表单验证的方法,包括内置规则、自定义规则及实时验证功能。 ... [详细]
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社区 版权所有