填志愿 --最大流---二分匹配

做了专门的最大流问题，刚开始用了最大流上网看了说二分匹配法更好，那就学习了二分匹配法。

最大流解法：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <queue>
 4 #include <cstring>
 5 using namespace std;
 6 const int N=405;
 7 const int maxData=10;
 8 int map[N][N];//记录残留网络的容量
 9 int flow[N];//记录源点到当前节点实际多少流量
10 int pre[N];//记录这条路径当前节点的前驱，同时标记该节点是否在队列中；
11 queue<int> q;
12 int n,m;
13 
14 int bfs(int src,int des) //找增广路径
15 {
16     int i,j;
17     while(!q.empty())
18         q.pop();
19     for(i=0;i<=m+n+1;i++)
20         
21         pre[i]=-1;
22     pre[src]=-2;
23     flow[src]=maxData;
24     q.push(src);
25     while(!q.empty())
26     {
27         int index=q.front();
28         q.pop();
29         if(index==des)
30             break;
31         for(int i=0;i<=m+n+1;i++)
32             if(i!=src&&map[index][i]>0&&pre[i]==-1)
33             {
34                 pre[i]=index;
35                 flow[i]=min(map[index][i],flow[index]);
36                 q.push(i);
37             }
38     }
39     if(pre[des]==-1)
40         return -1;
41     else
42         return flow[des];
43 }
44 int maxFlow(int src ,int des) 
45 {
46     int increasement=0;
47     int sumflow=0;
48     while((increasement=bfs(src,des))!=-1)
49     {
50         int k=des;//利用前驱寻找路径
51         while(k!=src)
52         {
53             int last=pre[k];
54             map[last][k]-=increasement;
55             map[k][last]+=increasement;
56             k=last;
57         }
58         sumflow+=increasement;
59     }
60     return sumflow;
61 }
62 
63 int main()
64 {
65     int i,j;
66     scanf("%d%d",&n,&m);
67     memset(map,0,sizeof(map));
68     memset(flow,0,sizeof(flow));
69     for(int i=1;i<=n;i++)
70     {
71         int x;
72         scanf("%d",&x);
73         while(x--)
74         {
75             scanf("%d",&j);
76             map[i][j+n]=1;
77         }
78     }
79     for(int i=1;i<=n;i++)
80         map[0][i]=1;
81     for(int i=n+1;i<=n+m;i++)
82         map[i][n+m+1]=1;
83     /*for(int i=0;i<=m+n+1;i++)
84     {
85         for(int j=0;j<=m+n+1;j++)
86             printf("%d ",map[i][j]);
87         printf("
");
88     }
89     */
90     printf("%d
",maxFlow(0,m+n+1));
91     return 0;
92 }
93 
94     
95     
96     
97     
98     
99

二分图求解：

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int MAXN=1000;
 5 int uN,vN;  //u,v数目
 6 int g[MAXN][MAXN];//编号是0~n-1的
 7 int linker[MAXN];//表示b集合中的i匹配到a集合的元素 a集合代表毕业生b集合高校
 8 bool used[MAXN];//b集合被访问
 9 bool dfs(int u) //给第u个学生分配高校
10 {
11     int v;
12     for(v=1;v<=vN;v++)
13         if(g[u][v]&&!used[v])
14         {
15             used[v]=true;
16             if(linker[v]==-1||dfs(linker[v]))
17             {
18                 linker[v]=u;
19                 return true;
20             }
21         }
22     return false;
23 }
24 int hungary()
25 {
26     int res=0;
27     int u;
28     memset(linker,-1,sizeof(linker));
29     for(u=1;u<=uN;u++)
30     {
31         memset(used,0,sizeof(used));
32         if(dfs(u))  res++;
33     }
34     return res;
35 }
36 int main(){
37 
38 int n,m;
39 while(cin>>n>>m)
40 {uN=n;vN=m;
41 int x,y;
42     for(int i=1;i<=n;i++)
43     {
44         cin>>x;
45         while(x--)
46         {
47             cin>>y;
48             g[i][y]=1;
49         }
50     }
51 
52    cout<<hungary()<<endl;
53 
54 }
55 
56 return 0;
57 
58 }