首页 > 代码库 > UVa11324 最大团
UVa11324 最大团
题意:一个有向图中,求一个节点数最多的结点集,使得该结点任意两点u和v, 要么u可达v,要么v可达u,u和v互相可达也可以。
思路:这一看就知道是最大团的定义了,可以说是最大团的模板题,可以先强连通缩点,缩点后就成了DAG(有向无环图),强连通里的点都可以满足要求,再求DAG的最长路径极为结果,每个强连通缩点后的点权即为该强连通的结点个数,而DAG求路径可用动态规划求。
一开始我记录每个连通图结点个数时,在tarjan算法里面写,可是WA,后来放在缩点的地方就对了。这个真心不知道为什么了。
#include<stdio.h>#include<string.h>const int maxn = 3000;const int maxm = 50009;struct node{ int v,next;}eg[maxm],tree[maxm];int head[maxn],root[maxn];int dfn[maxn],low[maxn],sta[maxn],insta[maxn],sum[maxn],belong[maxn];int tot,color,Index,top,n;int dp[maxn];inline int max(int a,int b){return a > b ? a : b;}inline int min(int a,int b){return a < b ? a : b;}void add(int a,int b){ eg[tot].v = b; eg[tot].next = head[a]; head[a] = tot++;}void addt(int a,int b){ tree[tot].v = b; tree[tot].next = root[a]; root[a] = tot++;}//求强连通void tarjan(int u){ dfn[u] = low[u] = ++Index; sta[top++] = u; insta[u] = 1; for(int i =head[u];i+1;i=eg[i].next) { int v = eg[i].v; if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); }if(insta[v]) { low[u] = min(low[u],dfn[v]); } } if(low[u] == dfn[u]) { color++; int v; do { v= sta[--top]; insta[v] = 0; belong[v] = color; // sum[color] ++; //为什么不可以在这里加 }while(u != v); }} //缩点void Buildtree(){ tot = 0; for(int u = 1;u <= n;u++) { sum[belong[u]] ++; //每个连通图的结点个数 for(int i=head[u];i+1;i=eg[i].next) { int v= eg[i].v; if(belong[u] != belong[v]) { addt(belong[u],belong[v]); } } }}void init(){ memset(dp,0,sizeof(dp)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(head,-1,sizeof(head)); memset(root,-1,sizeof(root)); memset(insta,0,sizeof(insta)); memset(belong,0,sizeof(belong)); memset(sum,0,sizeof(sum)); tot = Index = top = color = 0;}int Clique(int u) //dp求DAG的最长路径{ if(dp[u]>0) return dp[u]; dp[u]=sum[u]; for(int i=root[u];i+1;i=tree[i].next) { int v=tree[i].v; dp[u]=max(dp[u],Clique(v)+sum[u]); } return dp[u]; } void work(){ int u,i,ans =0; tot = 0; for( u =1;u<=n;u++) { if(!dfn[u]) tarjan(u); } Buildtree(); for(i=1;i<=color;i++) { ans = max(ans,Clique(i)); } printf("%d\n",ans);}int main(){ int m,i,a,b,t; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); add(a,b); } work(); } return 0;}/*25 51 22 33 14 15 25 51 22 33 14 15 2*/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。