2 条题解

  • 0
    @ 2025-10-8 17:03:28

    这道题的图可能存在负权边或负环，因此不能使用Dijkstra算法（Dijkstra算法适用于非负权图，无法处理负权边或负环）。以下是三种解法，其中前两种是基于强连通分量（SCC）缩点后在DAG上进行处理，第三种是直接对DAG进行拓扑排序和动态规划。

    86.5分的Dijkstra解法

    #include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> G1[N], G2[N];
int tsp, cnt, dfn[N], low[N], scc[N], W[N];
stack<int> stk;
bool instk[N];
int w[N], bar[N], dis[N];

void tarjan(int x) {
    dfn[x] = low[x] = ++tsp;
    stk.push(x);
    instk[x] = true;
    for (int y : G1[x]) {
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (instk[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        cnt++;
        for (int z = -1; z != x;) {
            z = stk.top();
            stk.pop();
            instk[z] = false;
            scc[z] = cnt;
            W[cnt] += w[z];
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        G1[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    int st, p;
    scanf("%d%d", &st, &p);
    for (int i = 1; i <= p; i++) scanf("%d", &bar[i]);

    tsp = cnt = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(scc, 0, sizeof(scc));
    memset(instk, 0, sizeof(instk));
    memset(W, 0, sizeof(W));
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    map<pair<int, int>, bool> mp;
    for (int i = 1; i <= n; i++) {
        for (int j : G1[i]) {
            int x = scc[i], y = scc[j];
            if (x != y && !mp[{x, y}]) {
                G2[x].push_back(y);
                mp[{x, y}] = 1;
            }
        }
    }

    st = scc[st];
    vector<int> dis(cnt + 1);
    dis[st] = W[st];
    vector<bool> vis(cnt + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> q;
    q.push({dis[st], st});
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int y : G2[x]) {
            if (dis[y] < dis[x] + W[y]) {
                dis[y] = dis[x] + W[y];
                q.push({dis[y], y});
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= p; i++) {
        ans = max(ans, dis[scc[bar[i]]]);
    }
    printf("%d\n", ans);
    return 0;
}

    100分的spfa解法

    #include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> G1[N], G2[N];
int tsp, cnt, dfn[N], low[N], scc[N], W[N];
stack<int> stk;
bool instk[N];
int w[N], bar[N], dis[N];

void tarjan(int x) {
    dfn[x] = low[x] = ++tsp;
    stk.push(x);
    instk[x] = true;
    for (int y : G1[x]) {
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (instk[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        cnt++;
        for (int z = -1; z != x;) {
            z = stk.top();
            stk.pop();
            instk[z] = false;
            scc[z] = cnt;
            W[cnt] += w[z];
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        G1[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    int st, p;
    scanf("%d%d", &st, &p);
    for (int i = 1; i <= p; i++) scanf("%d", &bar[i]);

    tsp = cnt = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(scc, 0, sizeof(scc));
    memset(instk, 0, sizeof(instk));
    memset(W, 0, sizeof(W));
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    map<pair<int, int>, bool> mp;
    for (int i = 1; i <= n; i++) {
        for (int j : G1[i]) {
            int x = scc[i], y = scc[j];
            if (x != y && !mp[{x, y}]) {
                G2[x].push_back(y);
                mp[{x, y}] = 1;
            }
        }
    }

    st = scc[st];
    vector<int> dis(cnt + 1);
    dis[st] = W[st];
    vector<bool> vis(cnt + 1);
    vis[st] = 1;
    queue<int> q;
    q.push(st);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int y : G2[x]) {
            if (dis[y] < dis[x] + W[y]) {
                dis[y] = dis[x] + W[y];
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= p; i++) {
        ans = max(ans, dis[scc[bar[i]]]);
    }
    printf("%d\n", ans);
    return 0;
}

    100分的Toposort DAG dp解法

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define lowbit(x) (x & -x)
#define pii pair<int, int>
#define N 500010
#define M 1000010
namespace graph {
    int head[N], nxt[M], to[M], rh[N];
    int cnt_edge;
    inline void connect_head(const int &x, const int &y, int *h = head) {
        ++cnt_edge;
        nxt[cnt_edge] = h[x];
        to[cnt_edge] = y;
        h[x] = cnt_edge;
    }
}
using namespace graph;
int n, m;
int dfn[N], low[N], dfc;
int sta[N], *top;
bool ins[N];
int bel[N], cnt, u, v;
ll s[N]; // 每个scc的总和
int ind[N], tmp, p, sn;
ll a[N];
ll dp[N], ans;
int q[N], *front, *tail;
bool b[N]; // 有酒吧
bool bn[N];
bool used[N]; // 经过s得到的点可以有used

void tarjan(const int &x) {
    dfn[x] = low[x] = ++dfc;
    ins[x] = 1;
    *(++top) = x;
    for (int edg = head[x]; edg; edg = nxt[edg]) {
        if (!dfn[to[edg]]) {
            tarjan(to[edg]);
            low[x] = min(low[x], low[to[edg]]);
        } else if (ins[to[edg]]) {
            low[x] = min(low[x], dfn[to[edg]]);
        }
    }
    if (dfn[x] != low[x]) return;
    int last = 0;
    ++cnt;
    while (last != x) { // 出栈直到x
        last = *top;
        --top;
        bel[last] = cnt;
        s[cnt] += a[last];
        ins[last] = 0;
    }
}

void input() {
    scanf("%d%d", &n, &m);
    cnt_edge = 0;
    memset(head, 0, sizeof(head));
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        connect_head(u, v);
    }
    top = sta;
    for (int i = 1; i <= n; i++) scanf("%lld", a + i);
    scanf("%d%d", &sn, &p);
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= p; i++) {
        scanf("%d", &tmp);
        b[tmp] = 1;
    }
}

void solve() {
    dfc = cnt = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(ins, 0, sizeof(ins));
    memset(bel, 0, sizeof(bel));
    memset(s, 0, sizeof(s));
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 建立DAG
    memset(ind, 0, sizeof(ind));
    cnt_edge = 0;
    memset(rh, 0, sizeof(rh));
    memset(bn, 0, sizeof(bn));
    for (int i = 1; i <= n; i++) {
        if (b[i]) bn[bel[i]] = 1;
        for (int edg = head[i]; edg; edg = nxt[edg]) {
            int x = bel[i], y = bel[to[edg]];
            if (x == y) continue;
            ++ind[y];
            connect_head(x, y, rh);
        }
    }

    // DAG拓扑排序+dp
    front = tail = q;
    memset(dp, 0, sizeof(dp));
    memset(used, 0, sizeof(used));
    ans = 0;
    for (int i = 1; i <= cnt; i++) {
        if (!ind[i]) {
            *(tail++) = i;
        }
    }
    used[bel[sn]] = true;
    dp[bel[sn]] = s[bel[sn]];
    while (front != tail) {
        int x = *front++;
        if (bn[x]) ans = max(ans, dp[x]);
        for (int edg = rh[x]; edg; edg = nxt[edg]) {
            int y = to[edg];
            if (used[x]) {
                used[y] = true;
                dp[y] = max(dp[y], dp[x] + s[y]);
            }
            if (--ind[y] == 0) {
                *(tail++) = y;
            }
        }
    }
}

void output() {
    printf("%lld\n", ans);
}

int main() {
    input();
    solve();
    output();
    return 0;
}
    • 0
      @ 2025-10-8 17:03:03

      这道题要想清楚为什么不能用Dijkstra？
      86.5分的Dijkstra：

      #include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>G1[N],G2[N];
int tsp,cnt,dfn[N],low[N],scc[N],W[N];
stack<int>stk;bool instk[N];
int w[N],bar[N],dis[N];

void tarjan(int x)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);instk[x]=True;
    for(int y:G1[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=-1;z!=x;)
        {
            z=stk.top();stk.pop();instk[z]=False;
            scc[z]=cnt;W[cnt]+=w[z];
        }
    }
}

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G1[x].push_back(y);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    int st,p;scanf("%d%d",&st,&p);
    for(int i=1;i<=p;i++) scanf("%d",&bar[i]);

    tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
    memset(W,0,sizeof(W));
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);

    map<pair<int,int>,bool>mp;
    for(int i=1;i<=n;i++)for(int j:G1[i])
    {
        int x=scc[i],y=scc[j];
        if(x!=y && !mp[{x,y}])G2[x].push_back(y),mp[{x,y}]=1;
    }
      			
    st=scc[st];
    vector<int>dis(cnt+1);dis[st]=W[st];
    vector<bool>vis(cnt+1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>> >q;q.push({dis[st],st});
    while(!q.empty())
    {
        int x=q.top().second;q.pop();if(vis[x]==1)continue;
        vis[x]=1;
        for(int y:G2[x])
        {
            if(dis[y]<dis[x]+W[y])
            {
                dis[y]=dis[x]+W[y];
                q.push({dis[y],y});
            }
        }
    }
    int ans=0;
    for(int i=1;i<=p;i++)ans=max(ans,dis[scc[bar[i]]]);
    printf("%d\n",ans);
    return 0;
}

      100分的spfa: 
      #include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>G1[N],G2[N];
int tsp,cnt,dfn[N],low[N],scc[N],W[N];
stack<int>stk;bool instk[N];
int w[N],bar[N],dis[N];

      void tarjan(int x)
{
dfn[x]=low[x]=++tsp;
stk.push(x);instk[x]=True;
for(int y:G1[x])
{
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(instk[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
cnt++;
for(int z=-1;z!=x;)
{
z=stk.top();stk.pop();instk[z]=False;
scc[z]=cnt;W[cnt]+=w[z];
}
}
}
      

      int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G1[x].push_back(y);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
int st,p;scanf("%d%d",&st,&p);
for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
      

      tsp=cnt=0;memset(dfn&#44;0&#44;sizeof(dfn));memset(low&#44;0&#44;sizeof(low));
memset(scc&#44;0&#44;sizeof(scc));memset(instk&#44;0&#44;sizeof(instk));
memset(W&#44;0&#44;sizeof(W));
for(int i=1;i&lt;=n;i++)if(!dfn[i])tarjan(i);

map&lt;pair&lt;int&#44;int&gt;&#44;bool&gt;mp;
for(int i=1;i&lt;=n;i++)for(int j:G1[i])
{
    int x=scc[i]&#44;y=scc[j];
    if(x!=y &amp;&amp; !mp[{x&#44;y}])G2[x].push_back(y)&#44;mp[{x&#44;y}]=1;
}
  			
st=scc[st];
vector&lt;int&gt;dis(cnt+1);dis[st]=W[st];
vector&lt;bool&gt;vis(cnt+1);vis[st]=1;
queue&lt;int&gt;q;q.push(st);
while(!q.empty())
{
    int x=q.front();q.pop();vis[x]=0;
    for(int y:G2[x])
    {
        if(dis[y]&lt;dis[x]+W[y])
        {
            dis[y]=dis[x]+W[y];
            if(!vis[y])q.push(y)&#44;vis[y]=1;
        }
    }
}
int ans=0;
for(int i=1;i&lt;=p;i++)ans=max(ans&#44;dis[scc[bar[i]]]);
printf("%d\n"&#44;ans);
return 0;

      

      }

      100 分的 Toposort DAG dp：</p> 
      #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define N 500010
#define M 1000010
namespace graph{
    int head[N],nxt[M],to[M],rh[N];
    int cnt_edge;
    inline void connect_head(const int &x,const int &y,int *h = head){
        ++cnt_edge;
        nxt[cnt_edge] = h[x];
        to[cnt_edge] = y;
        h[x] = cnt_edge;
    }
}
using namespace graph;
int n,m;
int dfn[N],low[N],dfc;
int sta[N],*top;
bool ins[N];
int bel[N],cnt,u,v;
ll s[N];// 每个 scc 的总和
int ind[N],tmp,p,sn;
ll a[N];
ll dp[N],ans;
int q[N],*front,*tail;
bool b[N];// 有酒吧
bool bn[N];
bool used[N];// 经过 s 得到的点可以有 used

void tarjan(const int &x){
    dfn[x] = low[x] = ++dfc;
    ins[x] = 1;
    *(++top) = x;
    for(int edg = head[x];edg;edg = nxt[edg]){
        if(!dfn[to[edg]]){
            tarjan(to[edg]);
            low[x] = min(low[x],low[to[edg]]);
        }else if(ins[to[edg]])low[x] = min(low[x],dfn[to[edg]]);
    }
    if(dfn[x] != low[x])return ;
    int last = 0;
    ++cnt;
    while(last != x){
        last = *top;
        --top;
        bel[last] = cnt;
        s[cnt] += a[last];
        ins[last] = 0;
    }
}

// 输入函数
void input(){
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d",&u,&v);
        connect_head(u,v);
    }
    top = sta;
    for(int i = 1;i <= n;++i)scanf("%lld",a+i);
    scanf("%d%d",&sn,&p);
    for(int i = 1;i <= p;++i){
        scanf("%d",&tmp);
        b[tmp] = 1;
    }
}

// 处理函数
void solve(){
    for(int i = 1;i <= n;++i)if(!dfn[i])tarjan(i);
    // 建立 dag
    for(int i = 1;i <= n;++i){
        if(b[i])bn[bel[i]] = 1;
        for(int edg = head[i];edg;edg = nxt[edg]){
            if(bel[i] == bel[to[edg]])continue;
            ++ind[bel[to[edg]]];
            connect_head(bel[i],bel[to[edg]],rh);
        }
    }
    // dagdp
    front = tail = q;
    for(int i = 1;i <= cnt;++i)if(!ind[i])*(tail++) = i;
    used[bel[sn]] = 1;
    int x;
    while(front != tail){
        x = *front;
        ++front;
        if(used[x])dp[x] += s[x];
        // printf("x = %d used = %d b = %d dp = %lld\n",x,used[x],bn[x],dp[x]);
        if(bn[x])ans = max(dp[x],ans);
        for(int edg = rh[x];edg;edg = nxt[edg]){
            --ind[to[edg]];
            if(used[x]){
                used[to[edg]] = 1;
                dp[to[edg]] = max(dp[to[edg]],dp[x]);
            }
            if(!ind[to[edg]])*(tail++) = to[edg];
        }
    }
}

// 输出函数
void output(){
    printf("%lld",ans);
}

// 主函数
int main(){
    input();
    solve();
    output();
    return 0;
}
      • 1

      【缩点】[APIO2009] 抢掠计划（好题）

      信息

      ID
      2832
      时间
      5000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      148
      已通过
      20
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 6ms
      4. Powered by Hydro v5.0.1 Community