博客

这是一道看起来很简单的麻题。
很显然可以发现第一问就是直接n^2DP求一个答案。
第二问模拟寻找最长不下降子序列的过程。
第三问改几条边再跑一遍。
但是要注意很多很多细节。
比如说，建模的时候应该反着建。
再比如说，对于最长长度只有1的情况应当格外注意，因为这可能会导致各种错误。
写起来还是有点烦心的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

const int INF=0x3f3f3f3f;
const int BIG=19260817;
inline int Min(int A,int B){
	return A<B?A:B;
}

inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[250005];
int h[2005],et=-1;

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int dep[2005],nw[2005],a[505];
int n,s,t,len;
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF,nw[i]=h[i];
	}
	dep[s]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
//	for(int i=1;i<=t;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	return dep[t]^INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
		}
	}
	return cnt;
}
int f[505];
inline void slv1(){
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]){
				f[i]=Max(f[i],f[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,f[i]);
	}
	len=ans;
	printf("%d\n",ans);
}

inline int dinic(){
	int RT=0;
	while(bfs()){
		RT+=dfs(s,INF);
	}
	return RT;
}

inline void slv2(){
	s=2*n+1,t=2*n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	et=-1;
	for(int i=1;i<=n;++i){
		if(f[i]==len){
			add(i+n,t,1);
		}
		if(f[i]==1){
			add(s,i,1);
		}
		add(i,i+n,1);
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]&&f[j]+1==f[i]){
				add(j+n,i,1);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
	add(1,n+1,BIG),add(s,1,BIG);
	if(f[n]==len){
		add(n,2*n,BIG),add(2*n,t,BIG);
	}
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	slv1();
	slv2();
}
int main(){
	init();
	return 0;
}

对于这一题，我们建三层的边来描述题目中的约束。
对于每道题建一个点，源点连一条容量为1的边到每一个点，表示每道题最多只能被选取一次。
对于每个种类建一个点，每一个点连一条容量为1的边到它所属的所有类，表示它仅可以被作为这个类来选取。
每个种类连一条容量为这个种类需要的选取次数的边到汇点，表示这个种类最多需要被选取的次数。
然后，跑一遍当前弧优化Dinic最大流，如果需要选取的总题数都能选取到，流量就等于需要选取的总题数。
当然也可以大力拆点跑二分图匹配，不过那样似乎更难写的样子。

#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[2005],et=-1;
int dep[2005],nw[2005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0); 
}

int n,m,s,t,Sans=0,tot; 

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
} 
//V表示从源点到当前路径上的剩余流量，cnt表示这个点向后流了多少流量。 
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				V-=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

void init(){
	scanf("%d%d",&m,&n);
	s=m+n+1,t=m+n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
//	注意初始化。 
	int p,x;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		Sans+=x;
		add(n+i,t,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p);
		add(s,i,1);
		for(int j=1;j<=p;++j){
			scanf("%d",&x);
			add(i,n+x,1);
//			注意哈希。 
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
		printf("%d\n",ans); 
	}
	if(ans<Sans){
		puts("No solution!");
		return;
	}
	for(int i=1;i<=m;++i){
		printf("%d: ",i);
		for(int j=h[n+i];j;j=e[j].nxt){
			if((j&1)&&(e[j].w==1)&&(e[j].v!=t)){
				printf("%d ",e[j].v);
			}
		}
		puts("");
	}
}

int main(){
	init();
	return 0;
}