51Nod 1524 可除图的最大团

Problem

对于一般的图，最大团问题是一个NP-难的问题。然而，对于一些特殊的图，最大团问题可以有比较有效的解决方案。

关于最大团问题的概念，请百度之。^_^

在一个正整数集合A上定义可除图。 A = {a1, a2, ..., an} ，图上的顶点就是集合A中的数字。两个数字 ai 和 aj (i ≠ j) 之间有一条边的条件是 ai 能够被 aj 整除，或者 aj 能够被 ai 整除.

现在给定一个正整数集A，请找出这个集合所确定的可除图的最大团。

样例解释：在这个例子中，最大团是3，可以选择 {3,6,18}。

Solution

很容易想到，从小到大构建一张有向图，一个数的因子向这个数连边，对于任意一个数a[i]，要计算1e6/a[i]次，连边复杂度1e6×(1/1+1/2+1/3+...+1/1e6)，是nlogn，然后拓扑排序做dp，结果就会发现，这样做过不了，是被卡常了。

然后可以用dp[i]表示对于数字i，最大团数量是多少，同样的循环就能过了。。。

Code

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
const int mod=1000000007;
int n,m;
int a[1000020],dp[1000020],f[1000020];
int ans;
inline int rd(){
	int x=0,f=1;
	char ch;
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

int main(){
	n=rd();
	for(int i=1;i<=n;i++){
		a[i]=rd();
		f[a[i]]=1;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(dp[a[i]]==0) dp[a[i]]=1;
		for(int j=a[i]*2;j<=a[n];j+=a[i]){
			if(f[j]){
				dp[j]=max(dp[j],dp[a[i]]+1);
				//if(i==6) printf("%d %d\n",j,dp[j]);
			}
		}
		ans=max(ans,dp[a[i]]);
		//printf("%d\n",dp[a[i]]);
	}
	
	printf("%d\n",ans);
	return 0;
}