程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3209 Dancing Links

ZOJ 3209 Dancing Links

編輯：C++入門知識

ZOJ 3209 Dancing Links

思路：這題挺好的，本來模板不是自己敲的嘛，理解了Dancing Links後是找了一個模板的，然後正好這題讓自己加深理解了，也知道在實際中怎麼建矩陣求解了。

把n*m的矩陣看成n*m個格子，像那個數獨一樣，作為n*m列；每一個矩形一行。

行列都建好矩陣後，就可以用舞蹈鏈求解了。

問題即轉化為從這些行中選擇最少的一部分使每一列被覆蓋且僅覆蓋一次。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int head,sz;
int U[maxn],D[maxn],L[maxn],R[maxn];//上下左右鏈表指針
int H[maxn],ROW[maxn],C[maxn],S[maxn],O[maxn];
void remove(int c)
{
    L[R[c]]=L[c];
    R[L[c]]=R[c];
    for(int i=D[c]; i!=c; i=D[i])
        for(int j=R[i]; j!=i; j=R[j])
        {
            U[D[j]]=U[j];
            D[U[j]]=D[j];
            --S[C[j]];
        }
}
void resume(int c)
{
    for(int i=U[c]; i!=c; i=U[i])
    {
        for(int j=L[i]; j!=i; j=L[j])
        {
            ++S[C[j]];
            U[D[j]]=j;
            D[U[j]]=j;
        }
    }
    L[R[c]]=c;
    R[L[c]]=c;
}
void init(int m)//m是列
{
    head=0;//頭指針為0
    for(int i=0; i<=m; i++)
    {
        U[i]=i;
        D[i]=i;//建立雙向十字鏈表
        L[i]=i-1;
        R[i]=i+1;
        S[i]=0;
    }
    R[m]=0;
    L[0]=m;
    S[0]=INF+1;
    sz=m+1;
    memset(H,0,sizeof(H));
}
void insert(int i, int j)
{
    if(H[i])
    {
        L[sz] = L[H[i]];
        R[sz] = H[i];
        L[R[sz]] = sz;
        R[L[sz]] = sz;
    }
    else
    {
        L[sz] = sz;
        R[sz] = sz;
        H[i] = sz;
    }
    U[sz] = U[j];
    D[sz] = j;
    U[D[sz]] = sz;
    D[U[sz]] = sz;
    C[sz] = j;
    ROW[sz] = i;
    ++S[j];
    ++sz;
}
int ans;
void dfs(int k)
{
    if(R[head]==head)
    {
        if(ans>k) ans=k;
        return;
    }
    int s=INF,c;
    for (int t=R[head]; t!=head; t=R[t])
        if (S[t]>t;
    while(t--)
    {
        int n,m,p,i,j,k,x1,y1,x2,y2;
        scanf("%d%d%d",&n,&m,&p);
        init(n*m);
        for(i=1;i<=p;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            for(j=x1;j