T1
Description
- 给定一个(N*N(N≤8))的矩阵，每一格有一个0~5的颜色。每次可将左上角的格子所在连通块变为一种颜色，求最少操作数。
Solution
- IDA*=启发式迭代加深
（我似乎是第一次打这东西）
- 首先我们要想到迭代加深
（这我都没想到）
- 设一个数组(v[][])。记左上角所在连通块为1，它扩展一周的位置为2。每次选取2中一种颜色i进行操作，操作时则从2中颜色为(i)的格子处(dfs)，更新(v[][])的值。当然回溯时要将所有值变回去。
- 然后设一个估价函数。如果当前矩阵中除了左上角的连通块之外，共有(M)种颜色，那么还需要的步数不小于(M)。因此如果当前搜索深度+估价函数的值>深度限制，可以回溯。
Code
#include <bits/stdc++.h>
#define S(a) memset(a,0,sizeof a);
#define C(a,b) memcpy(a,b,sizeof a);
#define fo(i,a,b) for(i=a;i<=b;i++)
#define go int k,xx,yy; fo(k,0,3)if((xx=x+v[k][0])&&xx<=n&&(yy=y+v[k][1])&&yy<=n&&!vis[xx][yy])
using namespace std;
const int N=9,v[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int i,j,n,a[N][N],V[N][N],c[6],V2[6],deep;
bool vis[N][N];
void getV(int x,int y)
{
vis[x][y]=V[x][y]=1;
c[a[x][y]]--;
go
if(a[xx][yy]==a[x][y]) getV(xx,yy); else
if(!V[xx][yy]) V[xx][yy]=2,V2[a[xx][yy]]++;
}
bool dfs(int t)
{
int i,x,y,cs=0,pV[N][N],pc[6],pV2[6];
fo(i,0,5) cs+=(bool)c[i];
if(t+cs>deep) return 0;
if(!cs) return 1;
fo(i,0,5)
if(V2[i])
{
C(pV,V) C(pc,c) C(pV2,V2)
fo(x,1,n) fo(y,1,n) if(V[x][y]==2&&a[x][y]==i)
{
V2[a[x][y]]--;
S(vis) getV(x,y);
}
if(dfs(t+1)) return 1;
C(V,pV) C(c,pc) C(V2,pV2)
}
return 0;
}
int main()
{
for(scanf("%d",&n); n; scanf("%d",&n))
{
S(c)
fo(i,1,n) fo(j,1,n) scanf("%d",&a[i][j]), c[a[i][j]]++;
S(V) S(V2) S(vis) getV(1,1);
fo(deep,0,n*n)
if(dfs(0)) break;
printf("%d
",deep);
}
}
T2
Description
- 给定一个(N(≤200))个点、(M(≤30000))条边的(DAG)，求最长反链长度。
- (DAG)中的反链：一个点集，其中的点两两不能互达
Solution
- 可以先用(Floyd)做一遍传递闭包（就是求(f[x][y])表示点(x)能否到达点(y)）。
- 如果我们把(f)数组取反，形成一个新的邻接矩阵，那么问题就转化为求最大团（团：极大完全子图）。
- 但这样很难用多项式算法解决。
- (Dilworth)定理：最长反链长度=最小链（可重复点）覆盖数。
- 这本来是应用在偏序集上的定理；但由于偏序集可与哈塞图映射，而哈塞图是一个(DAG)，故该定理也可应用在图论的(DAG)上面。
- 先定义两个东西：源为入度为0的点，汇为出度为0的点。
- 定理的证明就是用数学归纳法：1.对于某些特殊图（最长反链全部是源或汇）成立；2.对于一个图(G)，其有一个最长反链(A)，记(G)中能走到(A)的点集为(B)，(A)能走到的点集为(C)，则(Bcup C=G)且(Bcap C=A)，且(A)肯定是(B)、(C)中的一个最长反链，然后因为(B)、(C)是满足结论的（我们在用犯贱的数学归纳法），所以(A)又对应(B)、(C)的最小链（具体地说，(A)中每一个点是(B)的最小链的汇和(C)的最小链的源），故我们可将那些链两两拼接，则(G)也成立。
- 那么上面是要求可重复最小链覆盖数；我们可以对原图做一遍传递闭包，那么就转化为求不可重复最小链覆盖数。
- 不可重复最小链覆盖数=(n)（点数）-最大匹配数。具体地说，我们在二分图的左部和右部各开辟(n)个点；对于一条边(x o y)，我们用左部的(x)向右部的(y)连一条边。这样的话，我们每次匹配实际上就是将两条链合并，故答案(--)。
- 于是直接跑匈牙利即可。
Code
#include <bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int N=210;
int i,j,k,n,m,x,y,link[N],ans;
bool f[N][N],vis[N];
bool find(int x)
{
if(vis[x]) return 0;
vis[x]=1;
int y;
fo(y,1,n)
if(f[x][y]&&(!link[y]||find(link[y])))
{
link[y]=x;
return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
fo(i,1,m) scanf("%d%d",&x,&y), f[x][y]=1;
fo(k,1,n) fo(i,1,n) fo(j,1,n) f[i][j]|=f[i][k]&f[k][j];
fo(i,1,n)
{
fo(j,1,n) vis[j]=0;
ans+=find(i);
}
printf("%d",n-ans);
}
T3
Description
- 用(K(≤15))种颜色为(N)个点染色，要求第(i)种颜色使用(C_i(≤6))次，且相邻两个点颜色不能相同。求方案数。
- (T(≤2000))组询问。
Solution
- 这题应该是最水的，但腐太久降智了，完全没想到(DP)。
- 可以设个方程(f[i][j])表示用到第(i)种颜色，有(j)对相邻的点颜色相同。边界(f[0][0]=1)，答案显然是(f[K][0])。
- 转移详见(Code)。
Code
#include <cstdio>
#include <cstring>
#define min(x,y) (x<y?x:y)
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int mK=16,N=99,M=1e9+7;
int i,j,T,K,c,s,x,y;
ll C[N+1][N+1],f[mK][N];
int main()
{
fo(i,0,N)
{
C[i][0]=1;
fo(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;
}
for(scanf("%d",&T); T--;)
{
scanf("%d",&K);
s=0, f[0][0]=1;
fo(i,1,K)
{
memset(f[i],0,sizeof f[i]);
scanf("%d",&c);
fo(j,0,s)
if(f[i-1][j])
fo(x,1,c)
fo(y,0,min(x,j))
(f[i][j-y+c-x]+=f[i-1][j]*C[s+1-j][x-y]%M*C[j][y]%M*C[c-1][x-1])%=M;
s+=c;
}
printf("%lld
",f[K][0]);
}
}