# 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;
bool vis[N],jiuba[N],suojb[N];
struct aaa
{
int to,nxt;
}bian[N],bianx[N];
{
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;
}
inline void addx(int a,int b)//After shrinking, the connecting block and the connecting block are edged.
{
bianx[++ecntx].to=b;
}
void tarjan(int u)//Standard tarjan
{
dfn[u]=low[u]=++tim;
stk[++tk]=u;vis[u]=1;
{
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
{
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;
{
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;
return jiyi[dian];//Return the maximum amount of money from this point;
}
int main()
{
int a,b;
for(int i=1;i<=m;i++)
{
//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++)
for(int i=1;i<=p;i++)