[luogu P2756 ] 飞行员配对方案问题 (最大流)

强行做裸题做了两个小时。。我果然太水了QAQ

题目背景

第二次世界大战时期..

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入输出格式

输入格式：

第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。

接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。

输出格式：

第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入输出样例

输入样例#1：

5 10

1 7

1 8

2 6

2 9

2 10

3 7

3 8

4 7

4 8

5 10

-1 -1

输出样例#1：

4

1 7

2 9

3 8

5 10

code:

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int rd() {

    int x=0,fla=1; char c=' ';

    while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();}

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();

    return x*fla;

}

const int MAX=1010;

const int INF=0x3f3f3f3f;

int n,m,a,b,s,t,maxflow,cnt=1;

int gap[MAX<<1],d[MAX<<1],head[MAX],cur[MAX],S[MAX];

struct edges{

    int next,from,to,cap,flow;

}edge[MAX<<1];

void add(int a,int b,int c) {

    edge[++cnt]=(edges) {head[a],a,b,c,0};

//  cout<<cnt<<" : "<<edge[cnt].from<<" "<<edge[cnt].to<<" "<<edge[cnt].cap<<endl;

    head[a]=cnt;

}

void bfs() {

    memset(d,-1,sizeof d);

    memset(gap,0,sizeof gap);

    gap[0]=1;d[t]=0;

    queue <int> q;

    q.push(t);

    while(!q.empty()) {

        int u=q.front(); q.pop();

        for(int i=head[u];i;i=edge[i].next) {

            int v=edge[i].to;

            if(d[v]==-1) {

                d[v]=d[u]+1;

                gap[d[v]]++;

                q.push(v);

            }

        }

    }

}

void ISAP() {

    bfs();

    memcpy(cur,head,sizeof head);

    int u=s,top=0;

    while(d[s]<n) {

        if(u==t) {

            int Min=INF,inser;

            for(int i=0;i<top;i++) {

                if(Min>edge[S[i]].cap-edge[S[i]].flow) {

                    Min=edge[S[i]].cap-edge[S[i]].flow;

                    inser=i;

                }

            }

            for(int i=0;i<top;i++) {

                edge[S[i]].flow+=Min;

                edge[S[i]^1].flow-=Min;

            }

            maxflow+=Min;

            top=inser;

            u=edge[S[top]^1].to;

            continue;

        }

        bool ok=false;

        int v;

        for(int i=cur[u];i;i=edge[i].next) {

            v=edge[i].to;

            if(edge[i].cap-edge[i].flow && d[v]+1==d[u]) {

                ok=true;

                cur[u]=i;

                break;

            }

        }

        if(ok) {

            S[top++]=cur[u];

            u=v;

            continue;

        }

        int Min=n-1;

        for(int i=head[u];i;i=edge[i].next) {

            if(edge[i].cap-edge[i].flow && d[edge[i].to]<Min) {

                Min=d[edge[i].to];

                cur[u]=i;

            }

        }

        gap[d[u]]--;

        if(!gap[d[u]]) return ;

        d[u]=Min+1;

        gap[d[u]]++;

        if(u!=s) u=edge[S[--top]^1].to;

    }

    return ;

}

int main() {

    m=rd(),n=rd();

    s=n+1,t=n+2;

    for(int i=1;i<=m;i++) add(s,i,1),add(i,s,0);

    for(int i=m+1;i<=n;i++) add(i,t,1),add(t,i,0);

    a=rd(),b=rd();

    while(a!=-1 && b!=-1) {

        add(a,b,1);

        add(b,a,0);

        a=rd(),b=rd();

    }

    ISAP();

    printf("%d\n",maxflow);

    for(int i=2+n*2;i<=cnt;i+=2) {

//      cout<<i<<" : "<<edge[i].from<<" "<<edge[i].to<<" "<<edge[i].cap<<" "<<edge[i].flow<<endl;

        if(edge[i].flow==edge[i].cap)

            printf("%d %d\n",edge[i].from,edge[i].to);

    }

    return 0;

}

巴特西

[luogu P2756 ] 飞行员配对方案问题 (最大流)

最新文章

热门文章