TLE求调
查看原帖
TLE求调
745332
Henry2012楼主2024/8/8 16:00
#include<bits/stdc++.h>
using namespace std;
const int N=507,M=41007,inf=2e9;
int dis[N],head[N],hd[N],tot,n,m,sum;
struct Edge{
	int to,nx,wt;
} eg[M<<1];
void addE(int u,int v,int w){
	eg[tot]={v,hd[u],w},hd[u]=tot++;
}
bool bfs(){
	memset(dis,-1,sizeof dis);
	queue<int> q;
	q.push(0),dis[0]=0;
	while (q.size()){
		int u=q.front();q.pop();
		for (int i=hd[u];i!=-1;i=eg[i].nx){
			int v=eg[i].to;
			if (dis[v]==-1 && eg[i].wt)
				dis[v]=dis[u]+1,q.push(v);
		}
	}
	return dis[n+m+1]!=-1;
}
int dfs(int u,int flow){
	if (!flow || u==n+m+1) return flow;
	for (int i=head[u];i!=-1;i=eg[i].nx){
		int v=eg[i].to,w=eg[i].wt;
		if (!w || dis[v]!=dis[u]+1) continue;
		int t=dfs(v,min(w,flow));
		if (t){
			eg[i].wt-=t,eg[i^1].wt+=t;
			return t;
		}
	}
	return 0;
}
int dinic(){
	int ans=0;
	while (bfs()){
		for (int i=0;i<=n+m+1;++i) head[i]=hd[i];
		int t=dfs(0,inf);
		if (!t) break;
		ans+=t;
	}
	return ans;
}
signed main(){
	memset(hd,-1,sizeof hd);
	scanf("%d%d",&n,&m);
	for (int i=1,x;i<=n;++i){
		scanf("%d",&x),sum+=x;
		addE(0,i,x),addE(i,0,0);
	}
	for (int i=1,x;i<=m;++i){
		scanf("%d",&x);
		addE(n+i,n+m+1,x),addE(n+m+1,n+i,0);
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			addE(i,n+j,1),addE(n+j,i,0);
	if (dinic()!=sum){
		puts("0");
		return 0;
	}
	puts("1");
	for (int i=1;i<=n;++i){
		for (int j=hd[i];j!=-1;j=eg[j].nx)
			if (eg[j].to>n && !eg[j].wt) printf("%d ",eg[j].to-n);
		puts("");
	}
	return 0;
}
2024/8/8 16:00
加载中...