2019.01.17 bzoj1854: [Scoi2010]游戏（二分图匹配）

传送门

二分图匹配菜题。

题意：nnn个二元组(xi,yi)(x_i,y_i)(xi​,yi​)，每个二元组可以选一个数总共nnn个数aia_iai​，问将aia_iai​排好序之后从111开始最多可以连续存在多少个自然数。

代码：

#include<bits/stdc++.h>#define ri register intusing namespace std;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}const int N=1e6+5,M=1e4+5;int vis[M],n,pre[N],ans=0;vector<int>e[M];inline bool dfs(int p){if(vis[p])return 0;vis[p]=1;for(ri i=0;i<e[p].size();++i)if(!pre[e[p][i]]||dfs(pre[e[p][i]]))return pre[e[p][i]]=p,1;return 0;}int main(){n=read();for(ri i=1,x;i<=n;++i){x=read(),e[x].push_back(i);x=read(),e[x].push_back(i);}for(ri i=1;i<=10000;++i){memset(vis,0,sizeof(vis));if(dfs(i))++ans;else break;}cout<<ans;return 0;}