社区讨论

萌新初学OI!还女装了!

P2756飞行员配对方案问题参与者 12已保存回复 26

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
26 条
当前快照
1 份
快照标识符
@mi7pnpnn
此快照首次捕获于
2025/11/21 01:34
4 个月前
此快照最后确认于
2025/11/21 01:56
4 个月前
查看原帖
标题就是骗你们进来的qwq 巨巨们能不能看一下我的代码错哪里了QAQ(我知道没有写记录哪一对被匹配了,只是网络流部分就有错我把输出配对方案的部分先删了)
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100005;
struct Edge{
	int to,val,next;
}e[maxn*2];
queue<int>q;
int n,m,cnt=-1,head[maxn],dist[maxn],cur[maxn],maxflow=0;
void add(int x,int y,int z){
	e[++cnt].next=head[x];
	e[cnt].to=y;
	e[cnt].val=z;
	head[x]=cnt;
}
int bfs(int s,int t){
	memset(dist,-1,sizeof(dist));
	while(!q.empty())q.pop();
	for(int i=1;i<=n;i++)cur[i]=head[i];
	dist[s]=0;q.push(s);
	while(!q.empty()){
		int h=q.front();
		q.pop();
		for(int i=head[h];i!=-1;i=e[i].next){
			if(dist[e[i].to]==-1&&e[i].val){
				dist[e[i].to]=dist[h]+1;
				q.push(e[i].to);
			}
		}
	}
	if(dist[t]!=-1)return true;
	else return false;
}
int dfs(int now,int t,int limit){
	if(!limit||now==t)return limit;
	int flow=0,f;
	for(int i=cur[now];i!=-1;i=e[i].next){
		cur[now]=i;
		if(dist[e[i].to]==dist[now]+1&&(f=dfs(e[i].to,t,min(limit,e[i].val)))){
			flow+=f;limit-=f;
			e[i].val-=f;
			e[i^1].val+=f;
			if(!limit)break;
		}
	}
	return flow;
}
void Dinic(int s,int t){
	while(bfs(s,t))
	  maxflow+=dfs(s,t,1e9);
}
int main()
{
	int x,y;
	cin>>m>>n;
	memset(head,-1,sizeof(head));
	while(1){
		scanf("%d%d",&x,&y);
		if(x==-1&&y==-1)break;
		add(x,y,1);
		add(y,x,0);
	}
	for(int i=1;i<=m;i++)
	  add(0,i,1),add(i,0,0);
	for(int i=m+1;i<=n;i++)
	  add(i,n+1,1),add(n+1,i,0);
	Dinic(0,n+1);
	cout<<maxflow;
	return 0;
}

回复

26 条回复,欢迎继续交流。

正在加载回复...