简单二分图
- /**************************************************************
- Problem: 1191
- User: lxy8584099
- Language: C++
- Result: Accepted
- Time:24 ms
- Memory:852 kb
- ****************************************************************/
- /*
- 这题和那啥连续攻击系统一样
- 二分图 没有匹配就 break
- */
- #include<cstdio>
- using namespace std;
- const int N=1050;
- struct pp {int nxt,v;} e[N<<1];
- int n,m,tot,ans,fa[N],vis[N],head[N];
- void add(int u,int v)
- {
- e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;
- }
- bool dfs(int u,int t)
- {
- for(int j=head[u];j;j=e[j].nxt)
- {
- int v=e[j].v;
- if(vis[v]^t)
- {
- vis[v]=t;
- if(!fa[v]||dfs(fa[v],t))
- {
- fa[v]=u;return 1;
- }
- }
- }
- return 0;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1,x,y;i<=m;i++)
- {
- scanf("%d%d",&x,&y);
- add(i,x+1),add(i,y+1);
- }
- for(int i=1;;i++)
- if(dfs(i,i)) ans++;else break;
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2949073.html