2019-07-25 luogu P3627 [APIO2009]搶掠計劃 卡了三個小時，看了題解才作出來的（菜） 前驅知識： 壹~鄰接表存儲/遍歷 貳~SPFA跑最長路（<改>就行了） 叄~Tarjan縮點 壹.鄰接表儲存 兩個，add存無邊權，未縮點；build有邊權，已縮點。 貳.輸入 懶得開 ...
2019-07-25
luogu P3627 [APIO2009]搶掠計劃
卡了三個小時，看了題解才作出來的（菜）
前驅知識：
壹~鄰接表存儲/遍歷
貳~SPFA跑最長路（<改>就行了）
叄~Tarjan縮點
壹.鄰接表儲存
兩個，add存無邊權，未縮點；build有邊權，已縮點。
void add(int u,int v)
{
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void build(int u,int v,int w)
{
cnt++;
e[cnt].to=v;
e[cnt].val=w;
e[cnt].next=head[u];
head[u]=cnt;
}
貳.輸入
懶得開兩個head數組了，所以memset了。
cnt記得重置為零。
cnt=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
scanf("%d%d",&s,&p);
for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
叄.tarjan 縮點
void Tarjan(int x)
{
dfn[x]=low[x]=++total;
stk[++top]=x;vis[x]=true;
for(int i=head[x];i;i=e[i].next)
{
int t=e[i].to;
if(!dfn[t])
{
Tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(vis[t])
low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x])
{
tot++;
do{
int tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=false;
be[tp]=tot;
}while(stk[top--]!=x);
}//數組模擬棧
}
這裡我是用的數組模擬棧，首先int tp=stk[top]取出棧頂
sum表示縮完點後這個點的點權
不是很懂Tarjan的好好理解下Tarjan彈棧的部分再看這裡就懂了
懂Tarjan的模擬一下應該就懂了，每次彈棧時，所有被彈出的點都是縮完點後的一個點
即sum[tot]+=w[tp]，縮完點後的點權+=原點權
很好理解吧
不懂的說明你對Tarjan還是理解不到位……這篇題解不是講Tarjan的，樓下大佬應該有詳細講解。
然後vis[tp]=false表示tp已經出棧
g表示縮完點後每個點在哪個點中
即g[tp]=tot，tp這個點在縮完點後的第tot個點里
然後用棧頂和x比較，標準Tarjan操作
stk[top--]就相當於pop彈棧了
肆.Spfa跑最長路
void Spfa(int s)
{
for(int i=1;i<=tot;i++) dis[i]=0;
int bes=be[s];//不想認真想變數名了
q.push(bes);
vis[bes]=true;
dis[bes]=sum[bes];
while(!q.empty())
{
int h=q.front();q.pop();
vis[h]=false;
for(int i=head[h];i;i=e[i].next)
{
int t=e[i].to;
if(dis[t]<dis[h]+e[i].val)
{
dis[t]=dis[h]+e[i].val;
if(!vis[t])
{
q.push(t);
vis[t]=true;
}
}
}
}
}
起點邊權解決方法：
起點從s變為be[s]了，dis[s]不是0了
因為縮點
我們剛剛build建的圖是一張縮完點後的縮點圖，所以我們push起點的時候當然是push縮完點後s所在的點啊
為什麼呢？萬一s本身就在一個環里，push（s)的話問題就大了
所以我們把起點一律改成g[s]來操作
並且，我們把起點的dis值直接加上點權，這樣就不會漏掉起點點權了
而且放心，一開始更改dis值不會對後續鬆弛操作造成無法更改的影響，畢竟這是最長路
伍.main函數部分
for(int i=1;i<=m;i++)
if(be[u[i]]!=be[v[i]])
build(be[u[i]],be[v[i]],sum[be[v[i]]]);
這時候前面的u，v數組便起作用了
我們通過判斷u[i],v[i]是否在一個新點里，如果不在的話就build一條新邊，這樣就能建一個縮完點後的圖
！！！build：起點是u[i]所在的縮點，終點是v[i]所在的縮點（如果u[i]和v[i]在一個縮點里就不會執行build了），邊權是v[i]所在縮點的點權（sum）！！！
這樣，這張新圖就表明：從U走到V可以搶劫W的錢，錢數當然是縮點點權啊
但是-------------------------------------------------------------------------這樣每次把邊權設置為後頭那個縮點的點權，前頭那個點（起點）被忽略了，點權不就沒用了嗎？
對√的確有這個問題
但是在上一部分我們已經簡單粗暴の解決了
以下為AC碼：
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<queue>
#define maxn 500010
using namespace std;
struct edbee
{
int to,val,next;
} e[maxn];
int m,n,p,s,cnt,be[maxn],u[maxn],v[maxn],w[maxn],head[maxn],bar[maxn],dis[maxn],dfn[maxn],low[maxn],stk[maxn],sum[maxn];
bool vis[maxn];
queue <int> q;
int ans,top,tot,total;
void add(int u,int v)
{
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void build(int u,int v,int w)
{
cnt++;
e[cnt].to=v;
e[cnt].val=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void Tarjan(int x)
{
dfn[x]=low[x]=++total;
stk[++top]=x;vis[x]=true;
for(int i=head[x];i;i=e[i].next)
{
int t=e[i].to;
if(!dfn[t])
{
Tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(vis[t])
low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x])
{
tot++;
do{
int tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=false;
be[tp]=tot;
}while(stk[top--]!=x);
}
}
void Spfa(int s)
{
for(int i=1;i<=tot;i++) dis[i]=0;
int bes=be[s];
q.push(bes);
vis[bes]=true;
dis[bes]=sum[bes];
while(!q.empty())
{
int h=q.front();q.pop();
vis[h]=false;
for(int i=head[h];i;i=e[i].next)
{
int t=e[i].to;
if(dis[t]<dis[h]+e[i].val)
{
dis[t]=dis[h]+e[i].val;
if(!vis[t])
{
q.push(t);
vis[t]=true;
}
}
}
}
}
int main()
{
cnt=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
scanf("%d%d",&s,&p);
for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
for(int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
cnt=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++)
if(be[u[i]]!=be[v[i]])
build(be[u[i]],be[v[i]],sum[be[v[i]]]);
Spfa(s);
for(int i=1;i<=p;i++)
ans=max(ans,dis[be[bar[i]]]);
printf("%d",ans);
return 0;
}
謝謝你能看到這裡。
2019-07-25 22:35:43
以下為私貨，可以不看
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
REOL要出新專啦！！！
唱歌超好聽，人長得超好看的！！！
國內Apple music：https://music.apple.com/cn/album/1472096049?app=music再次謝謝你能看到這裡。
2019-07-2522:36:16
