为啥会RE?o(╥﹏╥)o
  • 板块学术版
  • 楼主无敌大蒟蒻
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/3/12 17:32
  • 上次更新2023/11/5 02:10:22
查看原帖
为啥会RE?o(╥﹏╥)o
87753
无敌大蒟蒻楼主2021/3/12 17:32

为啥会RE?

求助

P5154 数列游戏

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int S,T,N,head[1000001],dep[1000001];
struct node{
	int FROM,to,edge,next;
}a[1000001];
int add(int U,int V,int LONG1){
	a[N].FROM=U;
	a[N].to=V;
	a[N].edge=LONG1;
	a[N].next=head[U];
	head[U]=N++;
}
int Min(int AAA,int BBB){
	if(AAA>BBB) return BBB;
	return AAA;
}
int bfs(){
	queue<int> q;
	memset(dep,-1,sizeof(dep));
	dep[S]=0;
	q.push(S);
	while(!q.empty()){
		int From=q.front();
		q.pop();
		for(int i=head[From];i!=-1;i=a[i].next){
			int To=a[i].to;
			if(dep[To]==-1&&a[i].edge>0){
				dep[To]=dep[From]+1;
				if(To==T) return 1;
				q.push(To);
			}
		}
	}
	return 0;
}
int dfs(int u,int cs){
	if(u==T) return cs;
	int flow1=0;
	for(int i=head[u];i!=-1;i=a[i].next){
		int To=a[i].to;
		if(dep[To]!=dep[u]+1) continue;
		if(!a[i].edge) continue;
		int num=dfs(To,Min(cs-flow1,a[i].edge));
		a[i].edge-=num;
		a[i^1].edge+=num;
		flow1+=num;
		if(flow1==cs) return flow1;
	}
	return flow1;
}
int dinic(){
	int ans=0;
	while(bfs()) ans+=dfs(S,INF);
	return ans; 
}
int main(){
	//freopen("P2756_1.in","r",stdin);
//	freopen("P2756_1.out","w",stdout);
	int n,m;
	memset(head,-1,sizeof(head));
	scanf("%d%d",&m,&n);
	S=0,T=n+1;
	int U,V;
	while(scanf("%d%d",&U,&V)){
		if(U==-1&&V==-1) break;
		add(U,V,1);
		add(V,U,0);
	}
	for(int i=1;i<=m;i++){
		add(S,i,1);
		add(i,S,0);
	}
	for(int i=m+1;i<=n;i++){
		add(i,T,1);
		add(T,i,0);
	}
	int total=dinic();
	if(total==0){
		printf("0\n");
		return 0;
	}
	printf("%d\n",total);
	for(int i=0;i<=N-1;i++){
		if(a[i].FROM>m||a[i].FROM<1) continue;
		if(a[i].to>n||a[i].to<=m) continue;
		if(a[i].edge!=0) continue;
		printf("%d %d\n",a[i].FROM,a[i].to);
	}
	return 0;
}
2021/3/12 17:32
加载中...