傳送門

題意：給你一個圖，每一個點可以獲得一個愉悅值，求能從某一個點出發走能得到的最大愉悅值。路徑為單項的，顯然不會加上負的。可以通過tanjar縮點從而形成DAG，再跑一個計劃搜索即可求出。

怎么縮點呢？就是將圖跑完，每一個強連通分量就是一個點，該縮點的值就是這個強連通分量中所有值大于0的點的和。

ac代碼：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
typedef long long ll;
using namespace std;
const int maxn=3e4+4;
const int maxnn=150005;
int n,m,t,top,sign,ans,cnt;
struct node
{int to,p;
}edge[maxnn];
int head[maxn];
int low[maxn],dfn[maxn],inStack[maxn],Stack[maxn];
int sum[maxn],dp[maxn],belong[maxn],val[maxn];
vector<int>v[maxn];
void add(int u,int v)
{edge[sign]=node{v,head[u]};head[u]=sign++;
}
void init()
{sign=t=cnt=ans=top=0;for(int i=0;i<=n;i++){v[i].clear();low[i]=dfn[i]=inStack[i]=sum[i]=0;dp[i]=head[i]=-1;}
}
void tanjar(int u)
{low[u]=dfn[u]=++t;Stack[++top]=u;inStack[u]=1;for(int i=head[u];i!=-1;i=edge[i].p){int v=edge[i].to;if(!dfn[v]){tanjar(v);low[u]=min(low[u],low[v]);}else if(inStack[v]){low[u]=min(low[u],dfn[v]);}}int x;if(low[u]==dfn[u]){cnt++;do{x=Stack[top--];inStack[x]=0;sum[cnt]+=val[x];//記錄某個強連通分量的值belong[x]=cnt;}while(u!=x);}
}
int dfs(int u)
{if(dp[u]!=-1)return dp[u];dp[u]=sum[u];int l=v[u].size();for(int i=0;i<l;i++){int e=v[u][i];dp[u]=max(dp[u],dp[e]+sum[u]);}return dp[u];
}
int main()
{int x,y;while(scanf("%d %d",&n,&m)!=EOF){init();for(int i=0;i<n;i++){scanf("%d",&val[i]);if(val[i]<0)val[i]=0;}while(m--){scanf("%d%d",&x,&y);add(x,y);}for(int i=0;i<n;i++){if(!dfn[i])tanjar(i);}for(int i=0;i<n;i++)//這就是建立一個新圖{for(int j=head[i];j!=-1;j=edge[j].p){int e=edge[j].to;if(belong[i]!=belong[e])v[belong[i]].push_back(belong[e]);}}for(int i=0;i<n;i++)ans=max(ans,dfs(i));printf("%d\n",ans);}return 0;
}

?

總結

以上是生活随笔為你收集整理的POJ - 3160 Father Christmas flymouse tanjar缩点构图+dfs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。