本文主要是介绍训练赛 Grouping(强连通分量缩点 + DAG求最长路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=158#problem/F
大致题意：给出n个人和m种关系(ti,si)，表示ti的年龄不小于si。问最小能被划分为几个集合，每个集合都要满足里面的人都无法比较。
思路：对于一条路上的点，它们必定不能被划分到同一个集合中，因此原题变为求一条最长路。而题目中有可能出现环。因此，先tarjan缩点转化为DAG，而缩点后的每个点的点权便是该节点中包含的点的个数，然后记忆化求最长路。
PS：该题与上一篇
uva 11324 The Largest Clique是一样的。该题重在转化。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 100010;vector <int> edge[maxn],edge2[maxn];
int n,m;
int dfn[maxn],low[maxn],instack[maxn],dep,scc;
stack <int> st;
int set[maxn],num[maxn];
int d[maxn];void init()
{for(int i = 1; i <= n; i++){edge[i].clear();edge2[i].clear();}memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(instack,0,sizeof(instack));while(!st.empty()) st.pop();dep = 0;scc = 0;memset(num,0,sizeof(num));memset(d,0,sizeof(d));
}void tarjan(int u)
{dfn[u] = low[u] = ++dep;instack[u] = 1;st.push(u);for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(!dfn[v]){tarjan(v);low[u] = min(low[u],low[v]);}else if(instack[v])low[u] = min(low[u],dfn[v]);}if(dfn[u] == low[u]){scc++;int t;while(1){t = st.top();st.pop();instack[t] = 0;set[t] = scc;num[scc]++;if(t == u)break;}}
}void creat()
{for(int u = 1; u <= n; u++){for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(set[u] != set[v])edge2[set[u]].push_back(set[v]);}}
}int dp(int u)
{if(d[u]) return d[u];else if(edge2[u].size() == 0) return d[u] = num[u];int ans = 0;for(int i = 0; i < (int)edge2[u].size(); i++){int v = edge2[u][i];ans = max(ans,dp(v));}return d[u] = ans+num[u];
}int main()
{int u,v;while(~scanf("%d %d",&n,&m)){init();for(int i = 1; i <= m; i++){scanf("%d %d",&u,&v);edge[u].push_back(v);}for(int i = 1; i <= n; i++)if(!dfn[i])tarjan(i);creat();int ans = 0;for(int i = 1; i <= scc; i++){ans = max(ans,dp(i));}printf("%d\n",ans);}return 0;
}
这篇关于训练赛 Grouping(强连通分量缩点 + DAG求最长路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
