本文共 1457 字，大约阅读时间需要 4 分钟。
第一眼就想到二分图匹配
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)14 #define re(i,l,r) for(int i=(l);i<=(r);i++)15 #define Clear(a,b) memset(a,b,sizeof(a))16 #define inout(x) printf("%d",(x))17 #define douin(x) scanf("%lf",&x)18 #define strin(x) scanf("%s",(x))19 #define LLin(x) scanf("%lld",&x)20 #define op operator21 #define CSC main22 typedef unsigned long long ULL;23 typedef const int cint;24 typedef long long LL;25 using namespace std;26 void inin(int &ret)27 {28 ret=0;int f=0;char ch=getchar();29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();}30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();31 ret=f?-ret:ret;32 }33 int head[1000010],next[2000020],zhi[2000020],ed,n,pre[1000010],bo[1000010];34 bool find(int x,int T)35 {36 for(int i=head[x];i;i=next[i])37 if(bo[zhi[i]]!=T)38 {39 bo[zhi[i]]=T;40 if(!pre[zhi[i]]||find(pre[zhi[i]],T))41 {42 pre[zhi[i]]=x;43 return 1;44 }45 }46 return 0;47 }48 void add(int a,int b){next[++ed]=head[a],head[a]=ed,zhi[ed]=b;}49 int CSC()50 {51 inin(n);52 re(i,1,n)53 {54 int x;inin(x),add(x,i);55 inin(x),add(x,i);56 }57 re(i,1,n+1)if(!find(i,i))58 {59 printf("%d",i-1);60 return 0;61 }62 cout<
转载于:https://www.cnblogs.com/HugeGun/p/5197191.html