社区讨论
萌新初学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 条回复,欢迎继续交流。
正在加载回复...