UVA11324 The Largest Clique(DP+缩点)

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

分析：”同一个强连通分量中的点要么都选，要么不选。把强连通分量收缩点后得到SCC图，让每个SCC结点的权等于它的结点数，则题目转化为求SCC图上权最大的路径。由于SCC图是一个 DAG，可以用动态规划求解。“

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<cstdlib>
  6 #include<cstring>
  7 #include<cmath>
  8 #include<stack>
  9 #include<vector>
 10 #define clc(a,b) memset(a,b,sizeof(a))
 11 using namespace std;
 12 const double eps=1e-8;
 13 const double pi=acos(-1);
 14 const int maxn=1010;
 15 using namespace std;
 16 
 17 vector<int> G[maxn];
 18 int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
 19 stack<int> S;
 20 
 21 void dfs(int u)
 22 {
 23     pre[u] = lowlink[u] = ++dfs_clock;
 24     S.push(u);
 25     for(int i = 0; i < G[u].size(); i++)
 26     {
 27         int v = G[u][i];
 28         if(!pre[v])
 29         {
 30             dfs(v);
 31             lowlink[u] = min(lowlink[u], lowlink[v]);
 32         }
 33         else if(!sccno[v])
 34         {
 35             lowlink[u] = min(lowlink[u], pre[v]);
 36         }
 37     }
 38     if(lowlink[u] == pre[u])
 39     {
 40         scc_cnt++;
 41         for(;;)
 42         {
 43             int x = S.top();
 44             S.pop();
 45             sccno[x] = scc_cnt;
 46             if(x == u) break;
 47         }
 48     }
 49 }
 50 
 51 void find_scc(int n)
 52 {
 53     dfs_clock = scc_cnt = 0;
 54     memset(sccno, 0, sizeof(sccno));
 55     memset(pre, 0, sizeof(pre));
 56     for(int i = 0; i < n; i++)
 57         if(!pre[i]) dfs(i);
 58 }
 59 
 60 int sizee[maxn], TG[maxn][maxn];
 61 int d[maxn];
 62 int dp(int u)
 63 {
 64     int& ans = d[u];
 65     if(ans >= 0) return ans;
 66     ans = sizee[u];
 67     for(int v = 1; v <= scc_cnt; v++)
 68         if(u != v && TG[u][v]) ans = max(ans, dp(v) + sizee[u]);
 69     return ans;
 70 }
 71 
 72 int main()
 73 {
 74     int T, n, m;
 75     scanf("%d", &T);
 76     while(T--)
 77     {
 78         scanf("%d%d", &n, &m);
 79         for(int i = 0; i < n; i++) G[i].clear();
 80         for(int i = 0; i < m; i++)
 81         {
 82             int u, v;
 83             scanf("%d%d", &u, &v);
 84             u--;
 85             v--;
 86             G[u].push_back(v);
 87         }
 88 
 89         find_scc(n); // 找强连通分量
 90 
 91         memset(TG, 0, sizeof(TG));
 92         memset(sizee, 0, sizeof(sizee));
 93         for(int i = 0; i < n; i++)
 94         {
 95             sizee[sccno[i]]++; // 累加强连通分量大小（结点数）
 96             for(int j = 0; j < G[i].size(); j++)
 97                 TG[sccno[i]][sccno[G[i][j]]] = 1; // 构造SCC图
 98         }
 99 
100         int ans = 0;
101         memset(d, -1, sizeof(d)); // 初始化动态规划记忆化数组
102         for(int i = 1; i <= scc_cnt; i++) // 注意，SCC编号为1~scc_cnt
103             ans = max(ans, dp(i));
104         printf("%d
", ans);
105     }
106     return 0;
107 }

View Code