粗心了點,就一個強連通縮點,忘了出棧後要標記,找了一天的bug,,,
題意有點難懂,飛鼠想給大家發禮物,收到禮物後大家給飛鼠的滿足程度都已數量化。每個人都住一個房間,房間之間的路是單向的,飛鼠可以選任一個點為起點,路可以重復走,房間不能重復訪問,但可以經過而不訪問。現在問飛鼠得到的滿足程度最大會是多少?,有負值,,如果圖不形成環,直接求就可以,看了樣例可能形成環,所以用Tarjan縮點,,,
#include<stdio.h> #include<stack> #include<string.h> #include<queue> #define N 30010 using namespace std; struct edage { int ed; struct edage *next; }*E[N],*e[N]; struct op { int x,w; friend bool operator < (op a, op b) { return a.w<b.w; } }cur,next; void addedage(int x,int y,struct edage *p[]) { struct edage *q=new edage; q->ed=y; q->next=p[x]; p[x]=q; } int n,m,ins[N],belong[N],low[N],dfs[N],cont[N],a[N],idx,ans,inq[N],vis[N],dis[N],dp[N]; stack<int>Q; void Tarjan(int x) { int v; low[x]=dfs[x]=idx++; Q.push(x); ins[x]=1; for(edage *p=E[x];p;p=p->next) { if(dfs[p->ed]==-1) { Tarjan(p->ed); low[x]=low[x]>low[p->ed]?low[p->ed]:low[x]; } else if(ins[p->ed]==1) low[x]=low[x]>dfs[p->ed]?dfs[p->ed]:low[x]; } if(dfs[x]==low[x]) { while(1) { v=Q.top(); Q.pop(); belong[v]=ans; ins[v]=0;//就少了這行,找了一天的bug if(a[v]>0) cont[ans]+=a[v]; if(v==x)break; } ans++; } } int bfs(int u) { int max=-1; priority_queue<op>QQ; cur.x=u; cur.w=cont[u]; QQ.push(cur); while(!QQ.empty()) { cur=QQ.top(); QQ.pop(); if(vis[cur.x]==1)continue; if(max<cur.w)max=cur.w; for(edage *p=e[cur.x];p;p=p->next) { if(vis[p->ed]==0) { next.x=p->ed; next.w=cur.w+cont[p->ed]; QQ.push(next); } } } return max; } /*int spfa(int s) { int i; for(i=1;i<=ans;i++) { dis[i]=0; } dis[s]=cont[s]; queue<int>q; q.push(s); while(!q.empty()) { int w=q.front(); q.pop(); for(edage *p=e[w];p;p=p->next) { if(dis[p->ed]<dis[w]+cont[p->ed]) { q.push(p->ed); dis[p->ed]=dis[w]+cont[p->ed]; } } } int max=-1; for(i=1;i<=ans;i++) { if(max<dis[i]) max=dis[i]; } return max; }*/ int main() { int i,j,x,y; while(scanf("%d%d",&n,&m)!=-1) { for(i=0;i<n;i++) scanf("%d",&a[i]); memset(dfs,-1,sizeof(dfs)); memset(E,NULL,sizeof(E)); memset(e,NULL,sizeof(e)); memset(ins,0,sizeof(ins)); memset(inq,0,sizeof(inq)); memset(cont,0,sizeof(cont)); for(i=0;i<m;i++) { scanf("%d%d",&x,&y); addedage(x,y,E); } ans=idx=0; for(i=0;i<n;i++) { if(dfs[i]==-1) Tarjan(i); } for(i=0;i<n;i++) { for(edage *p=E[i];p;p=p->next) { if(belong[i]!=belong[p->ed]) { inq[belong[p->ed]]++; addedage(belong[i],belong[p->ed],e); } } } int max=-1; for(i=0;i<ans;i++) { memset(vis,0,sizeof(vis)); if(inq[i]==0) { j=bfs(i); if(max<j) max=j; } } printf("%d\n",max); /* for(i=1;i<=ans;i++) if(inq[i]==0) { addedage(0,i,e); } printf("%d\n",spfa(0));*/ } return 0; }