洛谷题解 P3627 【[APIO2009]抢掠计划】

图论 tarjan缩点+最短路的一道题

tarjan求强连通分量（为以后缩点打下良好的基础）

(如果不会tarjan的请点击这儿)

你需要的东西：

(1)、dfn[]，表示这个点在dfs时是第几个被搜到的。

(2)、low[]，表示这个点以及其子孙节点连的所有点中dfn最小的值

(3)、stack[]，表示当前所有可能能构成是强连通分量的点。

(4)、vis[]，表示一个点是否在stack中。

(5)、color[],记录每一个点强连通分量的编号。

(6)、deep,记录dfs树的深度

inline void tarjan(int now)

{

	dfn[now]=++deep;

	low[now]=deep;

	vis[now]=1;

	st.push(now);

	for(int i=0;i<ver[now].size();i++)

	{

		int x=ver[now][i];

		if(!dfn[x])

		{

			tarjan(x);

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

		}

		else

		{

			if(vis[x])

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

		}

	}

	if(dfn[now]==low[now])

	{

		color[now]=++sum;

		vis[now]=0;

		while(st.top()!=now)

		{

			color[st.top()]=sum;

			vis[st.top()]=0;

			st.pop();

		}

		st.pop();

	}

}

缩点（去除图中的环）

//重点：这里建新图是依托强连通分量的编号来建的

for(int i=1;i<=n;i++)

	{

		for(int j=0;j<ver[i].size();j++)

		{

			int x=ver[i][j];

			if(color[i]!=color[x])//如果不是属于同一个强连通分量中，那么就合并

			{

				g[color[i]].push_back(color[x]);

           //千万不能写成g[i].push_back(x);坑死我了

			}

		}

	}

//这一部分代码还可以适当优化...（想一想）

对于点权与酒馆的一些处理（方便求最短路）

for(int i=1;i<=n;i++)

	{

		ww[color[i]]+=w[i];//将这个强连通分量中所有的点权全部加起来

		if(tf[i])tf[color[i]]=1;//只要这个强连通分量中有一个结点有酒馆，那么就设定为有酒馆

	}

求最短路模板（然而实际是最长路）

//模板不做解释

inline void spfa()

{

	d[color[s]]=ww[color[s]];

	queue<int>q;

	q.push(color[s]);

	while(q.size())

	{

		int now=q.front();

		q.pop();

		for(int i=0;i<g[now].size();i++)

		{

			int x=g[now][i];

			if(d[now]+ww[x]>d[x])

			{

				d[x]=d[now]+ww[x];

				q.push(x);

			}

		}

	}

}

所以...

在所有有酒馆的节点中选一个最大值输出就好了

for(int i=1;i<=sum;i++)

	{

		//cout<<d[i]<<" ";

		if(tf[i])ans=max(ans,d[i]);

	}

完整代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=500000+10;

int n,m;

vector<int>ver[MAXN];

vector<int>g[MAXN];

int w[MAXN],ww[MAXN];

bool tf[MAXN];

int s,p,ans=0;

int dfn[MAXN],color[MAXN],low[MAXN];

int deep,sum;

bool vis[MAXN];

int d[MAXN];

stack<int>st;

inline int read()

{

	int tot=0;

	char c=getchar();

	while(c<'0'||c>'9')

		c=getchar();

	while(c>='0'&&c<='9')

	{

		tot=tot*10+c-'0';

		c=getchar();

	}

	return tot;

}

inline void tarjan(int now)

{

	dfn[now]=++deep;

	low[now]=deep;

	vis[now]=1;

	st.push(now);

	for(int i=0;i<ver[now].size();i++)

	{

		int x=ver[now][i];

		if(!dfn[x])

		{

			tarjan(x);

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

		}

		else

		{

			if(vis[x])

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

		}

	}

	if(dfn[now]==low[now])

	{

		color[now]=++sum;

		vis[now]=0;

		while(st.top()!=now)

		{

			color[st.top()]=sum;

			vis[st.top()]=0;

			st.pop();

		}

		st.pop();

	}

}

inline void spfa()

{

	d[color[s]]=ww[color[s]];

	queue<int>q;

	q.push(color[s]);

	while(q.size())

	{

		int now=q.front();

		q.pop();

		for(int i=0;i<g[now].size();i++)

		{

			int x=g[now][i];

			if(d[now]+ww[x]>d[x])

			{

				d[x]=d[now]+ww[x];

				q.push(x);

			}

		}

	}

}

int main()

{

	//freopen("testdata.in","r",stdin);

	n=read();m=read();

	for(int i=1;i<=m;i++)

	{

		int x=read(),y=read();

		ver[x].push_back(y);

	}

	for(int i=1;i<=n;i++)

		w[i]=read();

	s=read();p=read();

	for(int i=1;i<=p;i++)

	{

		int x=read();

		tf[x]=1;

	}

	for(int i=1;i<=n;i++)

	{

		if(!dfn[i])

			tarjan(i);

	}

	/*cout<<endl;

	for(int i=1;i<=n;i++)

		cout<<color[i]<<" ";

	cout<<endl;*/

	for(int i=1;i<=n;i++)

	{

		for(int j=0;j<ver[i].size();j++)

		{

			int x=ver[i][j];

			if(color[i]!=color[x])

			{

				//cout<<i<<" "<<x<<" "<<color[i]<<" "<<color[x]<<endl;

				g[color[i]].push_back(color[x]);

			}

		}

	}

	for(int i=1;i<=n;i++)

	{

		ww[color[i]]+=w[i];

		if(tf[i])tf[color[i]]=1;

	}

	/*cout<<color[s]<<endl;

	cout<<endl;

	for(int i=1;i<=sum;i++)

	{

		for(int j=0;j<g[i].size();j++)cout<<i<<" "<<g[i][j]<<"\n";

	}

	cout<<endl;

	for(int i=1;i<=sum;i++)

		cout<<ww[i]<<" ";cout<<endl;

	for(int i=1;i<=sum;i++)

		cout<<tf[i]<<" ";cout<<endl;

	cout<<ww[color[s]]<<endl;*/

	spfa();

	for(int i=1;i<=sum;i++)

	{

		//cout<<d[i]<<" ";

		if(tf[i])ans=max(ans,d[i]);

	}

	//cout<<endl;

	cout<<ans<<endl;

	return 0;

}

巴特西

洛谷题解 P3627 【[APIO2009]抢掠计划】

图论 tarjan缩点+最短路的一道题

最新文章

热门文章

巴特西

洛谷 题解 P3627 【[APIO2009]抢掠计划】

图论 tarjan缩点+最短路 的一道题

最新文章

热门文章

洛谷题解 P3627 【[APIO2009]抢掠计划】

图论 tarjan缩点+最短路的一道题