网络流24题 洛谷 2756 飞行员配对方案

 1 #include<bits/stdc++.h>
 2 
 3 const int N=1000+5;
 4 
 5 using namespace std;
 6 
 7 int link[N],g[N][N],ansx[N];
 8 int n,m,u,v,ans;
 9 bool vis[N];
10 
11 inline void read( int&x ) {
12     int f=1;x=0;char c=getchar();
13     while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}
14     while(c>=‘0‘&&c<=‘9‘) x=10*x+c-48,c=getchar();
15     x=x*f;
16 }
17 bool find(int x){
18     for(int i=1;i<=m;i++){
19         if(!vis[i] && g[x][i]){
20             vis[i]=true;
21             if((!link[i]) || find(link[i])){
22                 link[i]=x;
23                 ansx[i]=x;
24                 return true;
25             }
26         }
27     }
28     return false;
29 }
30 int main(){
31     read(m);read(n);
32     while(1){
33         read(u);read(v);
34         if(u==-1 && v==-1)
35             break;
36         g[v][u]=1;
37     }
38     for(int i=m+1;i<=n+m;i++){
39         memset(vis,false,sizeof(vis));
40         if(find(i))
41             ans++;
42     }
43     if(!ans){
44         printf("No solution!");
45         return 0;
46     }
47     printf("%d\n",ans);
48     for(int i=1;i<=m;i++)
49         if(link[i])
50             printf("%d %d\n",i,link[i]);
51     return 0;
52 }