题目来源：http://poj.org/problem?id=3160
强连通+DP
题目大意：圣诞节要到了，flymouse要给他的队友们送去礼物，，n个队友住在n个不同的房子里，每个队友住的地方都有一个comfort index （positive or negative）;
他每给一个队友送去礼物，都将得到该队友的comfort index ，问最后他能获得的maximized sum of accumulated comfort indices；
不过题目还有其他的要求：follow directed paths to visit _disibledevent=>
View Code 1 # include
2 # include 3 # include 4 # define N 30005 5 # define M 150005 6 using namespace std; 7 struct node{ 8 int from,next,to; 9 }edge1[M],edge2[M],edge[M]; 10 int head[N],tol1,head1[N],head2[N],tol2,val[N],visit1[N],visit2[N],V[N],tol; 11 int T[N],Belong[N],DP[N],in[N],Tcnt,Bcnt,Max,visit[N]; 12 queueS; 13 void Add(int a,int b) 14 { 15 edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++; 16 edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++; 17 } 18 void add(int a,int b) 19 { 20 edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++; 21 } 22 void dfs1(int i) 23 { 24 int j,v; 25 visit1[i]=1; 26 for(j=head1[i];j!=-1;j=edge1[j].next) 27 { 28 v=edge1[j].to; 29 if(!visit1[v]) dfs1(v); 30 } 31 T[Tcnt++]=i; 32 } 33 void dfs2(int i) 34 { 35 int j,v; 36 visit2[i]=1; 37 Belong[i]=Bcnt; 38 if(val[i]>0) V[Bcnt]+=val[i]; 39 for(j=head2[i];j!=-1;j=edge2[j].next) 40 { 41 v=edge2[j].to; 42 if(!visit2[v]) dfs2(v); 43 } 44 } 45 int main() 46 { 47 int i,n,m,a,b,j,v,cur; 48 while(scanf("%d%d",&n,&m)!=EOF) 49 { 50 for(i=0;i=0;i--) 67 { 68 if(!visit2[T[i]]) 69 { 70 dfs2(T[i]); 71 Bcnt++; 72 } 73 } 74 tol=0; 75 memset(head,-1,sizeof(head)); 76 memset(in,0,sizeof(in)); 77 for(i=0;iMax) Max=V[cur];
109 }
110 printf("%d\n",Max);
111 }
112 return 0;
113 }
延伸阅读
最新评论