求出,第五个点RE
查看原帖
求出,第五个点RE
296595
Matutino_Lux楼主2022/2/1 11:51

rt

第五个点下下来本地过了,在IDE上也过了

但是luogup 评测RE

#include<bits/stdc++.h>
#define reg register
#define Mod(x) (((x)+mod)%mod)
#define IN freopen(".in.txt","r",stdin)
#define OUT freopen(".out.txt","w",stdout)
#define int long long
using namespace std;
const int N=1e4+10,INF=1e18;
int n,m,s,t,cnt=1,head[N];
int nxt[N],tag[N];
queue<int> q;
int dep[N],cur[N],gap[N],check[N];
struct EDGE{
	int pre,from,to,val;
}edge[N<<1];
inline int read(){
	int k=1,x=0;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
	return k*x;
}
inline void add(reg int u,reg int v,reg int w){edge[++cnt]=(EDGE){head[u],u,v,w},head[u]=cnt;} 
inline bool bfs(){ 
	memset(dep,0,sizeof(dep));
	dep[s]=1,q.push(s);
	for (reg int i=1;i<=n;i++) cur[i]=head[i];
	while (!q.empty()){
		reg int u=q.front(); q.pop();
		for (reg int i=head[u];i;i=edge[i].pre){
			int v=edge[i].to;
			if (edge[i].val&&!dep[v]) dep[v]=dep[u]+1,q.push(v); 
		}
	} 
	return dep[t]; 
}
inline int dfs(int u,int flow){
	if (u==t) return flow;
	int dout=0;
	for (reg int i=cur[u];i&&flow;i=edge[i].pre){
		reg int v=edge[i].to;
		cur[u]=i;
		if (edge[i].val&&dep[v]==dep[u]+1){
			reg int res=dfs(v,min(flow,edge[i].val));
			if (res){
				nxt[u]=v;
                if (u!=s) tag[v-n]=1;
				edge[i].val-=res,edge[i^1].val+=res;  
				flow-=res,dout+=res; 				
			}
			if (!flow) break;
		}
	}
	if (!dout) dep[u]=0; 
	return dout; 
}
int sum;
signed main(){
	n=read(),m=read(),s=n+n+1,t=n+n+2;
	for (reg int i=1;i<=n;i++) add(s,i,1),add(i,s,0),add(i+n,t,1),add(t,i+n,0);
	for (reg int i=1,u,v;i<=m;i++) u=read(),v=read()+n,add(u,v,1),add(v,u,0); 
	memset(check,1,sizeof(check)); 
 	reg int ans=0;
	while (bfs()) memcpy(cur,head,sizeof(head)),ans+=dfs(s,1e18);
//	cout<<1;
//	memset(tag,1,sizeof(tag));
	for (reg int i=1,u;i<=n;i++)
	    if (!tag[i]){
	    	printf("%lld",i),u=i;
            while (nxt[u]!=s&&nxt[u]!=t&&nxt[u]-n>0) printf(" %lld",u=nxt[u]-n);
            puts("");
		}
	printf("%lld",n-ans); 
	return 0;
}
 
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.......RRRRRRRRRRRRRRRRRRRR...................PPPPPPPPPPPPPPPPPPPP...............................................
//.......RRRRRRRRRRRRRRRRRRRRRR.................PPPPPPPPPPPPPPPPPPPPPP.............................................
//.......RRRRRRRRRRRRRRRRRRRRRRR................PPPPPPPPPPPPPPPPPPPPPPPP...........................................
//.......RRRR.................RRRRR.............PPPP...............PPPPP...........................................
//.......RRRR.................RRRRR.............PPPP................PPPPP..........................................
//.......RRRR.................RRRRR.............PPPP................PPPPP..........................................
//.......RRRR...............RRRRR...............PPPP...............PPPPP...........................................
//.......RRRR............RRRRRR.................PPPP.............PPPPPP............................................
//.......RRRR............RRRRRR.................PPPP............PPPPPP.............................................
//.......RRRR........RRRRRR.....................PPPP........PPPPPP.................................................
//.......RRRRRRRRRRRRRRRRRR.....................PPPPPPPPPPPPPPPPPP.................................................
//.......RRRRRRRRRRRRRRRRRR.....................PPPPPPPPPPPPPPPP...................................................
//.......RRRR..........RRRR.....................PPPPP.................................+++................+++.......
//.......RRRR...........RRRR....................PPPPP.................................+++................+++.......
//.......RRRR.............RRRR..................PPPPP.................................+++................+++.......
//.......RRRR..............RRRR.................PPPPP...........................+++++++++++++++....+++++++++++++++.
//.......RRRR...............RRRR................PPPPP...........................+++++++++++++++....+++++++++++++++.
//.......RRRR................RRRR...............PPPPP.................................+++................+++.......
//.......RRRR.................RRRR..............PPPPP.................................+++................+++.......
//.......RRRR...................RRRR............PPPPP.................................+++................+++.......
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
2022/2/1 11:51
加载中...