Problem solving P3627 [[APIO2009] looting plan]

The idea in front of this problem is the same as other solutions, which are all tarjan contractions. Then it is to ask for the maximum value of gold coins. I use memory search to express how much money can be stolen from the connection block numbered I with jiyi[i]. When I search, if I encounter a point that has been searched (I know how much money can be stolen from that point), I will directly return. Because each point of memory search will only be traversed once, the complexity of memory search should be O(n).

In addition, my code style is a little strange. Let's explain first: stk[tk] is the pointer of the stack and the stack (tarjan), num is the number of connecting blocks, tim timestamp, shuyu[i] is which connecting block point I belongs to, he [] is how much money there is in a connecting block, vis [] is whether a point is in the stack, jiuba [] is whether a point has a bar, suojb [] is the reduced connecting block. Is there a bar in. bian[],head[],ecnt are all the edges in the graph before the shrink point. If there is suffix x after the shrink point, it means the edge in the new graph after the shrink point.

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,ecnt,s,p,tk,num,tim,ecntx,ans;
int qian[N],head[N],dfn[N],low[N],stk[N],shuyu[N],he[N],headx[N],jiyi[N];
bool vis[N],jiuba[N],suojb[N];
struct aaa
{
	int to,nxt;
}bian[N],bianx[N];
inline int read()//Standard fast reading
{
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return f?-x:x;
}
inline void add(int a,int b)//Chain forward star edge;
{
	bian[++ecnt].to=b;
	bian[ecnt].nxt=head[a];
	head[a]=ecnt;
}
inline void addx(int a,int b)//After shrinking, the connecting block and the connecting block are edged.
{
	bianx[++ecntx].to=b;
	bianx[ecntx].nxt=headx[a];
	headx[a]=ecntx;
}
void tarjan(int u)//Standard tarjan
{
	dfn[u]=low[u]=++tim;
	stk[++tk]=u;vis[u]=1;
	for(int i=head[u];i;i=bian[i].nxt)
	{
		int v=bian[i].to;
		if(!dfn[v])
			tarjan(v),low[u]=min(low[u],low[v]);
		else if(vis[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		num++;
		while(stk[tk]!=u)
		{
			shuyu[stk[tk]]=num;//The connection block to which the record point belongs;
			vis[stk[tk]]=0;
			stk[tk]=0;tk--;
		}
		shuyu[stk[tk]]=num;//At this time, there is another point on the top of the stack in this connection block, and it will be executed again.
		vis[stk[tk]]=0;
		stk[tk]=0;tk--;
	}
}
void suo()//Shrinkage point;
{
	for(int i=1;i<=n;i++)
	{
		he[shuyu[i]]+=qian[i];//Update the total amount of money in each Unicom block
		if(jiuba[i])suojb[shuyu[i]]=1;Update whether there is a bar in the Unicom block
		for(int j=head[i];j;j=bian[j].nxt)
		{
			int v=bian[j].to;
			if(shuyu[i]!=shuyu[v])
				addx(shuyu[i],shuyu[v]);//If the starting point and the ending point are not in the same connecting block, the edge is added between the two connecting blocks;
		}
	}
}
int dfs(int dian)//If the new graph is a directed acyclic graph, then we can get dfs.
{
	if(jiyi[dian])return jiyi[dian];//If the link block has been searched, that is, we know the maximum amount of money from this point, we will return directly;
	if(headx[dian]==0&&suojb[dian]==1)//If the connection block is 0 and there is a bar here, you can stop here and return the total amount of the connection block.
	{
		jiyi[dian]=he[dian];
		return he[dian];
	}
	if(headx[dian]==0&&suojb[dian]==0)return 0;//If the connection block is 0 but there is no bar, it can't stop here, so its contribution to the answer is 0;
	for(int i=headx[dian];i;i=bianx[i].nxt)
	{
		jiyi[dian]=max(jiyi[dian],dfs(bianx[i].to));//One of the multiple outputs of a connection block is the largest;
	}
	if(jiyi[dian]==0&&suojb[dian]==0)return 0;
   	//Note: at this time, we think less about a situation. If there is no bar in a series of points on a path, then the robber can't stop on this path, but if there is no bar, the program will still follow this path; plus this sentence, if there is no bar at the back of the point and there is no bar here, then its contribution to the answer is 0, direct return 0;
	jiyi[dian]+=he[dian];//Add your own point weight to the memory array;
	return jiyi[dian];//Return the maximum amount of money from this point;
}
int main()
{
	int a,b;
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		a=read();b=read();
		add(a,b);
                //There's a strange error. You can't write add (read()); otherwise, it will go wrong. I don't know why.
	}
	for(int i=1;i<=n;i++)
		qian[i]=read();
	s=read();p=read();
	for(int i=1;i<=p;i++)
		jiuba[read()]=1;
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	suo();
	ans=dfs(shuyu[s]);
	cout<<ans;
	return 0;
}

Keywords: PHP less

Added by JoeF on Fri, 18 Oct 2019 23:00:48 +0300