ZOJ 3795:Grouping(缩点+最长路)

时间:2022-11-09 18:49:10

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5303

题意:有n个人m条边,每条边有一个u,v,代表u的年龄大于等于v,现在要将这n个人分成x个组,组内的人的年龄不能够直接或者间接比较,问最少可以分成多少组。

思路:一开始没看清题意,直接拓扑排序做了。后来听师兄说会有环,年龄大于等于,如果有环代表这里面的年龄相等,那么环里面的人都是每个人一组,缩完点之后那个点的长度就是点的人数,然后用DP最长路做。

 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
struct Edge {
int v, nxt;
} edge[N*], edg[N*];
int cnt[N], dp[N], head[N], hea[N], tott, tot, tim, vis[N], deg[N], dfn[N], low[N], belong[N], num;
stack<int> sta; void Add(int u, int v) {
edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;
} void add(int u, int v) {
edg[tott].v = v; edg[tott].nxt = hea[u]; hea[u] = tott++;
} void tarjan(int u) {
dfn[u] = low[u] = ++tim;
sta.push(u); vis[u] = ;
for(int i = head[u]; ~i; i = edge[i].nxt) {
Edge &e = edge[i];
if(!dfn[e.v]) {
tarjan(e.v);
if(low[e.v] < low[u]) low[u] = low[e.v];
} else if(vis[e.v] && dfn[e.v] < low[u]) low[u] = dfn[e.v];
}
if(low[u] == dfn[u]) {
++num; int v = -;
cnt[num] = ;
while(v != u) {
v = sta.top(); sta.pop();
belong[v] = num;
cnt[num]++;
vis[v] = ;
}
}
} int DFS(int u) {
if(dp[u]) return dp[u];
int ans = cnt[u];
for(int i = hea[u]; ~i; i = edg[i].nxt) {
int v = edg[i].v;
ans = max(ans, DFS(v) + cnt[u]);
}
return dp[u] = ans;
} int main() {
int n, m;
while(~scanf("%d%d", &n, &m)) {
memset(head, -, sizeof(head));
memset(hea, -, sizeof(hea));
memset(dfn, , sizeof(dfn));
memset(dp, , sizeof(dp));
tot = num = tott = tim = ;
int u, v;
for(int i = ; i < m; i++) {
scanf("%d%d", &u, &v);
Add(u, v);
}
for(int i = ; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int u = ; u <= n; u++) {
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(belong[u] != belong[v]) {
add(belong[u], belong[v]);
}
}
}
int ans = ;
for(int i = ; i <= num; i++)
ans = max(ans, DFS(i));
printf("%d\n", ans);
}
return ;
}

ZOJ 3795:Grouping(缩点+最长路)的更多相关文章

  1. zoj 3795 Grouping tarjan缩点 &plus; DGA上的最长路

    Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Submit Status Practic ...

  2. ZOJ 3795 Grouping &lpar;强连通缩点&plus;DP最长路&rpar;

    <题目链接> 题目大意: n个人,m条关系,每条关系a >= b,说明a,b之间是可比较的,如果还有b >= c,则说明b,c之间,a,c之间都是可以比较的.问至少需要多少个集 ...

  3. ZOJ 3795 Grouping&lpar;scc&plus;最长路&rpar;

    Grouping Time Limit: 2 Seconds      Memory Limit: 65536 KB Suppose there are N people in ZJU, whose ...

  4. poj 3592 Instantaneous Transference 缩点&plus;最长路

    题目链接 给一个n*m的图, 从0, 0这个点开始走,只能向右和向下. 图中有的格子有值, 求能获得的最大值. 其中有些格子可以传送到另外的格子, 有些格子不可以走. 将图中的每一个格子都看成一个点, ...

  5. bzoj1179 &lbrack;Apio2009&rsqb;Atm——缩环最长路

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1179 tarjan 缩环,然后求到有酒吧的点的最长路即可: 但一开始想缩环后用拓扑序求答案, ...

  6. ZOJ 3795 Grouping 求最长链序列露点拓扑

    意甲冠军:特定n积分.m向边条. 该点被划分成多个集合随机的每个集合,使得2问题的关键是无法访问(集合只能容纳一个点) 问至少需要被分成几个集合. 假设没有戒指,接着这个话题正在寻求产业链最长的一个有 ...

  7. ZOJ 3795 Grouping

    大致题意是给n个人和m组关系,每组关系都是两个人s和t,表示s年龄不小于t的年龄,然后让你把这n个人分组,使得任何一个组里面的任意两人都不能直接或间接的得出这两个人的年龄大小关系. 思路:根据给出的关 ...

  8. ZOJ 3795 Grouping 强连通分量-tarjan

    一开始我还天真的一遍DFS求出最长链以为就可以了 不过发现存在有向环,即强连通分量SCC,有向环里的每个点都是可比的,都要分别给个集合才行,最后应该把这些强连通分量缩成一个点,最后保证图里是 有向无环 ...

  9. ZOJ 3795 Grouping&lpar;Tarjan收缩点&plus;DAG)

    Suppose there are N people in ZJU, whose ages are unknown. We have some messages about them. The i-t ...

