https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/E
【题意】
裸的最大匹配
【教训】
一开始边数开了k,建的是无向图，结果T了，改成2*k就A了
其实如果add(u,v+n)可以用无向图（注意边数）也可以用有向图。
如果add(u,v)只能用有向图，只从左边找右边。
【Accepted】
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 using namespace std; 9 int k,n,m; 10 const int maxn=1e3+3; 11 const int maxm=1e3+3; 12 struct edge 13 { 14 int to; 15 int nxt; 16 }e[maxm]; 17 int tot; 18 int head[maxn]; 19 bool vis[maxn]; 20 int link[maxn]; 21 void init() 22 { 23 tot=0; 24 memset(head,-1,sizeof(head)); 25 memset(link,-1,sizeof(link)); 26 } 27 void add(int u,int v) 28 { 29 e[tot].to=v; 30 e[tot].nxt=head[u]; 31 head[u]=tot++; 32 } 33 34 bool find(int u) 35 { 36 for(int i=head[u];i!=-1;i=e[i].nxt) 37 { 38 int v=e[i].to; 39 //cout<<v<<endl; 40 if(!vis[v]) 41 { 42 vis[v]=true; 43 if(link[v]==-1||find(link[v])) 44 { 45 link[v]=u; 46 return true; 47 } 48 } 49 } 50 return false; 51 } 52 int main() 53 { 54 while(~scanf("%d",&k)) 55 { 56 if(k==0) 57 { 58 break; 59 } 60 init(); 61 scanf("%d%d",&n,&m); 62 while(k--) 63 { 64 int u,v; 65 scanf("%d%d",&u,&v); 66 add(u,n+v); 67 // add(n+v,u); 68 } 69 int ans=0; 70 for(int i=1;i<=n+m;i++) 71 { 72 memset(vis,false,sizeof(vis)); 73 if(find(i)) 74 { 75 ans++; 76 } 77 } 78 //cout<<ans/2<<endl; 79 cout<<ans<<endl; 80 } 81 return 0; 82 }