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

題意讀懂是關(guān)鍵，he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence.通過(guò)這句話知道當(dāng)收禮者給予的反應(yīng)是負(fù)值時(shí)可以不加，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.即起點(diǎn)只有一個(gè)，且一條路到底，即要我們尋找一條路徑的尾節(jié)點(diǎn)出度為0，且路徑中所有數(shù)值為正的節(jié)點(diǎn)的和最大。

明顯是dfs，用max數(shù)組記錄每一個(gè)節(jié)點(diǎn)到出度為0的節(jié)點(diǎn)的最大值，但是由于此圖是有向圖，可能會(huì)產(chǎn)生環(huán)，因此先用強(qiáng)連通縮點(diǎn)，在dfs找到最到值。

1 #include <stdio.h>
2 #include <memory.h>
3 #define SIZE 30001
4 #define MAX(a,b) ((a)>(b)?(a):(b))
5 struct node
6 {
7 int end;
8 node *next;
9 }edge[5*SIZE],*head[SIZE],*p,Edge[5*SIZE],*Head[SIZE],*q;
10 int feel[SIZE],root_stack[SIZE],stack[SIZE],init[SIZE],belong[SIZE],sum[SIZE],max[SIZE];
11 bool visit[SIZE];
12 int cnt,father,MAXER;
13 void bulid(int a,int b)
14 {
15 p->end=b;
16 p->next=head[a];
17 head[a]=p++;
18 }
19 void add(int a,int b)
20 {
21 q->end=b;
22 q->next=Head[a];
23 Head[a]=q++;
24 }
25 void Gabow(int key)
26 {
27 root_stack[++root_stack[0]]=stack[++stack[0]]=key;
28 init[key]=++cnt;
29 for(node*tmp=head[key];tmp;tmp=tmp->next)
30 {
31 if(!init[tmp->end])
32 Gabow(tmp->end);
33 else if(!belong[tmp->end])
34 while(init[root_stack[root_stack[0]]]>init[tmp->end])
35 --root_stack[0];
36 }
37 if(root_stack[root_stack[0]]==key)
38 {
39 ++father,--root_stack[0];
40 do
41 {
42 belong[stack[stack[0]]]=father;
43 if(feel[stack[stack[0]]]>0)
44 sum[father]+=feel[stack[stack[0]]];
45 }
46 while(stack[stack[0]--]!=key);
47 }
48 }
49 void dfs(int key)
50 {
51 visit[key]=true;
52 for(node *tmp=Head[key];tmp;tmp=tmp->next)
53 {
54 if(!visit[tmp->end])
55 dfs(tmp->end);
56 max[key]=MAX(max[key],max[tmp->end]);
57 }
58 max[key]+=sum[key];
59 MAXER=MAX(MAXER,max[key]);
60 }
61 void ini()
62 {
63 memset(head,NULL,sizeof(head));
64 memset(Head,NULL,sizeof(Head));
65 memset(visit,false,sizeof(visit));
66 memset(feel,0,sizeof(feel));
67 memset(root_stack,0,sizeof(root_stack));
68 memset(stack,0,sizeof(stack));
69 memset(init,0,sizeof(init));
70 memset(belong,0,sizeof(belong));
71 memset(sum,0,sizeof(sum));
72 memset(max,0,sizeof(max));
73 }
74 int main()
75 {
76 int n,m;
77 while(scanf("%d %d",&n,&m)==2)
78 {
79 for(int i=0;i<n;++i)
80 scanf("%d",&feel[i]);
81 p=edge;
82 for(int i=0,a,b;i<m;++i)
83 {
84 scanf("%d %d",&a,&b);
85 bulid(a,b);
86 }
87 cnt=father=0;
88 for(int i=0;i<n;++i)
89 if(!init[i])
90 Gabow(i);
91 q=Edge;
92 for(int i=0;i<n;++i)
93 for(node*tmp=head[i];tmp;tmp=tmp->next)
94 if(belong[i]!=belong[tmp->end])
95 add(belong[i],belong[tmp->end]);
96 MAXER=-(1<<31);
97 for(int i=1;i<=father;++i)
98 if(!visit[i])
99 dfs(i);
100 printf("%d\n",MAXER);
101 ini();
102 }
103 return 0;
104 }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/mengxm-lincf/archive/2011/09/08/2171297.html

總結(jié)

以上是生活随笔為你收集整理的poj3160的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。