从前一个和谐的班级，有 nlnl 个是男生，有 nrnr 个是女生。编号分别为 1,…,nl1,…,nl 和 1,…,nr1,…,nr。
有若干个这样的条件：第 vv 个男生和第 uu 个女生愿意结为配偶。
请问这个班级里最多产生多少对配偶？
输入格式
第一行三个正整数，nl,nr,mnl,nr,m。
接下来 mm 行，每行两个整数 v,uv,u 表示第 vv 个男生和第 uu 个女生愿意结为配偶。保证 1≤v≤nl1≤v≤nl，1≤u≤nr1≤u≤nr，保证同一个条件不会出现两次。
输出格式
第一行一个整数，表示最多产生多少对配偶。
接下来一行 nlnl 个整数，描述一组最优方案。第 vv 个整数表示 vv 号男生的配偶的编号。如果 vv 号男生没配偶请输出 00。
样例一
input
2 2 3 1 1 1 2 2 1
output
2 2 1
explanation
11 号男生跟 22 号女生幸福地生活在了一起～
22 号男生跟 11 号女生幸福地生活在了一起～
样例二
input
2 2 2 1 1 2 1
output
1 1 0
explanation
班上一个女神一个女汉子，两个男生都去追女神。一种最优方案是：
11 号男生跟 11 号女生幸福地生活在了一起～
22 号男生孤独终生。= =||
正解：二分图最大匹配
解题报告：
二分图最大匹配裸题。
然而我才发现我的模板是一个萎的。。。这是第几个萎的模板了。
if(vis[x]) return false;只需一行，结束战斗。。。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 #ifdef WIN32 14 #define OT "%I64d" 15 #else 16 #define OT "%lld" 17 #endif 18 using namespace std; 19 typedef long long LL; 20 const int MAXN = 1011; 21 const int MAXM = 500011; 22 int nl,nr,m,ecnt; 23 int first[MAXN],next[MAXM],to[MAXM]; 24 int ans,match[MAXN]; 25 bool vis[MAXN]; 26 27 inline int getint() 28 { 29 int w=0,q=0; 30 char c=getchar(); 31 while((c<'0' || c>'9') && c!='-') c=getchar(); 32 if (c=='-') q=1, c=getchar(); 33 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); 34 return q ? -w : w; 35 } 36 37 inline bool dfs(int x){ 38 vis[x]=1; 39 for(int i=first[x];i;i=next[i]) { 40 int v=to[i]; if(vis[v]) continue; 41 if(!match[v] || dfs(match[v])) { 42 match[x]=v; match[v]=x; 43 return true; 44 } 45 } 46 return false; 47 } 48 49 inline void work(){ 50 nl=getint(); nr=getint(); m=getint(); 51 int x,y; 52 for(int i=1;i<=m;i++) { 53 x=getint(); y=getint()+nl; 54 next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; 55 next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x; 56 } 57 for(int i=1;i<=nl;i++) { 58 memset(vis,0,sizeof(vis)); 59 if(dfs(i)) ans++; 60 } 61 printf("%d ",ans); 62 for(int i=1;i<=nl;i++) if(match[i]) printf("%d ",match[i]-nl); else printf("0 "); 63 } 64 65 int main() 66 { 67 work(); 68 return 0; 69 }