1. hust 1017 DLX精确覆盖 模板题
勉强写了注释，但还是一脸懵逼，感觉插入方式明显有问题但又不知道哪里不对而且好像能得出正确结果真是奇了怪了
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const int inf = 0x3f3f3f3f;
const int maxk = 1e5+;
const int maxn = 1e4+; //第一行为虚拟行，是人为加上的，一共有m+1个点（第一个点独立于整个矩阵）
//而后加入的值为1的点标号用size表示
//即第一行一共m+1个点，所以size先从0~m，之后每加入一个为1的点，size++
//大部分数组X都用X[size]来标识标号为size的点的信息
struct DLX {
int n, m, size, fin;
int U[maxn], D[maxn], L[maxn], R[maxn];//上下左右
int head[maxn], S[maxn]; //分别存每一行第一个1的点的标号和每一列1的个数
int row[maxn], col[maxn], ans[maxn]; //row,col表示第size个点在哪一行/列 void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ ) //初始化第一行（人为增加的虚拟行）
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
}
R[m] = ; L[] = m; //第一行的最后一个元素指向第一个
size = m; //从m开始以后都是普通节点
memset( head, -, sizeof(head) );
head[] = ;
} void link( int r, int c )
{
size++; //得到新的点标号
col[size] = c; //第size个点在第c列
row[size] = r; //第size个点在第r行
S[c]++; //第c列1的个数+1 //组成一个环，和下面左右一样的插法
D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; //如果该行没有为1的节点
if ( head[r] < ) head[r] = L[size] = R[size] = size;
else
{
//组成一个环,插在head[r]和head[r]右边那个元素中间
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int c ) //删除列c及其所在行
{
L[R[c]] = L[c]; R[L[c]] = R[c]; //c的左右两个节点互相连接
for ( int i = D[c]; i != c; i = D[i] ) //屏蔽c列
for ( int j = R[i]; j != i; j = R[j] )
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[col[j]]; //j所在的列的1的数目数减少
}
} void resume( int 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;
++S[col[j]];
}
L[R[c]] = R[L[c]] = c;
} bool dance( int d )
{
if ( R[] == ) //第0行没有节点
{
fin = d;
return true;
} //找出含1数目最小的一列
int mark = R[];
for ( int i = R[]; i != ; i = R[i] )
if ( S[i] < S[mark] )
mark = i; remove(mark); //移除列mark的1的对应行
for ( int i = D[mark]; i != mark; i = D[i] )
{
ans[d] = row[i];
//移除该行的1的对应列
for ( int j = R[i]; j != i; j = R[j] )
remove(col[j]); if ( dance(d+) )
return true; //倒着恢复
for ( int j = L[i]; j != i; j = L[j] )
resume(col[j]);
}
resume(mark);
return false;
}
}dlx; int main()
{
//freopen("F:\\cpp\\test.txt","r",stdin); int n, m;
while ( ~scanf("%d %d", &n, &m) )
{
dlx.init(n,m);
for ( int i = ; i <= n; i++ )
{
int num, j;
scanf("%d",&num);
while (num--)
{
scanf("%d",&j);
dlx.link(i,j);
}
} if ( dlx.dance() )
{
printf( "%d", dlx.fin );
for ( int i = ; i < dlx.fin; i++ )
printf( " %d", dlx.ans[i] );
printf( "\n" );
//continue;
}
else
printf("NO\n");
} return ;
}
2. ZOJ 3209 矩阵映射DLX精确覆盖
给一个大矩阵和p个小矩阵，问在p个小矩阵中能否取若干个使它们覆盖整个大矩阵，并且小矩阵间两两互不覆盖。
把大矩阵分为1-n*m个小块（就是横竖切割n和m次），则题目的要求就变成了每个小块都要被一个且仅能有一个小矩阵覆盖，然后就是映射了，因为每个小矩阵能覆盖1~n*m这么多编号小块中的某些块，那么我们让每个小矩阵为1行，并设n*m列，则题目就变成p行n*m列的矩阵对其求精确覆盖了
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const int inf = 0x3f3f3f3f;
const int maxk = 1e5+;
const int maxn = 1e5; struct DLX {
int n, m, size, fin;
int U[maxn], D[maxn], L[maxn], R[maxn]; //上下左右
int head[maxn], S[maxn]; //分别存每一行第一个1的点的标号和每一列1的个数
int row[maxn], col[maxn], ans[maxn]; //row,col表示第size个点在哪一行/列 void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ ) //初始化第一行（人为增加的虚拟行）
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
}
R[m] = ; L[] = m; //第一行的最后一个元素指向第一个
fin = -; size = m; //从m开始以后都是普通节点
memset( head, -, sizeof(head) );
} void link( int r, int c )
{
size++; //得到新的点标号
col[size] = c; //第size个点在第c列
row[size] = r; //第size个点在第r行
S[c]++; //第c列1的个数+1 //组成一个环，和下面左右一样的插法
D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; //如果该行没有为1的节点
if ( head[r] < ) head[r] = L[size] = R[size] = size;
else
{
//组成一个环,插在head[r]和head[r]右边那个元素中间
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int c ) //删除列c及其所在行
{
L[R[c]] = L[c]; R[L[c]] = R[c]; //c的左右两个节点互相连接
for ( int i = D[c]; i != c; i = D[i] ) //屏蔽c列
for ( int j = R[i]; j != i; j = R[j] )
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[col[j]]; //j所在的列的1的数目数减少
}
} void resume( int 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;
++S[col[j]];
}
L[R[c]] = R[L[c]] = c;
} void dance( int d )
{
if ( fin != - && fin <= d )
return;
if ( R[] == ) //第0行没有节点
{
fin = d;
return;
} //找出含1数目最小的一列
int mark = R[];
for ( int i = R[]; i != ; i = R[i] )
if ( S[i] < S[mark] )
mark = i; remove(mark); //移除列mark的1的对应行
for ( int i = D[mark]; i != mark; i = D[i] )
{
ans[d] = row[i];
//移除该行的1的对应列
for ( int j = R[i]; j != i; j = R[j] )
remove(col[j]); dance(d+); //倒着恢复
for ( int j = L[i]; j != i; j = L[j] )
resume(col[j]);
}
resume(mark); return;
}
}dlx; int pos[][]; int main()
{
freopen("F:\\cpp\\test.txt","r",stdin); int n, m, p;
int x1, x2, y1, y2;
int T; cin >> T;
while (T--)
{
scanf("%d %d %d", &n, &m, &p);
dlx.init(p, n*m); int id = ;
for ( int i = ; i <= n; i++ )
for ( int j = ; j <= m; j++ )
pos[i][j] = id++; for ( int r = ; r <= p; r++ )
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
//注意对应的规则
for ( int i = x1+; i <= x2; i++ )
for ( int j = y1+; j <= y2; j++ )
dlx.link( r, pos[i][j] );
} dlx.dance();
printf("%d\n", dlx.fin);
} return ;
}
懒得修改了...直接贴另一种返回
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const int inf = 0x3f3f3f3f;
const int maxk = 1e5+;
const int maxn = 1e5; struct DLX {
int n, m, size, fin;
int U[maxn], D[maxn], L[maxn], R[maxn]; //上下左右
int head[maxn], S[maxn]; //分别存每一行第一个1的点的标号和每一列1的个数
int row[maxn], col[maxn], ans[maxn]; //row,col表示第size个点在哪一行/列 void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ ) //初始化第一行（人为增加的虚拟行）
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
}
R[m] = ; L[] = m; //第一行的最后一个元素指向第一个
fin = -; size = m; //从m开始以后都是普通节点
memset( head, -, sizeof(head) );
} void link( int r, int c )
{
size++; //得到新的点标号
col[size] = c; //第size个点在第c列
row[size] = r; //第size个点在第r行
S[c]++; //第c列1的个数+1 //组成一个环，和下面左右一样的插法
D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; //如果该行没有为1的节点
if ( head[r] < ) head[r] = L[size] = R[size] = size;
else
{
//组成一个环,插在head[r]和head[r]右边那个元素中间
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int c ) //删除列c及其所在行
{
L[R[c]] = L[c]; R[L[c]] = R[c]; //c的左右两个节点互相连接
for ( int i = D[c]; i != c; i = D[i] ) //屏蔽c列
for ( int j = R[i]; j != i; j = R[j] )
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[col[j]]; //j所在的列的1的数目数减少
}
} void resume( int 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;
++S[col[j]];
}
L[R[c]] = R[L[c]] = c;
} bool dance( int d )
{
if ( fin != - && fin <= d )
return false;
if ( R[] == ) //第0行没有节点
{
fin = d;
return true;
} //找出含1数目最小的一列
int mark = R[];
for ( int i = R[]; i != ; i = R[i] )
if ( S[i] < S[mark] )
mark = i; remove(mark); //移除列mark的1的对应行
for ( int i = D[mark]; i != mark; i = D[i] )
{
ans[d] = row[i];
//移除该行的1的对应列
for ( int j = R[i]; j != i; j = R[j] )
remove(col[j]); dance(d+); //倒着恢复
for ( int j = L[i]; j != i; j = L[j] )
resume(col[j]);
}
resume(mark); return false;
}
}dlx; int pos[][]; int main()
{
freopen("F:\\cpp\\test.txt","r",stdin); int n, m, p;
int x1, x2, y1, y2;
int T; cin >> T;
while (T--)
{
scanf("%d %d %d", &n, &m, &p);
dlx.init(p, n*m); int id = ;
for ( int i = ; i <= n; i++ )
for ( int j = ; j <= m; j++ )
pos[i][j] = id++; for ( int r = ; r <= p; r++ )
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
//注意对应的规则
for ( int i = x1+; i <= x2; i++ )
for ( int j = y1+; j <= y2; j++ )
dlx.link( r, pos[i][j] );
} dlx.dance();
printf("%d\n", dlx.fin);
} return ;
}
3.HDU 2295 圆形重复覆盖+二分
一脸懵逼逼逼....如果说之前那个模板还勉强看的懂...这个就完全懵逼了（还非常容易写错）。题目比较简单就不说了
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = 1e4;
const int maxn = ; struct DLX {
int n, m, size, fin;
int U[maxk], D[maxk], L[maxk], R[maxk];
int C[maxk]; int head[maxk];
int S[maxk];
bool vis[maxk]; void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ )
{
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
S[i] = ;
}
L[] = m; R[m] = ;
size = m;
memset( head, -, sizeof(head) );
} void link( int r, int c )
{
size++;
C[size] = c;
S[c]++; D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; if ( head[r] < )
head[r] = L[size] = R[size] = size;
else
{
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int id )
{
for ( int i = D[id]; i != id; i = D[i] )
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
} void resume( int id )
{
for ( int i = D[id]; i != id; i = D[i] )
L[R[i]] = R[L[i]] = i;
} int h()
{
int sum = ;
memset( vis, , sizeof(vis) );
for ( int i = R[]; i != ; i = R[i] )
if (!vis[i])
{
sum++;
for ( int j = D[i]; j != i; j = D[j] )
for ( int k = R[j]; k != j; k = R[k] )
vis[C[k]] = ;
}
return sum;
} void dance( int k )
{
int mark, mmin = inf;
if ( k + h() >= fin )
return;
if ( R[] == )
{
if ( k < fin )
fin = k;
return;
} for ( int i = R[]; i != ; i = R[i] )
if ( mmin > S[i] )
{
mmin = S[i];
mark = i;
} for ( int i = D[mark]; i != mark; i = D[i] )
{
remove(i);
for ( int j = R[i]; j != i; j = R[j] ) remove(j);
dance(k+);
for ( int j = R[i]; j != i; j = R[j] ) resume(j);
resume(i);
}
}
}dlx; double mmap[maxn][];
double cir[maxn][]; void init( int n, int m )
{
for ( int i = ; i <= n; i++ )
scanf("%lf %lf", &mmap[i][], &mmap[i][]);
for ( int i = ; i <= m; i++ )
scanf("%lf %lf", &cir[i][], &cir[i][]);
} double getdis( int i, int j )
{
double a = mmap[i][] - cir[j][];
double b = mmap[i][] - cir[j][];
a *= a; b *= b;
return sqrt(a+b);
} bool judge( int n, int m, int k, double r )
{
dlx.init(m, n); dlx.fin = inf; for ( int i = ; i <= n; i++ )
for ( int j = ; j <= m; j++ )
{
if ( r >= getdis(i,j) )
dlx.link(j,i);
}
dlx.dance();
if ( dlx.fin <= k ) return ;
else return ;
} int main()
{
#ifdef local
freopen("F:\\cpp\\test.txt","r",stdin);
#endif int n, m, k;
int T; cin >> T;
while (T--)
{
scanf("%d %d %d", &n, &m, &k);
init(n,m); double mid, lhs = 0.0, rhs = 1000.0;
while ( rhs - lhs > eps )
{
mid = (lhs+rhs) / ;
if ( judge(n,m,k,mid) )
rhs = mid;
else
lhs = mid;
}
printf("%.6lf\n", (lhs+rhs)/);
}
return ;
}
4.FZU 1686 矩形重复覆盖
原来DLX主要是考察建模啊，模板实在不想每次都打一遍了...直接ctrl+c
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = ;
const int maxn = ; struct DLX {
int n, m, size, fin;
int U[maxk], D[maxk], L[maxk], R[maxk];
int C[maxk]; int head[maxk];
int S[maxk];
bool vis[maxk]; void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ )
{
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
S[i] = ;
}
L[] = m; R[m] = ;
fin = inf; size = m;
memset( head, -, sizeof(head) );
} void link( int r, int c )
{
size++;
C[size] = c;
S[c]++; D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; if ( head[r] < )
head[r] = L[size] = R[size] = size;
else
{
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int id )
{
for ( int i = D[id]; i != id; i = D[i] )
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
} void resume( int id )
{
for ( int i = D[id]; i != id; i = D[i] )
L[R[i]] = R[L[i]] = i;
} int h()
{
int sum = ;
memset( vis, , sizeof(vis) );
for ( int i = R[]; i != ; i = R[i] )
if (!vis[i])
{
sum++;
for ( int j = D[i]; j != i; j = D[j] )
for ( int k = R[j]; k != j; k = R[k] )
vis[C[k]] = ;
}
return sum;
} void dance( int k )
{
int mark, mmin = inf;
if ( k + h() >= fin )
return;
if ( R[] == )
{
if ( k < fin )
fin = k;
return;
} for ( int i = R[]; i != ; i = R[i] )
if ( mmin > S[i] )
{
mmin = S[i];
mark = i;
} for ( int i = D[mark]; i != mark; i = D[i] )
{
remove(i);
for ( int j = R[i]; j != i; j = R[j] ) remove(j);
dance(k+);
for ( int j = R[i]; j != i; j = R[j] ) resume(j);
resume(i);
}
}
}dlx; int mmap[][], g[][]; void init()
{
memset( mmap, , sizeof(mmap) );
memset( g, , sizeof(g) );
} int main()
{
#ifdef local
freopen("F:\\cpp\\test.txt","r",stdin);
#endif int R, C, r, c;
while ( ~scanf("%d %d", &R, &C) )
{
init();
int cnt = ;
for ( int i = ; i <= R; i++ )
for (int j = ; j <= C; j++)
{
scanf("%d", &mmap[i][j]);
if ( mmap[i][j] )
g[i][j] = ++cnt;
}
scanf("%d %d", &r, &c);
dlx.init( (R-r+)*(C-c+), cnt ); cnt = ;
for ( int i = ; i+r- <= R; i++ )
for ( int j = ; j+c- <= C; j++ )
{
for ( int a = i; a <= i+r-; a++ )
for ( int b = j; b <= j + c - ; b++ )
if (g[a][b])
dlx.link(cnt, g[a][b]);
cnt++;
}
dlx.dance();
printf("%d\n", dlx.fin);
} return ;
}
5.POJ 3074
求解数独....emmmm我得好好理解下才行
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <time.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = 1e8;
const int maxn = ; struct node {
int x, y, k;
}e[]; struct DLX {
int n, m, size, fin;
int U[maxn], D[maxn], L[maxn], R[maxn];//上下左右
int head[maxn], S[maxn]; //分别存每一行第一个1的点的标号和每一列1的个数
int row[maxn], col[maxn], ans[maxn]; //row,col表示第size个点在哪一行/列 void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ ) //初始化第一行（人为增加的虚拟行）
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
}
R[m] = ; L[] = m; //第一行的最后一个元素指向第一个
size = m; //从m开始以后都是普通节点
memset( head, -, sizeof(head) );
head[] = ;
} void link( int r, int c )
{
size++; //得到新的点标号
col[size] = c; //第size个点在第c列
row[size] = r; //第size个点在第r行
S[c]++; //第c列1的个数+1 //组成一个环，和下面左右一样的插法
D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; //如果该行没有为1的节点
if ( head[r] < ) head[r] = L[size] = R[size] = size;
else
{
//组成一个环,插在head[r]和head[r]右边那个元素中间
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int c ) //删除列c及其所在行
{
L[R[c]] = L[c]; R[L[c]] = R[c]; //c的左右两个节点互相连接
for ( int i = D[c]; i != c; i = D[i] ) //屏蔽c列
for ( int j = R[i]; j != i; j = R[j] )
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[col[j]]; //j所在的列的1的数目数减少
}
} void resume( int 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;
++S[col[j]];
}
L[R[c]] = R[L[c]] = c;
} bool dance( int d )
{
if ( R[] == ) //第0行没有节点
{
fin = d;
return true;
} //找出含1数目最小的一列
int mark = R[];
for ( int i = R[]; i != ; i = R[i] )
if ( S[i] < S[mark] )
mark = i; remove(mark); //移除列mark的1的对应行
for ( int i = D[mark]; i != mark; i = D[i] )
{
ans[d] = row[i];
//移除该行的1的对应列
for ( int j = R[i]; j != i; j = R[j] )
remove(col[j]); if ( dance(d+) )
return true; //倒着恢复
for ( int j = L[i]; j != i; j = L[j] )
resume(col[j]);
}
resume(mark);
return false;
}
}dlx; int mmap[][];
char sudoku[]; void read()
{
dlx.init(,);
int row = ; for ( int i = ; i <= ; i++ )
for ( int j = ; j <= ; j++ )
{
if ( !mmap[i][j] )
{
for ( int k = ; k <= ; k++ )
{
++row;
dlx.link(row, (i-)*+j);
dlx.link(row, +(i-)*+k);
dlx.link(row, +(j-)*+k);
dlx.link(row,+(((i-)/)*+(j+)/-)*+k);
e[row].x = i; e[row].y = j; e[row].k = k;
}
}
else
{
++row;
int k = mmap[i][j];
dlx.link(row, (i-)*+j);
dlx.link(row, +(i-)*+k);
dlx.link(row, +(j-)*+k);
dlx.link(row, +(((i-)/)*+(j+)/-)*+k);
e[row].x = i; e[row].y = j; e[row].k = k;
}
} } void init()
{
int t = ; for ( int i = ; i <= ; i++ )
for ( int j = ; j <= ; j++ )
{
if ( sudoku[++t] != '.' )
mmap[i][j] = sudoku[t] - '';
else
mmap[i][j] = ;
} read();
} int main()
{
//freopen("F:\\cpp\\test.txt", "r", stdin ); while ( ~scanf("%s", sudoku+) )
{
if (sudoku[] == 'e') break;
init(); dlx.dance();
for ( int i = ; i < dlx.fin; i++ )
{
int tmp = dlx.ans[i];
sudoku[(e[tmp].x-)* + e[tmp].y-] = ''+e[tmp].k;
}
sudoku[dlx.fin] = '\0';
printf("%s\n", sudoku);
} return ;
}
6. HDU 5046
和hdu2295基本一样，有个可以优化的方法是将可行的距离排序后二分下标，如果不这样做直接二分，左右区间要到1~4e9才行，而且大概率TLE（交了一发1300ms）
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <time.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = ;
const int maxn = ; int N, K; struct DLX {
int n, m, size, fin;
int U[maxk], D[maxk], L[maxk], R[maxk];
int C[maxk]; int head[];
int S[];
bool vis[maxk]; void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ )
{
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
S[i] = ;
}
L[] = m; R[m] = ;
size = m;
memset( head, -, sizeof(head) );
} void link( int r, int c )
{
size++;
C[size] = c;
S[c]++; D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; if ( head[r] < )
head[r] = L[size] = R[size] = size;
else
{
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int id )
{
for ( int i = D[id]; i != id; i = D[i] )
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
} void resume( int id )
{
for ( int i = D[id]; i != id; i = D[i] )
L[R[i]] = R[L[i]] = i;
} int h()
{
int sum = ;
memset( vis, , sizeof(vis) );
for ( int i = R[]; i != ; i = R[i] )
if (!vis[i])
{
sum++;
for ( int j = D[i]; j != i; j = D[j] )
for ( int k = R[j]; k != j; k = R[k] )
vis[C[k]] = ;
}
return sum;
} void dance( int k )
{
int mark, mmin = inf;
int tmp = k + h();
if ( tmp >= fin || tmp > K )
return;
if ( R[] == )
{
if ( k < fin )
fin = k;
return;
} for ( int i = R[]; i != ; i = R[i] )
if ( mmin > S[i] )
{
mmin = S[i];
mark = i;
} for ( int i = D[mark]; i != mark; i = D[i] )
{
remove(i);
for ( int j = R[i]; j != i; j = R[j] ) remove(j);
dance(k+);
for ( int j = R[i]; j != i; j = R[j] ) resume(j);
resume(i);
}
}
}dlx; int cnt;
int g[][]; struct mmap {
int x, y;
LL dist;
bool operator < ( const mmap &a ) const
{ return dist < a.dist; }
}node[*]; LL getdist( int i, int j )
{
LL x = abs(g[i][]-g[j][]);
LL y = abs(g[i][]-g[j][]);
return x+y;
} void init( int n )
{
cnt = ;
for( int i = ; i <= n; i++ )
scanf("%d %d", &g[i][], &g[i][] );
for ( int i = ; i <= n; i++ )
for ( int j = i; j <= n; j++ )
{
node[cnt].x = i; node[cnt].y = j;
node[cnt++].dist = getdist(i,j);
}
sort(node, node+cnt);
} bool judge( int n, int k, LL mid )
{
dlx.init(n, n); dlx.fin = k+; for ( int i = ; i < cnt; i++ )
{
if ( node[i].dist > mid ) break; dlx.link( node[i].x, node[i].y );
if ( node[i].x != node[i].y )
dlx.link( node[i].y, node[i].x );
} dlx.dance();
if ( dlx.fin <= k )
return true;
else
return false;
} LL solve( int n, int k )
{
LL mid, lhs = , rhs = cnt;
while ( lhs <= rhs )
{
mid = (lhs+rhs)>>;
if ( judge(n,k,node[mid].dist) )
rhs = mid-;
else
lhs = mid+;
} if ( judge(n,k,node[lhs].dist) )
return node[lhs].dist;
else
return node[rhs].dist;
} int main()
{
//freopen("F:\\cpp\\test.txt", "r", stdin ); int T; cin >> T;
int n, k, cnt = ;
while (T--)
{
scanf("%d %d", &n, &k);
N = n; K = k;
init(n);
printf("Case #%d: %lld\n", cnt++, solve(n,k));
} return ;
}
7.ZOJ 3122
16个数字的数独，和9个数字的数独其实一样，这次加了注释，终于理解了...然后dlx范围老是调不好
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <time.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a,LL b) { return a>b?a:b; }
inline LL LMin(LL a,LL b) { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = 1e5;
const int maxn = ; //行：16x16x16=4096表示每个格子有16种选择
//列：(16x16)x3=768，表示16行16列16小块每个各有16种数字单独存在
//列：还要加上768+16x16=1024，表示每个格子只能有一个数字 struct DLX {
int n, m, size, fin;
int U[maxk], D[maxk], L[maxk], R[maxk];//上下左右
int head[maxk], S[maxk]; //分别存每一行第一个1的点的标号和每一列1的个数
int row[maxk], col[maxk], ans[maxk]; //row,col表示第size个点在哪一行/列 void init( int _n, int _m )
{
n = _n; m = _m;
for ( int i = ; i <= m; i++ ) //初始化第一行（人为增加的虚拟行）
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i-;
R[i] = i+;
}
R[m] = ; L[] = m; //第一行的最后一个元素指向第一个
size = m; //从m开始以后都是普通节点
memset( head, -, sizeof(head) );
head[] = ;
} void link( int r, int c )
{
size++; //得到新的点标号
col[size] = c; //第size个点在第c列
row[size] = r; //第size个点在第r行
S[c]++; //第c列1的个数+1 //组成一个环，和下面左右一样的插法
D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size; //如果该行没有为1的节点
if ( head[r] < ) head[r] = L[size] = R[size] = size;
else
{
//组成一个环,插在head[r]和head[r]右边那个元素中间
R[size] = R[head[r]];
L[R[size]] = size;
L[size] = head[r];
R[head[r]] = size;
}
} void remove( int c ) //删除列c及其所在行
{
L[R[c]] = L[c]; R[L[c]] = R[c]; //c的左右两个节点互相连接
for ( int i = D[c]; i != c; i = D[i] ) //屏蔽c列
for ( int j = R[i]; j != i; j = R[j] )
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[col[j]]; //j所在的列的1的数目数减少
}
} void resume( int 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;
++S[col[j]];
}
L[R[c]] = R[L[c]] = c;
} bool dance( int d )
{
if ( R[] == ) //第0行没有节点
{
fin = d;
return true;
} //找出含1数目最小的一列
int mark = R[];
for ( int i = R[]; i != ; i = R[i] )
if ( S[i] < S[mark] )
mark = i; remove(mark); //移除列mark的1的对应行
for ( int i = D[mark]; i != mark; i = D[i] )
{
ans[d] = row[i];
//移除该行的1的对应列
for ( int j = R[i]; j != i; j = R[j] )
remove(col[j]); if ( dance(d+) )
return true; //倒着恢复
for ( int j = L[i]; j != i; j = L[j] )
resume(col[j]);
}
resume(mark);
return false;
}
}dlx; char mmap[][];
char sudoku[][];
struct node {
int x, y, k;
}e[maxk]; void init()
{
//4096行，1024列
dlx.init(,);
int row = ; for ( int i = ; i <= ; i++ )
for ( int j = ; j <= ; j++ )
{
if ( mmap[i][j] == '-' )
for (int k = ; k <= ; k++ )
{
row++;
dlx.link(row, (i-)*+j ); //第i行第j个格子已经填了数字
dlx.link(row, +(i-)*+k); //第i行已经填了数字k
dlx.link(row, +(j-)*+k); //第j列已经填了数字k
dlx.link(row, +(((i-)/)* + (j-)/)*+k); //第xxx个格子已经填了数字k
e[row].x = i; e[row].y = j; e[row].k = k;
}
else
{
row++;
int k = mmap[i][j] - 'A' + ;
dlx.link(row, (i-)*+j);
dlx.link(row, +(i-)*+k);
dlx.link(row, +(j-)*+k);
dlx.link(row, +(((i-)/)* + (j-)/)*+k);
e[row].x = i; e[row].y = j; e[row].k = k;
}
}
} int main()
{
//freopen("F:\\cpp\\test.txt", "r", stdin ); int cnt = ;
while ()
{
if ( ~scanf("%s", mmap[]+) )
{
for ( int i = ; i <= ; i++ )
scanf("%s", mmap[i]+); if (cnt++)
printf("\n"); init();
dlx.dance(); int tmp;
for ( int i = ; i < dlx.fin; i++ )
{
tmp = dlx.ans[i];
sudoku[e[tmp].x-][e[tmp].y-] = e[tmp].k + 'A' - ;
sudoku[e[tmp].x-][] = '\0';
}
for ( int i = ; i < ; i++ )
printf("%s\n", sudoku[i]);
}
else
break;
}
}