首页 > 代码库 > zoj Grouping(强连通＋缩点＋关键路径)
zoj Grouping(强连通＋缩点＋关键路径)
题意：
给你Ｎ个人，Ｍ条年龄大小的关系，现在打算把这些人分成不同的集合，使得每个集合的任意两个人之间的年龄是不可比的。问你最小的集合数是多少？
分析：
首先，假设有一个环，那么这个环中的任意两个点之间都是可比的，并且，和这个环相连的任意一个点或环也和这个环是可比的，因为关系具有传递性。但如果两个点或者环，无法处在同一条路径上，那么这两个点和环就是不可比的。所以，如果我们把这些环－－强连通分量缩为一个点。强连通分量的点数就是缩点后的点权。那么缩点后的新图就是一个有向带权无环图，题目就是要求我们求出这个有向带权无环图的关键路径－－－－最长路径。（因为那些较短的路径上的点总可以和较长的路径点和为一点）。
1 //First Edit Time: 2014-11-25 13:38 2 //Last Edit Time: 2014-11-25 14:24 3 #include<cstdio> 4 #include<cstring> 5 #include<vector> 6 using namespace std; 7 8 #define _clr(x, y) memset(x, y, sizeof (x)) 9 #define Min(x, y) (x < y ? x : y) 10 #define Max(x, y) (x > y ? x : y) 11 #define INF 0x3f3f3f3f 12 #define N 100010 13 14 vector<int> map[N], new_map[N]; 15 int low[N], dfn[N]; 16 int Stack[N], be[N]; 17 bool instack[N]; 18 int dist[N], sum[N]; 19 int top, n, cnt, time; 20 21 void Init() 22 { 23 top = time = cnt = 0; 24 _clr(instack, 0); 25 _clr(Stack, 0); 26 _clr(dist, -1); 27 _clr(low, 0); 28 _clr(sum, 0); 29 _clr(dfn, 0); 30 _clr(be, 0); 31 for(int i=0; i<=n; i++) 32 { 33 map[i].clear(); 34 new_map[i].clear(); 35 } 36 } 37 38 //ｄｆｓ生成树求强连通分量 39 void dfs(int u) 40 { 41 dfn[u] = low[u] = ++time; 42 Stack[top++] = u; 43 instack[u] = true; 44 for(int i=0; i<(int)map[u].size(); i++) 45 { 46 int v = map[u][i]; 47 if(!dfn[v]) 48 { 49 dfs(v); 50 low[u] = Min(low[u], low[v]); 51 } 52 else if(instack[v]) 53 low[u] = Min(low[u], dfn[v]); 54 } 55 if(dfn[u]==low[u]) 56 { 57 cnt++; 58 do 59 { 60 u = Stack[--top]; 61 instack[u] = false; 62 be[u] = cnt; 63 sum[cnt]++; 64 }while(dfn[u] != low[u]); 65 } 66 } 67 68 void Tarjan_Scc() 69 { 70 for(int i=1; i<=n; i++) 71 { 72 if(!dfn[i]) 73 dfs(i); 74 } 75 for(int i=1; i<=n; i++) 76 { 77 for(int j=0; j<(int)map[i].size(); j++) 78 { 79 int v = map[i][j]; 80 if(be[i] != be[v]) 81 new_map[be[i]].push_back(be[v]); 82 } 83 } 84 } 85 86 int Get(int u) 87 { 88 if(dist[u]!=-1) return dist[u]; 89 dist[u] = 0; 90 for(int i=0; i<(int)new_map[u].size(); i++) 91 dist[u] = Max(Get(new_map[u][i]), dist[u]); 92 return dist[u] = dist[u] + sum[u]; 93 } 94 95 int main() 96 { 97 int m, x, y; 98 while(~scanf("%d%d",&n,&m)) 99 {100 Init();101 for(int i=0; i<m; i++)102 {103 scanf("%d%d",&x, &y);104 map[x].push_back(y);105 }106 107 Tarjan_Scc(); //Tarjan算法求强连通缩点为一个ＤＡＧ108 109 int ans = -INF;110 for(int i=1; i<=cnt; i++) //记忆化搜索求ＤＡＧ关键路径111 ans = Max(Get(i), ans);112 113 printf("%d\n", ans);114 }115 return 0;116 }
zoj Grouping(强连通＋缩点＋关键路径)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。