调麻了,本机AC提交全部RE找不出来
查看原帖
调麻了,本机AC提交全部RE找不出来
881015
Resstifnurvˆwˆ.tar.gz楼主2023/12/2 13:14

甚至给数组开大了100倍,也无济于事,我本机能跑也找不出问题所在

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

inline int read(){
	int ret=0;
	char ch=' ',c=getchar();
	while(!('0'<=c&c<='9')) ch=c,c=getchar();
	while('0'<=c&&c<='9') ret=(ret<<1)+(ret<<3)+(c^48),c=getchar();
	return ch=='-'?-ret:ret;
}

int n,m;
int S,T;
const int N=1e4+10,M=1e6+10;

int to[M],nt[M],c[M],idx,h[N],cur[N];
inline int add(int x,int y,int z){
	to[idx]=y,nt[idx]=h[x],c[idx]=z,h[x]=idx++;
	to[idx]=x,nt[idx]=h[y],c[idx]=0,h[y]=idx++;
}

int lv[N];
int q[N],tt=-1,hh=0;

bool bfs(){
	memset(lv,-1,sizeof(lv));
	tt=-1,hh=0;
	q[++tt]=S;
	lv[S]=0;
	cur[S]=h[S];
	while(hh<=tt){
		int u=q[hh++];
		for(int i=h[u];i!=-1;i=nt[i]){
			int j=to[i];
			if(lv[j]!=-1||c[i]==0) continue;
			q[++tt]=j;
			lv[j]=lv[u]+1;
			cur[j]=h[j];
			if(j==T) return true;
		}
	}
	return false;
}

int find(int u,int limit){
	if(u==T) return limit;
	int flow=0;
	for(int i=cur[u];i!=-1&&flow<limit;i=nt[i]){
		int j=to[i];
		cur[u]=i;
		if(lv[j]!=lv[u]+1||c[i]==0) continue;
		int k=find(j,min(c[i],limit-flow));
		if(k==0) lv[j]=-1;
		flow+=k;
		c[i]-=k;
		c[i^1]+=k;
	}
	return flow;
}

int dinic(){
	int ans=0,flow=0;
	while(bfs()){
		while(flow=find(S,0x3f3f3f3f)) ans+=flow;
	}
	return ans;
}

int main(){
	memset(h,-1,sizeof(h));
	m=read(),n=read();
	int x,y,z;
	while(true){
		x=read(),y=read();
		if(x==-1) break;
		add(x,y,1);
	}
	S=0,T=n+1;
	for(int i=1;i<=m;i++) add(S,i,1);
	for(int i=m+1;i<=n;i++) add(i,T,1);
	printf("%d\n",dinic());
	for(int u=1;u<=m;u++){
		for(int i=h[u];i!=-1;i=nt[i]){
			int j=to[i];
			if(m+1<=j&&j<=n&&c[i]==0) printf("%d %d\n",u,j);
		}
	}
	return 0;
}
2023/12/2 13:14
加载中...