粗心了点,就一个强连通缩点,忘了出栈后要标记,找了一天的bug,,,
题意有点难懂,飞鼠想给大家发礼物,收到礼物后大家给飞鼠的满足程度都已数量化。每个人都住一个房间,房间之间的路是单向的,飞鼠可以选任一个点为起点,路可以重复走,房间不能重复访问,但可以经过而不访问。现在问飞鼠得到的满足程度最大会是多少?,有负值,,如果图不形成环,直接求就可以,看了样例可能形成环,所以用Tarjan缩点,,,
#include#include #include #include #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 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 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 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 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 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] ed]) { q.push(p->ed); dis[p->ed]=dis[w]+cont[p->ed]; } } } int max=-1; for(i=1;i<=ans;i++) { if(max 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