训练指南 UVA - 11324（双连通分量 + 缩点+ 基础DP）

layout: post

title: 训练指南 UVA - 11324（双连通分量 + 缩点+ 基础DP）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 双连通分量

- 基础DP

- 图论

- 训练指南

The Largest Clique

UVA - 11324

题意

给一张有向图G，求一个结点数最大的结点集，使得该结点中任意两个结点 u 和 v满足：要么 u 可以到达 v，要么 v 可以到达 u（u 和 v 相互可达也可以）。

题解

同一个强连通分量中的点要么都选，要么不选。把强连通分量收缩点后得到SCC图，让每个SCC结点的权等于它的结点数，则题目转化为求SCC图上权最大的路径。所以转化成了dp求DAG上的最长路。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e3+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

vector<int>G[maxn],g[maxn];

int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt,sccnum[maxn];

stack<int>S;

void dfs(int u){

    pre[u]=lowlink[u]=++dfs_clock;

    S.push(u);

    for(int i=0;i<G[u].size();i++){

        int v=G[u][i];

        if(!pre[v]){

            dfs(v);

            lowlink[u]=min(lowlink[u],lowlink[v]);

        }

        else if(!sccno[v]){

            lowlink[u]=min(lowlink[u],pre[v]);

        }

    }

    if(lowlink[u]==pre[u]){

        scc_cnt++;

        for(;;){

            int x=S.top();S.pop();

            sccno[x]=scc_cnt;

            sccnum[scc_cnt]++;

            if(x==u)break;

        }

    }

}

void find_scc(int n){

    dfs_clock=scc_cnt=0;

    memset(sccno,0,sizeof(sccno));

    memset(pre,0,sizeof(pre));

    memset(sccnum,0,sizeof(sccnum));

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

        if(!pre[i])dfs(i);

}

int d[maxn];

int dp(int i){

    int &ans=d[i];

    if(ans>=0)return ans;

    ans=sccnum[i];

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

        int v=g[i][j];

        ans=max(ans,dp(v)+sccnum[i]);

    }

    return ans;

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int t;

   // freopen("input.txt","r",stdin);

    //freopen("output.txt","w",stdout);

    cin>>t;

    while(t--){

        int n,m;

        cin>>n>>m;

        for(int i=0;i<=n;i++)G[i].clear(),g[i].clear();

        int u,v;

        for(int i=0;i<m;i++){

            cin>>u>>v;

            u--;v--;

            G[u].push_back(v);

        }

        find_scc(n);

        memset(d,-1,sizeof(d));

        for(int u=0;u<n;u++)

        for(int i=0;i<G[u].size();i++){

            int v=G[u][i];

            if(sccno[u]!=sccno[v])

                g[sccno[u]].push_back(sccno[v]);

        }

        int ans=0;

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

            ans=max(ans,dp(i));

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

训练指南 UVA - 11324（双连通分量 + 缩点+ 基础DP）

The Largest Clique

题意

题解

最新文章

热门文章