SPJ锅了
查看原帖
SPJ锅了
279095
gargantuar楼主2021/6/29 20:28

rt 输入

3 3
2 2 2
2 2 2

要求输出

1
1 2
1 3
2 3

我的输出

1
1 3
2 3
1 2

wa了 程序,如下

#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
int head[500],cur[500],lv[500],qqt[500],cont=1,start,end,ns,tt,n;
struct li {
	int to,next,w;
} e[85000];
void add(int s,int t,int w) {
	e[++cont].to=t;
	e[cont].w=w;
	e[cont].next=head[s];
	head[s]=cont;
	e[++cont].to=s;
	e[cont].w=0;
	e[cont].next=head[t];
	head[t]=cont;
	return;
}
bool bfs() {
	for(int i=1; i<=n; ++i)cur[i]=head[i],lv[i]=-1;
	lv[start]=0;
	queue<int>q;
	q.push(start);
	int th,ak,vk;
	while(!q.empty()) {
		th=q.front();
		q.pop();
		if(th==end)break;
		for(int i=head[th]; i; i=e[i].next) {
			ak=e[i].to,vk=e[i].w;
			if(lv[ak]==-1&&vk>0) {
				lv[ak]=lv[th]+1;
				q.push(ak);
			}
		}
	}
	return lv[end]!=-1;
}
int dfs(int a,int flow) {
	if(a==end)return flow;
	int ak,vk,c,rnm=flow;
	for(int i=cur[a]; i&&rnm; i=e[i].next) {
		cur[a]=i;
		ak=e[i].to,vk=e[i].w;
		if(vk>0&&lv[ak]==lv[a]+1) {
			c=dfs(ak,min(rnm,vk));
			rnm-=c;
			e[i].w-=c;
			e[i^1].w+=c;
		}
	}
	return flow-rnm;
}
int dinic() {
	int ans;
	while(bfs())ans+=dfs(start,11451419);
	return ans;
}
int main() {
	scanf("%d%d",&ns,&tt);
	n=ns+tt;
	start=n+1,end=n+2;
	int ls,lss,wkk=0;
	for(int i=1; i<=ns; i++) {
		scanf("%d",&ls);
		wkk+=ls;
		add(start,i,ls);
	}
	for(int i=1; i<=tt; i++) {
		scanf("%d",&ls);
		add(i+ns,end,ls);
	}
	for(int i=1; i<=ns; i++) {
		for(int j=1; j<=tt; j++)
			add(i,ns+j,1);
	}
	n=n+2;
//	for(int i=1; i<=ns; i++) {
//		for(int j=head[i]; j; j=e[j].next) {
//			if(e[j].w==1)printf("%d ",e[j].to-ns);
//		}
//		printf("\n");
//	}
	if(dinic()!=wkk) {
		printf("0");
		return 0;
	}
	printf("1\n");
	ls=0;
	for(int i=1; i<=ns; i++) {
		for(int j=head[i]; j; j=e[j].next) {
			if(e[j].to<=ns+tt&&e[j].w==0)qqt[++ls]=e[j].to-ns;
			//printf("%d ",e[j].to-ns);
		}
		sort(qqt+1,qqt+1+ls);
		for(int j=1; j<=ls; j++) {
			printf("%d ",qqt[j]);
		}
		ls=0;
		printf("\n");
	}
}
2021/6/29 20:28
加载中...