90pts求条
查看原帖
90pts求条
704651
Yanran_10086楼主2024/9/18 17:20
#include<bits/stdc++.h>
using namespace std;
const int N=480,M=(150*270)+N*2,INF=1e8;
int m,n,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N];
void add(int a,int b,int c){
	e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
	e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
	int head=0,tai=0;
	memset(d,-1,sizeof d);
	q[0]=S;
	d[S]=0;
	cur[S]=h[S];
	while(head<=tai){
		int t=q[head++];
		for(int i=h[t];~i;i=ne[i]){
			int ver=e[i];
			if(d[ver]==-1 && f[i]){
				d[ver]=d[t]+1;
				cur[ver]=h[ver];
				if(ver==T){
					return 1;
				}
				q[++tai]=ver;
			}
		}
	}
	return 0;
}
int find(int u,int limit){
	if(u==T){
		return limit;
	}
	int flow=0;
	for(int i=h[u];~i && flow<limit;i=ne[i]){
		cur[u]=i;
		int ver=e[i];
		if(d[ver]==d[u]+1&&f[i]){
			int t=find(ver,min(f[i],limit-flow));
			if(!t){
				d[ver]=-1;
			}
			f[i]-=t;
			f[i^1]+=t;
			flow+=t;
		}
	}
	return flow;
}
int dinic(){
	int r=0,flow=0;
	while(bfs()){
		while(flow=find(S,INF)){
			r+=flow;
		}
	}
	return r;
}
int main(){
	cin>>m>>n;
	S=0;
	T=n+m+1;
	int tot=0;
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++){
		int c;
		cin>>c;
		add(S,i,c);
		tot+=c;
	}
	for(int i=1;i<=n;i++){
		int c;
		cin>>c;
		add(i+m,T,c);
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			add(i,m+j,1);
		}
	}
	if(dinic()!=tot){
		cout<<0<<endl;
	}
	else{
		cout<<1<<endl;
		for(int i=1;i<=m;i++){
			for(int j=h[i];~j;j=ne[j]){
				if(e[j]>m&&e[j]<=m+n&&!f[j]){
					cout<<e[j]-m<<" ";
				}
			}
			cout<<endl;
		}
	}
}
2024/9/18 17:20
加载中...