首页 > 代码库 > UVA 11324 The Largest Clique (强连通分量缩点，图DP)
UVA 11324 The Largest Clique (强连通分量缩点，图DP)
题目：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2299
题意：
给你一个有向图，求一个点集合的最大大小，使得此点集合中对于任意点对(u,v)，有从u到v或者从v到u的边
方法：
先找强连通分量缩点，每个强连通分量显然满足条件，然后在缩点后的图中找到一条权值最大的路径，权值为此路径的点权之和，点权为这个强连通分量的点数
1 int dp[maxn];2 int dfs(int u)3 {4 if (dp[u]) return dp[u];5 int ret = 0;6 for (int i = head[u]; ~i; i = edge[i].next)7 ret = max(ret, dfs(edge[i].v));8 return dp[u] = ret + node[u];9 }
代码：
1 /******************************************** 2 *ACM Solutions 3 * 4 *@Title: 5 *@Version: 1.0 6 *@Time: 2014-xx-xx 7 *@Solution: http://www.cnblogs.com/xysmlx/p/xxxxxxx.html 8 * 9 *@Author: xysmlx(Lingxiao Ma) 10 *@Blog: http://www.cnblogs.com/xysmlx 11 *@EMail: xysmlx@163.com 12 * 13 *Copyright (C) 2011-2015 xysmlx(Lingxiao Ma) 14 ********************************************/ 15 // #pragma comment(linker, "/STACK:102400000,102400000") 16 #include <cstdio> 17 #include <iostream> 18 #include <cstring> 19 #include <string> 20 #include <cmath> 21 #include <set> 22 #include <list> 23 #include <map> 24 #include <iterator> 25 #include <cstdlib> 26 #include <vector> 27 #include <queue> 28 #include <ctime> 29 #include <stack> 30 #include <algorithm> 31 #include <functional> 32 using namespace std; 33 typedef long long ll; 34 #define pb push_back 35 #define ROUND(x) round(x) 36 #define FLOOR(x) floor(x) 37 #define CEIL(x) ceil(x) 38 const int maxn = 1010; 39 const int maxm = 200010; 40 const int inf = 0x3f3f3f3f; 41 const ll inf64 = 0x3f3f3f3f3f3f3f3fLL; 42 const double INF = 1e30; 43 const double eps = 1e-6; 44 int kase; 45 int n, m; 46 struct Edge 47 { 48 int u, v; 49 int next; 50 Edge(int _u, int _v, int _next): u(_u), v(_v), next(_next) {} 51 Edge() {} 52 } edge[maxm]; 53 int en; 54 int head[maxn]; 55 int node[maxn]; 56 void addse(int u, int v) 57 { 58 edge[en] = Edge(u, v, head[u]); 59 head[u] = en++; 60 } 61 struct SCC 62 { 63 Edge edge[maxm]; 64 int en; 65 int head[maxn]; 66 int h[maxn]; 67 void addse(int u, int v) 68 { 69 edge[en] = Edge(u, v, head[u]); 70 head[u] = en++; 71 } 72 void init() 73 { 74 memset(head, -1, sizeof(head)); 75 en = 0; 76 } 77 int sid[maxn]; 78 int mark[maxn], low[maxn]; 79 int check[maxn]; 80 int sstack[maxn], top; 81 int dfn, ssn; 82 int n, m; 83 bool mtx[maxn][maxn]; 84 void dfs(int k) 85 { 86 int i, j; 87 check[k] = 1; 88 low[k] = mark[k] = dfn++; 89 sstack[top++] = k; 90 for (int i = head[k]; i != -1; i = edge[i].next) 91 { 92 int j = edge[i].v; 93 if (mark[j] == 0) 94 { 95 dfs(j); 96 low[k] = min(low[k], low[j]); 97 } 98 else if (check[j]) 99 low[k] = min(low[k], mark[j]);100 }101 if (mark[k] == low[k])102 {103 while (sstack[--top] != k)104 {105 check[sstack[top]] = 0;106 sid[sstack[top]] = ssn;107 }108 sid[k] = ssn;109 check[k] = 0;110 ++ssn;111 }112 return;113 }114 void tarjan()115 {116 ssn = 1;117 dfn = 1;118 top = 0;119 memset(check, 0, sizeof(check));120 memset(mark, 0, sizeof(mark));121 for (int i = 0; i < n; ++i) if (mark[i] == 0) dfs(i);122 123 memset(h, 0, sizeof(h));124 for (int i = 0; i < n; i++)125 h[sid[i]]++;126 memset(mtx, 0, sizeof(mtx));127 for (int i = 0; i < en; i++)128 mtx[sid[edge[i].u]][sid[edge[i].v]] = 1;129 }130 } scc;131 132 int dp[maxn];133 int dfs(int u)134 {135 if (dp[u]) return dp[u];136 int ret = 0;137 for (int i = head[u]; ~i; i = edge[i].next)138 ret = max(ret, dfs(edge[i].v));139 return dp[u] = ret + node[u];140 }141 142 void init()143 {144 kase++;145 scc.init();146 memset(head, -1, sizeof(head));147 en = 0;148 memset(dp, 0, sizeof(dp));149 }150 void input()151 {152 scanf("%d%d", &n, &m);153 scc.n = n;154 for (int i = 0; i < m; i++)155 {156 int u, v;157 scanf("%d%d", &u, &v);158 u--, v--;159 scc.addse(u, v);160 }161 }162 void debug()163 {164 //165 }166 void solve()167 {168 scc.tarjan();169 n = scc.ssn;170 for (int i = 1; i < scc.ssn; i++)171 {172 for (int j = 1; j < scc.ssn; j++)173 {174 if (i == j) continue;175 if (scc.mtx[i][j])176 addse(i, j);177 }178 }179 for (int i = 1; i < scc.ssn; i++)180 node[i] = scc.h[i];181 // for (int i = 1; i < scc.ssn; i++)182 // cout << node[i] << " ";183 // cout << endl;184 int ans = 0;185 memset(dp, 0, sizeof(dp));186 for (int i = 1; i < n; i++)187 {188 ans = max(ans, dfs(i));189 }190 printf("%d\n", ans);191 }192 void output()193 {194 //195 }196 int main()197 {198 // 32-bit199 // int size = 256 << 20; // 256MB200 // char *p = (char *)malloc(size) + size;201 // __asm__("movl %0, %%esp\n" :: "r"(p));202 203 // 64-bit204 // int size = 256 << 20; // 256MB205 // char *p = (char *)malloc(size) + size;206 // __asm__("movq %0, %%rsp\n" :: "r"(p));207 208 // std::ios_base::sync_with_stdio(false);209 #ifdef xysmlx210 freopen("in.txt", "r", stdin);211 #endif212 213 kase = 0;214 int T;215 scanf("%d", &T);216 while (T--)217 {218 init();219 input();220 solve();221 output();222 }223 return 0;224 }
UVA 11324 The Largest Clique (强连通分量缩点，图DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。