[HDOJ3335 Divisibility]【DAG图的最大独立集】【最大反链】【最小链划分】【最小路径覆盖】

【题目大意】
给定N个数，让你取最多的数，使得取出的数里，不存在A是B的倍数这种情况。
【算法分析】
虽然当时ACM_DIY群赛时蒙对了算法，当时推理方式见（那叫一个强力）：
http://hi.baidu.com/edwardmj/blog/item/1ae99b3f5f5cbee53d6d9789.html
但一直没有理解，于是今天重温二分图时回来做了一下。
本题可以先把相同的数去掉，然后若A为B的倍数，那么B->A。
由于A>B，那么是一个DAG图（有向无环图）
然后DAG图的最大反链就可以利用匹配来搞。（传递闭包后的DAG图的最大独立集=最大反链）
具体做法是每个点拆两个点，弄成二分图，然后匹配。最后输出n-匹配数。
二分图总结见：http://hi.baidu.com/edwardmj/blog/item/b5fc0419bd3661f1af513325.html
小菜总结，不足谢谢补充。
【CODE】
#include #include #include const int N=1005;
typedef __int64 lld;
struct edge{int y;edge *next;}g[1005555],*ls[N];
int n,e,cnt;
int v[N],link[N];
lld a[N];

int cmp(const void *A,const void *B){
lld AA=*((lld*)A),BB=*((lld*)B);
if (AA>BB) return 1;
if (AA return 0;
}

void addedge(int x,int y){
g[++e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void build(){
int tot=0,i,j;
for (i=1;i<=n;i++)
if (!tot || a[i]!=a[tot])
a[++tot]=a[i];
n=tot;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
if (a[j]%a[i]==0 && a[j]>a[i])
addedge(i,j);
}

bool Find(int p){
for (edge *t=ls[p];t;t=t->next)
if (v[t->y]!=cnt){
v[t->y]=cnt;
int q=link[t->y];
link[t->y]=p;
if (!q || Find(q)) return true;
link[t->y]=q;
}
return false;
}

void solve(){
memset(link,0,sizeof(link));
memset(v,0,sizeof(v));
int ans=0;
for (cnt=1;cnt<=n;cnt++)
if (Find(cnt)) ans++;
printf("%dn",n-ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
e=0;
for (int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
ls[i]=NULL;
}
qsort(a+1,n,sizeof(lld),cmp);
build();
solve();
}
}