91分,没过样例和#1,求调
  • 板块P3254 圆桌问题
  • 楼主Tiagim
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/7/8 10:27
  • 上次更新2023/11/3 11:05:45
查看原帖
91分,没过样例和#1,求调
237963
Tiagim楼主2023/7/8 10:27

rt

#include<bits/stdc++.h>
#define ri register int
using namespace std;
int m,n,s=421,t=422,ans;
int hd[425],nxt[81845],w[81845],to[81845],tot=1;
int dep[425],cnt[425],nw[425];
void build(int u,int v,int ww){
	nxt[++tot]=hd[u];
	to[tot]=v;
	w[tot]=ww;
	hd[u]=tot;
	nxt[++tot]=hd[v];
	to[tot]=u;
	hd[v]=tot;
}
void bfs(){
	queue<int> q;
	q.push(t);
	++cnt[dep[t]=1];
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(ri i(hd[x]);i;i=nxt[i]){
			int ed=to[i];
			if(!dep[ed]&&!w[i]){
				dep[ed]=dep[x]+1;
				++cnt[dep[ed]];
				q.push(ed);
			}
		}
	}
}
int dfs(int x,int val){
	if(x==t)return val;
	int sum=0;
	for(ri i(nw[x]);i;i=nxt[i]){
		nw[x]=i;
		int ed=to[i];
		if(dep[x]==dep[ed]+1&&w[i]){
			int cst=dfs(ed,min(w[i],val-sum));
			w[i]-=cst;
			w[i^1]+=cst;
			sum+=cst;
			if(sum==val)return val;
		}
	}
	if(!--cnt[dep[x]])dep[s]=n+1;
	++cnt[++dep[x]];
	return sum;
}
int main(){
	scanf("%d%d",&m,&n);
	int ww;
	for(ri i(1);i<=m;++i)scanf("%d",&ww),build(s,i,ww),ans+=ww;
	for(ri i(1);i<=n;++i)scanf("%d",&ww),build(m+i,t,ww);
	for(ri i(1);i<=m;++i)
		for(ri j(1);j<=n;++j)
			build(i,j+m,1);
	bfs();
	while(dep[s]<=n){
		memcpy(nw,hd,sizeof(hd));
		ans-=dfs(s,2e9);
	}
	if(!ans){
		printf("1\n");
		for(ri i(1);i<=m;++i){
			for(ri j(hd[i]);j;j=nxt[j]){
				int ed=to[j];
				if(ed!=s&&!w[j])printf("%d ",ed-m);
			}
			printf("\n");
		}
	}
	else printf("0");
	return 0;
}
2023/7/8 10:27
加载中...