[NPSC 2009 高中組決賽][TIOJ 1690][DLX] 補習班的報名熱

原題連結

這邊不對DLX做太多的講解，只說如何建模。

我們可以把每個人當成一個列(column)，每條邊是一個行（row)，那麼每行就只有2個1，代表著這條邊連接的兩個人。

那麼問題就變成了經典的精確覆蓋問題，即選擇一些行使得每列都恰有1個1，可以用DLX解決。

DLX最簡單的介紹在這裡
網路上可以搜尋到各種精闢的教學，就不多說了。

另外我的模板是參考Ruija大神的模板......寫得真是挺精簡的<(_ _)>

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxc=1000+5;
const int maxr=10000+5;
const int maxnode=10000*2+5;
struct DLX
{
    vector<int> column[maxr];
    int anscnt,ansd,ans[maxr],n,sz,S[maxc];
    int row[maxnode],col[maxnode];
    int L[maxnode],R[maxnode],U[maxnode],D[maxnode];
    void init(int n,int m)
    {
        this->n=n;
        anscnt=0,ansd=-1;
        for(int i=1;i<=m;i++) column[i].clear();
        for(int i=0;i<=n;i++) U[i]=i,D[i]=i,L[i]=i-1,R[i]=i+1;
        L[0]=n,R[n]=0;
        sz=n+1;
        for(int i=0;i<=n;i++) S[i]=0;
    }
    void addRow(int r)
    {
        int first=sz;
        for(int i=0;i<column[r].size();i++)
        {
            int c=column[r][i];
            L[sz]=sz-1,R[sz]=sz+1;
            D[sz]=c,U[sz]=U[c];
            D[U[c]]=sz,U[c]=sz;
            row[sz]=r,col[sz]=c;
            S[c]++;sz++;
        }
        L[first]=sz-1,R[sz-1]=first;
    }
    #define FOR(i,A,st) for(int i=A[st];i!=st;i=A[i])
    void remove(int c)
    {
        L[R[c]]=L[c];
        R[L[c]]=R[c];
        FOR(i,D,c) FOR(j,R,i) {U[D[j]]=U[j];D[U[j]]=D[j];--S[col[j]];}
    }
    void restore(int c)
    {
        FOR(i,U,c) FOR(j,L,i) {U[D[j]]=j;D[U[j]]=j;++S[col[j]];}
        L[R[c]]=c;
        R[L[c]]=c;
    }
    void dfs(int d)
    {
        if(R[0]==0)
        {
            ansd=d,anscnt++;
            return;
        }
        int c=R[0];
        FOR(i,R,0) if(S[i]<S[c]) c=i;
        
        remove(c);
        FOR(i,D,c)
        {
            ans[d]=row[i];
            FOR(j,R,i) remove(col[j]);
            dfs(d+1);
            if(anscnt>1) return;
            FOR(j,L,i) restore(col[j]);
        }
        restore(c);
    }
    void solve()
    {
        dfs(0);
        if(anscnt==0 || anscnt>1) printf("NO\n");
        else
        {
            vector<pair<int,int> > vec;
            printf("YES\n");
            for(int i=0;i<ansd;i++) vec.push_back(make_pair(column[ans[i]][0],column[ans[i]][1]));
            sort(vec.begin(),vec.end());
            for(int i=0;i<vec.size();i++) printf("%d %d\n",vec[i].first,vec[i].second);
        }
    }
}solver;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        solver.init(n,m);
        for(int i=1,a,b;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            if(a>b) swap(a,b);
            solver.column[i].push_back(a);solver.column[i].push_back(b);
            solver.addRow(i);
        }
        solver.solve();
    }
}