随机推荐

  1. A quick renice command rescheduled the upgrade to a lower priority and I was back to surfing in no time&period;

    https://www.nixtutor.com/linux/changing-priority-on-linux-processes/ Changing Priority on Linux Proc ...

  2. &lbrack;daily&rsqb;&lbrack;archlinux&rsqb;&lbrack;fonts&rsqb; 在linux下管理字体

    序: linux是社区搞出来, 商业应用也都是服务器场景.社区里又都是技术人员.字体又是细节.而且会英文早成了标配.所以没有很多社区以外的人力来搞字体这个毫无回报的东西. 结果很自然的,装linux桌 ...

  3. 8个经典HTML5 3D动画赏析

    HTML5技术已经越来越被我们所接受,特别是一些3D的动画特效.本文介绍的8个HTML5 3D动画并没有特别华丽的界面,但是比较实用,涉及到3D图片.3D图表.3D按钮等方面,一起来看看. 1.HTM ...

  4. 学习JAVA第一部分总结

    把自己这几天的学习情况记录下来. 第一章,认识JAVA,了解JAVA的运行机制,虚拟机. 第二章,了解java的注释,标识符,关键字.. 第三章,基本的数据类型,byte short int long ...

  5. SQL server 2008无法修改表

    长久未使用SQL server,一直都是使用Navicat来处理各种数据库,感觉使用很方便,但由于实际需要,必须要用SQL server创建新的数据库,却意外的遇到了以前从未遇到过的问题. 在建好表以 ...

  6. Tips &amp&semi; Tricks:Apache log4j简明教程(一)

    Apache log4j的官方介绍是“log4j is a reliable, fast and flexible logging framework (APIs) written in Java, ...

  7. &lbrack;已解决&rsqb;Cannot find one or more components&period;Please reinstall the application

    Microsoft SQL Server Management Studio 17,一段时间未用出现Cannot find one or more components.Please reinstal ...

  8. iOS开发造* &vert; 通用占位图

    https://www.jianshu.com/p/beca3ac24031 实际运用场景: 没网时的提示view,tableView或collectionView没内容时的展示view,以及其它特殊 ...

  9. 运维与自动化系列③自动化部署基础与shell脚本实现

    自动化部署基础与shell脚本实现 关于自动化的基础知识: 1.1:当前代码部署的实现方式: 运维纯手工scp到web服务器纯手工登录git服务器执行git pull或svn服务器执行svn upda ...

  10. 目前&period;NET Core创建Windows Service比较好的一个开源框架:DasMulli&period;Win32&period;ServiceUtils

    新建一个.NET Core控制台程序,搜索并下载Nuget包:DasMulli.Win32.ServiceUtils GitHub 链接及使用指南 Write a windows service us ...