专栏首页Zaqdt_ACMHUST 1017 Exact cover(DLX精确覆盖)

HUST 1017 Exact cover(DLX精确覆盖)

       题意是给了n*m的01矩阵,选择最少的行,使得每一列都恰好包含一个1,然后输出这些行


AC代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int maxm = 110;
const int maxnode = 110 * 110;
int L[maxnode], R[maxnode], U[maxnode], D[maxnode];
int C[maxnode],H[maxn],cnt[maxm],vis[maxn],ans[maxn],Row[maxnode];
int n,m,id,len;

void init(){
    for(int i=0;i<=m;i++){
        cnt[i] = 0; U[i] = D[i] = i;
        L[i + 1] = i; R[i] = i + 1;
    }
    R[m] = 0; id = m + 1;
    memset(H, -1, sizeof(H));
}

void Link(int r, int c){
    cnt[c]++; C[id] = c; Row[id] = r;
    U[id] = U[c]; D[ U[c] ] = id;
    D[id] = c; U[c] = id; Row[id] = r;
    if(H[r] == -1) H[r] = L[id] = R[id] = id;
    else{
        L[id] = L[ H[r] ]; R[ L[ H[r] ] ] = id;
        R[id] = H[r]; L[ H[ r ] ] = id;
    }
    id++;
}

void Remove(int Size){
    L[ R[Size] ] = L[Size];
    R[ L[Size] ] = R[Size];
    for(int i=D[Size];i!=Size;i=D[i]){
        for(int j=R[i];j!=i;j=R[j]){
            U[ D[j] ] = U[j]; D[ U[j] ] = D[j];
            cnt[ C[j] ]--;
        }
    }
}

void Resume(int Size){
    for(int i=D[Size];i!=Size;i=D[i]){
        for(int j=R[i];j!=i;j=R[j]){
            U[ D[j] ] = j; D[ U[j] ] = j;
            cnt[ C[j] ]++;
        }
    }
    L[ R[Size] ] = Size;R[ L[Size] ] = Size;
}

bool DLX(int k){
    int pos,mm = maxn;
    if(R[0] == 0){
        len = k;
        return true;
    }
    for(int i=R[0];i;i=R[i]){
        if(mm > cnt[i]){
            mm = cnt[i];
						pos = i;
        }
    }
    Remove(pos);
    for(int i=D[pos];i!=pos;i=D[i]){
        ans[k] = Row[i];
        for(int j=R[i];j!=i;j=R[j]) Remove(C[j]);
        if(DLX(k + 1)) return true;
        for(int j=L[i];j!=i;j=L[j]) Resume(C[j]);
    }
    Resume(pos);
    return false;
}

int main(){
  int u,v,a;
  while(~scanf("%d%d",&n,&m)){
    init();
    for(int i=1;i<=n;i++){
      int xx;
			scanf("%d",&xx);
			for(int j=1;j<=xx;j++){
				int yy;
				scanf("%d",&yy);
				Link(i, yy);
			}
    }
    bool ans1 = DLX(0);
    if(ans1 == false) printf("No\n");
    else{
			printf("%d",len);
			for(int i=0;i<len;i++){
				printf(" %d",ans[i]);
			}
			puts("");
		}
  }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 3498 whosyourdaddy(DLX重复覆盖)

    //acm.hdu.edu.cn/showproblem.php?pid=3498

    Ch_Zaqdt
  • HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444

    Ch_Zaqdt
  • Codeforces Round #535 (Div. 3) B. Divisors of Two Integers(思维)

    题目链接:http://codeforces.com/contest/1108/problem/B

    Ch_Zaqdt
  • HDU-5985-Lucky Coins

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <cstri...

    f_zyj
  • P2733 家的范围 Home on the Range

    题目背景 农民约翰在一片边长是N (2 <= N <= 250)英里的正方形牧场上放牧他的奶牛。(因为一些原因,他的奶牛只在正方形的牧场上吃草。)遗憾的是,他的...

    attack
  • P1631 序列合并

    题目描述 有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到 个和,求这 个和中最小的N个。 输入输出格式 输入格式: 第一行一个正整数N; 第...

    attack
  • HDU-5534-Partial Tree

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <algor...

    f_zyj
  • HDU 3498 whosyourdaddy(DLX重复覆盖)

    //acm.hdu.edu.cn/showproblem.php?pid=3498

    Ch_Zaqdt
  • 蓝桥杯 基础练习 数列排序

    第一行为一个整数n。 第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    Debug客栈
  • P1629 邮递员送信

    题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

    attack

扫码关注云+社区

领取腾讯云代金券