<题目链接>
题目大意：
n个人，m条关系，每条关系a >= b，说明a，b之间是可比较的，如果还有b >= c，则说明b，c之间，a，c之间都是可以比较的。问至少需要多少个集合使得每个集合内的人都是不可比较的。
解题分析：
将所给的关系当成有向边，根据题意，同一强连通分量中的任意两点不能分到一组，所以我们先将整张图进行缩点，缩点后"点"的中点的数量当做点权，然后就可以转化为最长路的求解了。这里比较难想，因为同一连通分量中的点不能在一组，所以必然要将它们全部排成一条。因为要求最少分成的组，所以我们只需要将整张图的最长关键路径(最大点权和的路径)找出即可，这样可以将不在关键路径上的"点"中的所有的点与最长路径上的不同点分配到一组，因为它们不属于一个连通分量，所以这样分配，每组之间的所有点仍然是不可比较的。又因为这是最长路径，所以每次必然能够最长路径之外的"点"中所有的点与最短路径上的点一 一分配到一组。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 const int N = 1e5+10; 8 const int M = 3e5+10; 9 struct Edge{ 10 int v, nxt; 11 } edge[M], edg[M]; 12 int n,m,tott, tot, ord, scc, top; 13 int cnt[N], dp[N], head[N], hea[N], vis[N], deg[N], dfn[N], low[N], belong[N],stk[N]; 14 15 void init(){ 16 tot = scc = tott = ord = top = 0; 17 memset(head, -1, sizeof(head)); 18 memset(hea, -1, sizeof(hea)); 19 memset(dfn, 0, sizeof(dfn)); 20 memset(dp, 0, sizeof(dp)); 21 memset(cnt,0,sizeof(cnt)); 22 } 23 void Add(int u, int v) { 24 edge[tot].v = v; edge[tot].nxt = head[u]; 25 head[u] = tot++; 26 } 27 void add(int u, int v) { 28 edg[tott].v = v; edg[tott].nxt = hea[u]; 29 hea[u] = tott++; 30 } 31 void tarjan(int u) { 32 dfn[u] = low[u] = ++ord; 33 stk[++top]=u; vis[u] = 1; 34 for(int i = head[u]; ~i; i = edge[i].nxt) { 35 int v = edge[i].v; 36 if(!dfn[v]){ 37 tarjan(v); 38 low[u]=min(low[u],low[v]); 39 }else if(vis[v])low[u]=min(low[u],dfn[v]); 40 } 41 if(low[u] == dfn[u]) { 42 ++scc; 43 while(true){ 44 int v=stk[top--]; 45 belong[v] = scc; 46 cnt[scc]++; 47 vis[v] = 0; 48 if(v==u)break; 49 } 50 } 51 } 52 //将"点"中点的数量作为这个点的点权，然后求出最大点权的路径 53 //dp[u]表示，以u为起点的最长路径 54 int DFS(int u) { 55 if(dp[u]) return dp[u]; 56 int ans = cnt[u]; 57 for(int i = hea[u]; ~i; i = edg[i].nxt) { 58 int v = edg[i].v; 59 ans = max(ans, DFS(v) + cnt[u]); 60 } 61 return dp[u] = ans; 62 } 63 int main() { 64 while(~scanf("%d%d", &n, &m)) { 65 init(); 66 for(int i = 0; i < m; i++) { 67 int u,v;scanf("%d%d", &u, &v); 68 Add(u, v); 69 } 70 for(int i = 1; i <= n; i++) 71 if(!dfn[i]) tarjan(i); 72 for(int u = 1; u <= n; u++) 73 for(int i = head[u]; ~i; i = edge[i].nxt) { 74 int v = edge[i].v; 75 if(belong[u] != belong[v]) { 76 add(belong[u], belong[v]); 77 } 78 } 79 int ans = -1; 80 for(int i = 1; i <= scc; i++) 81 ans = max(ans, DFS(i)); //所有点为起点的最长路径即为整张图的最长路径 82 printf("%d ", ans); 83 } 84 }
2018-11-26