二分图最大匹配 51nod 2006

xiaoxiao2021-02-28  39

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=2006

//#include <bits/stdc++.h> #include<stdio.h> #include<string.h> #include<string> #include<math.h> #include<algorithm> #include<iostream> #include<queue> #include<vector> #include<stack> #include<map> #include<set> #include<stdlib.h> #include<time.h> #include <iomanip> #define lowbit(x) (x&(-x)) #define inf 0x7fffffff #define linf 0x7fffffffffffffff #define fill(x,y) memset(x,y,sizeof(x)) #define fup(i,x,y) for(int i=(x);i<=(y);i++) #define fdn(i,x,y) for(int i=(x);i>=(y);i--) #define sp(x) setprecision(x) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define sc(n) scanf("%s",&n) #define pf(x) printf("%d\n",x) #define pfl(x) printf("%lld\n",x) #define pff(x) printf("%lf\n",x) #define N 200005 #define M 4000009 #define mod 9973 #define pi acos(-1) //cout.setf(ios::fixed); //freopen("out.txt","w",stdout); using namespace std; typedef long long ll; typedef double db; inline int scan(int &n) { int res=0,ch,flag=0; if((ch=getchar())=='-')flag=1; else if(ch>='0' && ch<='9')res=ch-'0'; while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-'0'; n= flag ? -res : res; } vector<int> q[105]; int n,vis[105],link[105]; int ok(int x) { for(int i=0;i<q[x].size();i++) { int tp=q[x][i]; if(!vis[tp])//首先判断是否被访问过 { vis[tp]=1; if(!link[tp]||ok(link[tp])) { link[tp]=x; return 1; } } } return 0; } int main() { int m; sdd(n,m); int x,y; while(~sdd(x,y)) { if(x==-1&&y==-1) break; q[x].push_back(y); } int ans=0; fup(i,1,n) { fill(vis,0); if(ok(i)) ans++; } pf(ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1950176.html

最新回复(0)