二分图匹配, 将需要进行的编号 (1-10000) 和物件进行匹配, 而非编号之间, 编号对应物品
- #include<bits/stdc++.h>
- using namespace std;
- const int N=10005;
- const int M=1000005;
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
- while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x*f;}
- int n,tot,ans,vis[N],head[N],link[M];
- struct node{int v,next;}e[M<<1];
- void insert(int u,int v){
- e[++tot]=(node){v,head[u]};head[u]=tot;}
- int match(int u){
- if(vis[u]) return 0;
- vis[u]=1;
- for(int i=head[u];i;i=e[i].next){
- int v=e[i].v;
- if(!link[v]||match(link[v])){
- link[v]=u;return 1;}
- }return 0;
- }
- /*
- int match(int u){
- if(vis[u]) return 0;
- vis[u]=1;
- for(int i=head[u];i;i=e[i].next){
- int v=e[i].v;
- if(vis[v]) continue;
- vis[v]=1;
- if(!link[v]||match(link[v])){
- link[v]=u;return 1;}
- }return 0;
- }
- 上述写法会漏掉在 match(link[v])中对 link[v]的 vis 判断
- */
- // 将编号和属性相连接进行二分图匹配
- // 寻找每个属性由 1-10000(x,y) 匹配到的物件编号(i)
- int main(){
- n=read();
- for(int x,y,i=1;i<=n;i++){
- x=read(),y=read();
- insert(x,i),insert(y,i);}
- for(int i=1;i<=10000;i++){
- memset(vis,0,sizeof vis);
- if(match(i)) ans++;
- else break;}
- printf("%d",ans);return 0;
- }
来源: http://www.bubuko.com/infodetail-2754822.html