2013 ACM/ICPC Asia Regional Chengdu Online&hdu4735Little Wish~ lyrical step~(DLX解重复覆盖)

好吧，其实这题把这题代码改一点也能过。。。。说好的没有原题呢

题目请戳这里

题目大意：给一颗树，有n个点，每个点代表一个性别，两点之间的边上有边权w，表示2点之间的距离。现在已知如果某个点是男的，那么与他距离不超过D的点都被他罩着。现在要使所有的女的都至少被一个男的罩，求最少要交换几对男女的位置。

题目分析：求最小点支配集。跟这题区别大么。不过多了点约束条件而已。用dancinglingks+A*优化搜索。搜索过程中注意控制男生人数。

具体方法就是先找出最小支配集，然后判断最小支配集中有多少男生。少了的就是要交换的。

详情请见代码：

#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 55;const int M = 3000;const int inf = 0x3f3f3f3f;typedef __int64 ll;ll dis[N][N];int sex[N];int u[M],d[M],l[M],r[M],s[M],col[M],row[M],h[M],sta[M];int n,m,num,boy,ans;ll D;bool flag;void init(){    memset(h,0,sizeof(h));    memset(s,0,sizeof(s));    for(int i = 0;i <= n;i ++)    {        u[i] = d[i] = i;        r[i] = (i + 1) % (n + 1);        l[i] = (i - 1 + n + 1) % (n + 1);    }    num = n + 1;}void floyd(){    int i,j,k;    for(k = 1;k <= n;k ++)        for(i = 1;i <= n;i ++)            for(j = 1;j <= n;j ++)                dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);}void build(int i,int j){    if(h[i])    {        l[num] = l[h[i]];        r[num] = h[i];        r[l[num]] = num;        l[r[num]] = num;    }    else        h[i] = l[num] = r[num] = num;    s[j] ++;    u[num] = u[j];    d[num] = j;    d[u[num]] = num;    u[j] = num;    col[num] = j;    row[num] = i;    num ++;}void remove(int x){    for(int i = d[x];i != x;i = d[i])        l[r[i]] = l[i],r[l[i]] = r[i],s[col[i]] --;}void resume(int x){    for(int i = d[x];i != x;i = d[i])        l[r[i]] = r[l[i]] = i,s[col[i]] ++;}int A(){    int i,j,k,ret = 0;    bool vis[N];    memset(vis,false,sizeof(vis));    for(i = r[0];i;i = r[i])    {        if(vis[i] == false)        {            vis[i] = true;            ret ++;            for(j = d[i];j != i;j = d[j])                for(k = r[j];k != j;k = r[k])                    vis[col[k]] = true;        }    }    return ret;}void dfs(int dp){    if(dp + A() > boy)        return;    int i,j,cur;    for(i = j = 0;i < dp;i ++)        j += sex[sta[i]];    if(dp - j >= ans)        return;    if(r[0] == 0)    {        flag = true;        for(i = j = 0;i < dp;i ++)            j += sex[sta[i]];//统计boy        ans = min(ans,dp - j);        return;    }    int tmp = inf;    for(i = r[0];i;i = r[i])        if(s[i] < tmp)        {            tmp = s[i];            cur = i;        }    for(i = d[cur];i != cur;i = d[i])    {        sta[dp] = row[i];        remove(i);        for(j = r[i];j != i;j = r[j])        {            remove(j);            s[col[j]] --;        }        dfs(dp + 1);        for(j = l[i];j != i;j = l[j])        {            resume(j);            s[col[j]] ++;        }        resume(i);    }}int main(){    int t,i,j,cas = 0;    int a,b;    ll w;    scanf("%d",&t);    while(t --)    {        scanf("%d%I64d",&n,&D);        init();        for(i = 1,boy = 0;i <= n;i ++)        {            scanf("%d",&sex[i]);            boy += sex[i];            for(j = 1;j <= n;j ++)                dis[i][j] = inf;            dis[i][i] = 0;        }        for(i = 1;i < n;i ++)        {            scanf("%d%d%I64d",&a,&b,&w);            dis[a][b] = dis[b][a] = min(dis[a][b],w);        }        floyd();        for(i = 1;i <= n;i ++)        {            for(j = 1;j <= n;j ++)                if(dis[i][j] <= D)                    build(i,j);        }        ans = inf;        flag = false;        dfs(0);        if(flag == false)            ans = -1;        printf("Case #%d: %d\n",++cas,ans);    }    return 0;}