首页 > 代码库 > ZOJ3795 Grouping 强连通缩点+图的最长路
ZOJ3795 Grouping 强连通缩点+图的最长路
给出m条a年龄大于等于b的信息,要求可以比较的两个人不能放在同一组,问最少能分成几组。
由于是大于等于,所以原图可能构成强连通分量,意思就是有很多人年龄相同(想想也该知道,总共10w个人,肯定有很多人年龄重复= =!)将原图缩点后,对新图记忆化搜索求最长路。
如果不缩点,会RE。。。
#include <iostream> #include<cstring> #include<cstdio> #include<string> #include<algorithm> using namespace std; #define MAXN 100005 #define MAXM 300005 struct node { int to,next; }edge[MAXM],edge2[MAXM]; int head[MAXN],en; int low[MAXN],dfn[MAXN],stack[MAXN],top,set[MAXN],col,num; bool vis[MAXN],instack[MAXN]; int n; int m; void addedge(int a,int b) { edge[en].to=b; edge[en].next=head[a]; head[a]=en++; } void tarjan(int u) { vis[u]=1; dfn[u]=low[u]=++num; instack[u]=true; stack[++top]=u; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!vis[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(dfn[v],low[u]); } if(dfn[u]==low[u]) { int j; col++; do { j=stack[top--]; instack[j]=false; set[j]=col; } while (j!=u); } } int head2[MAXN]; int sum[MAXN],en2; int dp[MAXN]; int in[MAXN]; void init() { int i; en2=en=top=col=num=0; memset(dp,-1,sizeof(dp)); memset(head,-1,sizeof(head)); memset(instack,0,sizeof(instack)); memset(vis,0,sizeof(vis)); memset(set,-1,sizeof(set)); memset(head2,-1,sizeof(head2)); memset(sum,0,sizeof(sum)); memset(in,0,sizeof(in)); } void addedge2(int a,int b) { edge2[en2].to=b; edge2[en2].next=head2[a]; head2[a]=en2++; } int dfs(int now) { if(~dp[now]) return dp[now]; int maxn=sum[now]; for(int i=head2[now];~i;i=edge2[i].next) { int to=edge2[i].to; maxn=max(maxn,sum[now]+dfs(to)); } return dp[now]=maxn; } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { init(); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b); } for(int i=1;i<=n;i++) if(!vis[i])tarjan(i); for(int i=1;i<=n;i++) sum[set[i]]++; // for(int i=1;i<=n;i++) printf("%d=%d\n",i,set[i]); for(int i=1;i<=n;i++) { for(int j=head[i];~j;j=edge[j].next) { int to=edge[j].to; if(set[to]!=set[i]) { in[set[to]]++; addedge2(set[i],set[to]); } } } for(int i=1;i<=col;i++) if(in[i]==0) addedge2(0,i); dfs(0); int ans=0; for(int i=1;i<=col;i++) ans=max(ans,dp[i]); printf("%d\n",ans); } return 0; } /* 7 8 1 2 2 3 3 1 3 5 3 4 4 6 6 7 7 4 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。