縮點，就是把一張有向有環(huán)圖中的環(huán)縮成一個個點，形成一個有向無環(huán)圖。

首先我介紹一下為什么這題要縮點（有人肯定覺得這是放屁，這不就是縮點的模板題嗎？但我們不能這么想，考試的時候不會有人告訴你打什么板上去吧）

根據(jù)題目意思，我們只需要找出一條點權(quán)最大的路徑就行了，不限制點的個數(shù)。那么考慮對于一個環(huán)上的點被選擇了，一整條環(huán)是不是應(yīng)該都被選擇，這一定很優(yōu)，能選干嘛不選。很關(guān)鍵的是題目還允許我們重復經(jīng)過某條邊或者某個點，我們就不需要考慮其他了。因此整個環(huán)實際上可以看成一個點（選了其中一個點就應(yīng)該選其他的點）

那么就正式開始縮環(huán)為點了。當然了，首先肯定是找環(huán)，為大家推薦兩篇博客（不是我宣傳，這兩篇博客也只是我找的[] (http://blog.csdn.net/acmmmm/article/details/16361033)）[](http://blog.csdn.net/sentimental_dog/article/details/53790582)

希望博客被我轉(zhuǎn)載的博主不要介意。

看看這兩篇博客，我覺得大家就有了一個基本認識了。在縮點操作中，最重要的是維護三個東西，它們在我代碼里分別是stac（棧）（ps：之所以不加k是因為萬能頭文件的荼毒），dfn（時間戳），low(夠追溯到的最早的棧中節(jié)點的次序號)，詳細的解釋在代碼注釋里。

下面就是考慮對這三個東西的運用。詳細參考博客（博客帶圖），需要注意的是，當dfn[u]==low[u]時，表明u一定是環(huán)上的一點，且環(huán)上的其他點就是u的子樹。為什么呢？看代碼
low[x]=dfn[x]=++tim;

low[x]=min(low[x],low[v]);

我截取了兩句代碼，第一句是對點x的low，dfn的初始化。在之后的操作中,low[x]始終取自己子樹low[v]的較小值，那么什么情況會使得dfn[u]又“重新”和low[u]相等呢，就是在u的子樹中有一條邊（就是博客1中的后向邊）直接指回了u。這樣不就是形成了一個環(huán)了嗎？

之后就是把環(huán)上所有的點的sd都變成這個u，即用u代替整個環(huán)，并把權(quán)值集中在u上

還有值得注意的，這個棧表示的究竟是什么？（這個在博客1中也有），根據(jù)我的理解表示的是當前搜索的一條鏈上的一個個點吧。

下面我附上代碼先

#include<bits/stdc++.h>
using namespace std;const int maxn=10000+15;
int n,m,sum,tim,top,s;
int p[maxn],head[maxn],sd[maxn],dfn[maxn],low[maxn];//DFN(u)為節(jié)點u搜索被搜索到時的次序編號(時間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點的次序號 
int stac[maxn],vis[maxn];//棧只為了表示此時是否有父子關(guān)系 
int h[maxn],in[maxn],dist[maxn];
struct EDGE
{int to;int next;int from;
}edge[maxn*10],ed[maxn*10];
void add(int x,int y)
{edge[++sum].next=head[x];edge[sum].from=x;edge[sum].to=y;head[x]=sum;
}
void tarjan(int x)
{low[x]=dfn[x]=++tim;stac[++top]=x;vis[x]=1;for (int i=head[x];i;i=edge[i].next){int v=edge[i].to;if (!dfn[v]) {tarjan(v);low[x]=min(low[x],low[v]);}else if (vis[v]){low[x]=min(low[x],low[v]);}}if (dfn[x]==low[x]){int y;while (y=stac[top--]){sd[y]=x;vis[y]=0;if (x==y) break;p[x]+=p[y];}}
}
int topo()
{queue <int> q;int tot=0;for (int i=1;i<=n;i++)if (sd[i]==i&&!in[i]){q.push(i);dist[i]=p[i];} while (!q.empty()){int k=q.front();q.pop();for (int i=h[k];i;i=ed[i].next){int v=ed[i].to;dist[v]=max(dist[v],dist[k]+p[v]);in[v]--;if (in[v]==0) q.push(v);}}int ans=0;for (int i=1;i<=n;i++)ans=max(ans,dist[i]);return ans;
}
int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&p[i]);for (int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);}for (int i=1;i<=n;i++)if (!dfn[i]) tarjan(i);for (int i=1;i<=m;i++){int x=sd[edge[i].from],y=sd[edge[i].to];if (x!=y){ed[++s].next=h[x];ed[s].to=y;ed[s].from=x;h[x]=s;in[y]++;}}printf("%d",topo());return 0;
}

在處理了環(huán)后，我們就重新建立一張圖，以每個環(huán)為節(jié)點（孤立一個點也算也算環(huán)的，其實也就是強聯(lián)通分量了）。在這張圖中我們要dp，顯然對于任意邊<u,v>,dp[v]=max(dp[v],dp[u]+p[v])，p[v]是v是這個環(huán)的總權(quán)值。

那么怎么解決無后效性問題呢？答案就是拓撲排序，至于為什么，在我的另一篇題解里我有提及。這下我有安利嫌疑了，但我還是希望大家去看一看，下面我附上鏈接。

這也是一篇題解，其實主要講的就是拓撲排序解決DP的無后效性問題了

轉(zhuǎn)載于:https://www.cnblogs.com/xxzh/p/9154060.html

總結(jié)

以上是生活随笔為你收集整理的图论之tarjan缩点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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