TIOJ 1333 蕃茄小豆湯

TIOJ 1333 蕃茄小豆湯

題目概述:

這題就是"精確覆蓋問題"的裸題。精確覆蓋問題大概就是，假設有N組含有M個的01位元，要挑選某幾組使得涵蓋所有位元且沒有重複涵蓋。

思路:

要使用Dancing links來解。

AC code:

//By SCJ

//TIOJ 1333 蕃茄小豆湯

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define maxn 40010

#define INF 10000000

int cnt=-1,mp[202][202],U[maxn],D[maxn],L[maxn],R[maxn],C[maxn],N[maxn];

inline void remove(int 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],N[C[j]]--;

L[R[c]]=L[c],R[L[c]]=R[c];

}

inline void resume(int c)

{

L[R[c]]=R[L[c]]=c;

for(int i=U[c];i!=c;i=U[i])

for(int j=L[i];j!=i;j=L[j])

U[D[j]]=D[U[j]]=j,N[C[j]]++;

}

int ans=INF;

void dfs(int c,int dep)

{

remove(c);

for(int i=D[c];i!=c;i=D[i]){//每舉每一列

for(int j=R[i];j!=i;j=R[j]) remove(C[j]);

bool f=1;

for(int i=R[0];i;i=R[i]) if(U[i]==i) f=0;

int st,MIN=INF;

for(int i=R[0];i!=0;i=R[i]) if(N[i]<MIN) MIN=N[i],st=i;//挑最少列的行

if(R[0]&&f) dfs(st,dep+1);

else if(R[0]==0) ans=min(ans,dep);

for(int j=L[i];j!=i;j=L[j]) resume(C[j]);

}

resume(c);

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

int n,m;cin>>n>>m;

for(int i=0;i<=m;++i) mp[0][i]=++cnt;

for(int i=1;i<=n;++i) mp[i][0]=-1;

for(int i=1;i<=n;++i){

for(int j=1;j<=m;++j){

int tp;cin>>tp;

if(tp==0) mp[i][j]=-1;

else mp[i][j]=++cnt,C[mp[i][j]]=j,N[j]++;

}

}

for(int i=0;i<=n;++i)

{

for(int j=0;j<=m;++j)

{

if(mp[i][j]==-1) continue;

if(i!=0&&j==0) continue;

for(int k=(i+1)%(n+1);;k=(k+1)%(n+1))

if(mp[k][j]!=-1){D[mp[i][j]]=mp[k][j];break;}

for(int k=(i-1+n+1)%(n+1);;k=(k-1+n+1)%(n+1))

if(mp[k][j]!=-1){U[mp[i][j]]=mp[k][j];break;}

for(int k=(j+1)%(m+1);;k=(k+1)%(m+1))

if(mp[i][k]!=-1){R[mp[i][j]]=mp[i][k];break;}

for(int k=(j-1+m+1)%(m+1);;k=(k-1+m+1)%(m+1))

if(mp[i][k]!=-1){L[mp[i][j]]=mp[i][k];break;}

}

}

dfs(min_element(N+1,N+m+1)-N,1);

cout<<ans<<endl;

}