Cogs 14. [网络流24题] 搭配飞行员

这道题其实蛮好想的，因为分为正，副飞行员。所以就把正飞行员当作Boy，副飞行员当作Girl。然后做Hungry即可。

 #include<bits/stdc++.h>

 using namespace std;

 int G[][],vis[],girl[],n,n1;

 int hungry(int boy)

 {

     int i;

     for(i=n1+;i<=n;i++)

     {

         if(G[boy][i]==&&vis[i]==)

         {

             vis[i]=;

             if(hungry(girl[i])==||girl[i]==)

             {

                 girl[i]=boy;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     int a,b,sum,i;

     scanf("%d %d",&n,&n1);

     while(scanf("%d %d",&a,&b)!=EOF)G[a][b]=;

     memset(girl,,sizeof(girl));

     sum=;

     for(i=;i<=n1;i++)

     {

         memset(vis,,sizeof(vis));

         if(hungry(i)==)sum++;

     }

     printf("%d",sum);

     return ;

 }

但这道题是“网络流24题”，所以还是要练一练网络流。所以直接用Dinic做最大流即可。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 int n,s,t,q[],dis[],G[][];

 int Min(int aaa,int bbb){if(aaa>bbb)return bbb;else return aaa;}

 int Bfs()

 {

     int head,tail,u,v;

     memset(q,,sizeof(q)),head=,tail=,q[tail]=s;

     memset(dis,-,sizeof(dis)),dis[s]=;

     while(head<=tail)

     {

         u=q[++head];

         for(v=;v<=n;v++)

         {

             if(G[u][v]>&&dis[v]<)

             {

                 dis[v]=dis[u]+;

                 q[++tail]=v;

             }

         }

     }

     if(dis[n]<=)return ;

     else return ;

 }

 int Dfs(int u,int minflow)

 {

     int v,ans;

     if(u==n)return minflow;

     for(v=;v<=n;v++)

     {

         if(G[u][v]>&&dis[v]==dis[u]+)

         {

             ans=Dfs(v,Min(minflow,G[u][v]));

             if(ans!=)

             {

                 G[u][v]-=ans;

                 G[v][u]+=ans;

                 return ans;

             }

         }

     }

     return ;

 }

 int Dinic()

 {

     int maxflow=,ans;

     while(Bfs()!=)

     {

         ans=Dfs(s,0x7fffffff);if(ans==)break;maxflow+=ans;

     }

     return maxflow;

 }

 int main()

 {

     int n1,a,b,i;

     scanf("%d %d",&n,&n1);

     while(scanf("%d %d",&a,&b)!=EOF)G[a][b]=;

     n+=;s=n-;t=n;

     for(i=;i<=n1;i++)G[s][i]=;

     for(i=n1+;i<=n-;i++)G[i][t]=;

     printf("%d",Dinic());

     return ;

 }