训练指南 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;
}
上一篇:PHP + JS 实现大文件分割上传


下一篇:C# DESC加密