ZOJ3795_Grouping
2024-10-15 10:26:00
告诉你某些人的年龄大小关系,问你把所有的人分成若干个组,最少需要多少组,使得组内任意两个人的年龄不可比。
首先考虑特殊情况,如果所有年龄关系构成了一个环,那么这个环中所有人的年龄都是相等,也就是可比的。
同时所有其他的与这个环中任意一个点相连的任意一个环或者点都是可比的。
如果两个点或者环,无法处在同一条路径上,那么这两个点和环就是不可比的。
于是算法就出来了。
对于每一个强连通分量,我们将其缩为一个点,点权为这个连通分量中的点数。这样就相当于我们找一条权值最大的路径就好了。
由于缩点后一定是一个有向无环图,那么可以通过dp或者记忆化搜索解决问题。
召唤代码君:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define maxn 600600
using namespace std; vector<int> V[maxn];
int to[maxn],next[maxn],first[maxn],edge;
int d[maxn],f[maxn],low[maxn],belong[maxn],ans;
int stack[maxn],top;
int n,m,sccnum,dfs_clock; void _init()
{
edge=ans=;
top=sccnum=;
memset(first,-,sizeof(int)*(n+));
memset(d,,sizeof(int)*(n+));
memset(belong,,sizeof(int)*(n+));
} void addedge(int U,int V)
{
if (U==V) return;
to[edge]=V,next[edge]=first[U],first[U]=edge++;
} void dfs(int cur)
{
d[cur]=low[cur]=++dfs_clock;
stack[++top]=cur;
for (int i=first[cur]; i!=-; i=next[i])
if (!d[to[i]]){
dfs(to[i]);
low[cur]=min(low[cur],low[to[i]]);
}
else if (!belong[to[i]]) low[cur]=min(low[cur],d[to[i]]);
if (low[cur]==d[cur]){
V[++sccnum].clear();
f[sccnum]=;
for (;;){
int x=stack[top--];
belong[x]=sccnum;
f[sccnum]++;
if (x==cur) break;
}
}
} int get(int x)
{
if (d[x]!=-) return d[x];
d[x]=;
for (unsigned i=; i<V[x].size(); i++)
d[x]=max(get(V[x][i]),d[x]);
return d[x]=d[x]+f[x];
} int main()
{
int UU,VV;
while (scanf("%d%d",&n,&m)!=EOF){
_init();
while (m--){
scanf("%d%d",&UU,&VV);
addedge(UU,VV);
}
for (int i=; i<=n; i++)
if (!d[i]) dfs(i);
for (int i=; i<=n; i++)
for (int j=first[i]; j!=-; j=next[j])
if (belong[i]!=belong[to[j]])
V[belong[i]].push_back(belong[to[j]]);
memset(d,-,sizeof(int)*(sccnum+));
for (int i=; i<=sccnum; i++)
ans=max(ans,get(i));
printf("%d\n",ans);
}
return ;
}
最新文章
- 浅尝辄止——使用ActiveX装载WPF控件
- hdu 4651 - Partition(五边形数定理)
- STL容器删除元素的陷阱
- 以对象的方式来访问xml数据表(三)
- OpenGL-选择与拾取
- 移动OA日程支持费用及评论
- APK重编译
- Redis 安全配置
- vue2.0子组件修改父组件props数据的值
- Azkaban学习笔记(二)
- centos 7.x设置守护进程的文件数量限制
- Java动态加载属性文件.properties
- docker stack命令
- 883. Projection Area of 3D Shapes
- 关于Redis命令keys在性能方面的说明
- Win10 Cygwin Cd Permission denied
- Android 音频系统得框架
- Kafka(1)-概述
- Go编译安装
- 转【jenkins插件】