UVA11324 The Lagest Lique(SCC缩点+DP)

Given a directed graph G, con- sider the following transformation. First, create a new graph T(G) to have the same vertex set as G. Cre- ate a directed edge between two vertices u and v in T(G) if and only if there is a path between u and v in G that follows the directed edges only in the forward direction. This graph T(G) is often called the tran- sitive closure of G. We define a clique in a directed graph as a set of vertices U such that for any two vertices u and v in U, there is a directed edge either from u to v or from v to u (or both). The size of a clique is the number of vertices in the clique. Input The number of cases is given on the first line of input. Each test case describes a graph G. It begins with a line of two integers n and m, where 0 ≤ n ≤ 1000 is the number of vertices of G and 0 ≤ m ≤ 50, 000 is the number of directed edges of G. The vertices of G are numbered from 1 to n. The following m lines contain two distinct integers u and v between 1 and n which define a directed edge from u to v in G. Output For each test case, output a single integer that is the size of the largest clique in T(G). Sample Input 1 5 5 1 2 2 3 3 1 4 1 5 2 Sample Output 4The

题解：让你求至少单向可以连通的最多的节点数；

我们可以用个SCC缩点以后，然后进行记忆化搜索+DP，从没一个“点”开始，求最大值即可；

dp[x]=max(dp[x],sz[x]+DP(G[x][i]); DP为搜索函数，搜索点x的最多节点数；sz[x]为点“x”代表的点集的个数；

参考代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int t,n,m,u,v,times,blocks;

 int dfn[maxn],lowv[maxn],belong[maxn],ins[maxn],sz[maxn];

 int dp[maxn];

 struct Node{

     int u,v;

     Node(int _u,int _v): u(_u),v(_v) { }

 };

 vector<Node> edges;

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

 stack<int> st;

 void Addedge(int u,int v)

 {

     G[u].push_back(edges.size());

     edges.push_back(Node(u,v));

 }

 void Init()

 {

     times=blocks=;

     memset(dp,-,sizeof dp);

     memset(dfn,,sizeof dfn);

     memset(lowv,,sizeof lowv);

     memset(sz,,sizeof sz);

     memset(ins,,sizeof ins);

     memset(belong,,sizeof belong);

     while(!st.empty()) st.pop();

     edges.clear();

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

 }

 void Tarjan(int u)

 {

     dfn[u]=lowv[u]=++times;

     st.push(u);

     ins[u]=;

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

     {

         int v=edges[G[u][i]].v;

         if(!dfn[v]) Tarjan(v),lowv[u]=min(lowv[u],lowv[v]);

         else if(ins[v]) lowv[u]=min(lowv[u],dfn[v]);

     }

     if(dfn[u]==lowv[u])

     {

         ++blocks;

         int v;

         do

         {

             v=st.top(); st.pop();

             ins[v]=;

             belong[v]=blocks;

             sz[blocks]++;

         } while(u!=v);

     }

 }

 int DP(int x)

 {

     if(dp[x]>) return dp[x];

     dp[x]=sz[x];

     for(int i=;i<GG[x].size();i++) dp[x]=max(dp[x],DP(GG[x][i])+sz[x]);

     return dp[x];

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin>>t;

     while(t--)

     {

         cin>>n>>m;

         Init();

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

         {

             cin>>u>>v;

             Addedge(u,v);

         }

         for(int i=;i<=n;i++) if(!dfn[i]) Tarjan(i);

         for(int i=;i<=n;i++) GG[i].clear();

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

         {

             for(int j=;j<G[i].size();j++)

             {

                 if(belong[i]!=belong[edges[G[i][j]].v])

                     GG[belong[i]].push_back(belong[edges[G[i][j]].v]);

             }

         }

         int ans=;

         for(int i=;i<=blocks;i++) ans=max(ans,DP(i));

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

UVA11324 The Lagest Lique(SCC缩点+DP)

最新文章

热门文章