首页 > 其他 > 详细

网络流24题

时间:2020-04-24 00:00:38      阅读:75      评论:0      收藏:0      [点我收藏+]

网络流24题:

P2756 飞行员配对方案问题

简单二分图匹配,

技术分享图片
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e3+5;
int gp[N][N],match[N],vis[N];
int n,m;
bool findpath(int u){
    for(int i=m+1;i<=n+m;i++){
        if(gp[u][i]&&!vis[i]){
            vis[i]=1;
            if(!match[i]||findpath(match[i])){
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}   
void init(){
    memset(gp,0,sizeof gp);
    memset(match,0,sizeof match);
}
int main(){
    init();
    scanf("%d %d",&m,&n);
    int u,v;
    while(~scanf("%d %d",&u,&v)){
        if(u+v<0)break;
        gp[u][v]=1;
    }
    vector<int>ans;
    for(int i=1;i<=m;i++){
    
        memset(vis,0,sizeof vis);
        if(findpath(i))ans.pb(i);
    
    }
    for(int i=m+1;i<=n+m;i++){
        if(match[i])match[ match[i] ]=i;
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        printf("%d %d\n",ans[i],match[ ans[i] ]);
    }

    // system("pause");
    return 0;
}
View Code

 

网络流24题

原文:https://www.cnblogs.com/littlerita/p/12764681.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!