CosmicBlocks - TopCoder- 12034 (网络流)

注意题目定义的同构是存在不同的颜色覆盖关系，而不是存在不同的排列顺序

所以先枚举每一层放了那些颜色，再枚举那些颜色之间有覆盖

每一层的颜色划分数很少，最多可能同时存在的覆盖关系是$9$种，枚举复杂度最多是$2^9$，然后可以$2^n\cdot n\ \text{dp}$出拓扑序列的个数

问题在于如何快速又方便地判断对于当前情况是否存在方案

一种方法是上下界网络流

按照层之间的关系，覆盖关系就连$[1,+\infty)$的边，同时源点向$1$层的点连$[0,+\infty)$的边，每个点都向汇点连$[0,\infty)$的边

注意由于要限制流过每个点的流量，每个点要拆成两个点中间连$[num_i,num_i]$的边

最后判断一下有源汇可行流即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<bits/stdc++.h>
using namespace std;

#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}



static const int N=20,INF=1e8+10;
int n,m,ans,L,R;
int cnt[N],id[N];
vector <int> G[N];
int GS[N];
vector <int> Layer[N];

int Calc_DAG() { // 计算拓扑序列的个数
	static int dp[1<<6];
	int A=(1<<n)-1;
	rep(i,0,A) dp[i]=0;
	dp[0]=1;
	rep(S,0,A-1) rep(i,0,n-1) if((~S&(1<<i)) && (S&GS[i+1])==GS[i+1]) dp[S|(1<<i)]+=dp[S];
	return dp[A];
}

int ind[N];
struct Limited_Flow{ // 有源汇可行流
	static const int M=300;
	int S,T;
	struct Edge{
		int to,nxt,w;
	} e[M];
	int head[N],ecnt;
	void clear(){
		rep(i,1,n*2+4) head[i]=0;
		ecnt=0;
	}
	#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
	void AddEdge(int u,int v,int w) { e[ecnt]=(Edge){v,head[u],w},head[u]=ecnt++; } 
	void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,0); }
	int dis[N];

	int Bfs(){
		static queue <int> que;
		rep(i,1,T) dis[i]=INF; dis[S]=0,que.push(S);
		while(!que.empty()) {
			int u=que.front(); que.pop();
			erep(u,i) {
				int v=e[i].to,w=e[i].w;
				if(!w || dis[v]<=dis[u]+1) continue;
				dis[v]=dis[u]+1,que.push(v);
			}
		}
		return dis[T]<INF;
	}
	int Dfs(int u,int flowin){
		if(u==T) return flowin;
		int flowout=0;
		erep(u,i) {
			int v=e[i].to,w=e[i].w;
			if(!w || dis[v]!=dis[u]+1) continue;
			int t=Dfs(v,min(flowin-flowout,w));
			e[i].w-=t,e[i^1].w+=t,flowout+=t;
			if(flowin==flowout) break;
		}
		if(!flowout) dis[u]=0;
		return flowout;
	}
	int Dinic(){
		int ans=0;
		while(Bfs()) ans+=Dfs(S,INF);
		return ans;
	}
	int Check(){
		erep(S,i) if(e[i].w) return 0;
		erep(T,i) if(e[i^1].w) return 0;
		return 1;
	}
} Flow;

void Extend_Edge(int u,int v,int L,int R){
	ind[u]-=L,ind[v]+=L;
	Flow.Link(u,v,R-L);
}

int Check(){
	rep(i,1,n*2+4) ind[i]=0;
	Flow.clear();
	rep(i,1,n) Extend_Edge(i*2-1,i*2,cnt[i],cnt[i]);
	rep(i,1,n) if(id[i]==1) Extend_Edge(n*2+1,i*2-1,cnt[i],cnt[i]);
	rep(u,1,n) for(int v:G[u]) Extend_Edge(u*2,v*2-1,1,INF);
	rep(i,1,n) Extend_Edge(i*2,n*2+2,0,INF);
	Extend_Edge(n*2+2,n*2+1,0,INF);

	rep(i,1,n*2+2) {
		if(ind[i]>0) Flow.Link(n*2+3,i,ind[i]);
		if(ind[i]<0) Flow.Link(i,n*2+4,-ind[i]);
	}
	Flow.S=n*2+3,Flow.T=n*2+4;

	Flow.Dinic();
	return Flow.Check();
}

void Dfs_GetDAG(int p) { // dfs枚举覆盖关系
	if(p==n+1) {
		int Ways=Calc_DAG();
		if(Ways<L || Ways>R) return;
		ans+=Check();
		return;
	}
	if(id[p]==m) return Dfs_GetDAG(p+1);
	int n=Layer[id[p]+1].size();
	rep(S,0,(1<<n)-1) {
		rep(i,0,n-1) if(S&(1<<i)) G[p].pb(Layer[id[p]+1][i]),GS[p]|=1<<(Layer[id[p]+1][i]-1);
		Dfs_GetDAG(p+1);
		G[p].clear(),GS[p]=0;
	}
}

void Dfs_Getlayer(int num,int fir,int chosennumber){ // dfs枚举层的情况
	if(chosennumber==n) {
		m=num;
		rep(i,1,m) Layer[i].clear();
		rep(i,1,n) Layer[id[i]].pb(i);
		Dfs_GetDAG(1);
		return;
	}
	rep(i,fir,n) if(!id[i]) {
		id[i]=num;
		Dfs_Getlayer(num,i+1,chosennumber+1);
		id[i]=0;
	}
	if(fir!=1) Dfs_Getlayer(num+1,1,chosennumber);
}

class CosmicBlocks {
public:
	int getNumOrders(vector <int> a, int Min, int Max) {
		L=Min,R=Max;
		n=a.size(),ans=0; rep(i,0,n-1) cnt[i+1]=a[i];
		Dfs_Getlayer(1,1,0);
		return ans;
	}
};

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!