大家可以先看看这些大佬的博客(本人等过段时间自己写下自己的理解);
https://www.cnblogs.com/shenben/p/5573788.html
http://blog.csdn.net/nice_punch/article/details/54957819
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x7f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) const int mod = 1e9+7; const int maxn = 1e3+5; const double EPS = 1e-6; using namespace std; //左边是问题 右边是锦囊 int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } bool vis[maxn]; int p[maxn];//p[i] 表示第i个锦囊的匹配的是哪个问题,负一就是都没有匹配 vector<int> G[maxn]; bool fd(int u){ int len = sz(G[u]); rep(i,0,len){ int v = G[u][i]; if(vis[v]) continue; vis[v] = true; if(p[v]==-1||fd(p[v])){ //如果当前这个锦囊没有问题匹配的话,或者匹配这个锦囊的问题可以找到新的锦囊的话 p[v] = u;//v这个锦囊匹配u这个问题 return true; } } return false; } int main() { int n,m; while(~scanf("%d%d",&n,&m)){ //n种锦囊 m个问题 mt(p,-1); int x,y; rep(i,0,m){ scanf("%d%d",&x,&y); G[i].pb(x); G[i].pb(y); } int ans = 0; rep(i,0,m){ mt(vis,false); if(fd(i)) ans++; else break;//因为如果这题没有打出来 那他就不能继续往下答了 } printf("%d ",ans); } return 0; }
//D. 唐纳德和他的数学老师 #include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x7f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) const int mod = 1e9+7; const int maxn = 1e6+5; const int N = 3010; const double EPS = 1e-6; using namespace std; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int a[maxn]; bool isprime[maxn]; int prime[maxn]; int tot; vector<int> G[maxn]; bool vis[maxn]; int p[maxn]; void getprime(int mx){ mt(isprime,true);mt(prime,0); tot = 0; isprime[0] = isprime[1] = false; rep(i,2,mx+1){ if(isprime[i]) prime[++tot] = i; for(int j=1;j<=tot && i*prime[j]<=mx;j++){ isprime[i*prime[j]] = false; if(!(i%prime[j])) break; } } } void getedge(int x){ int u = x; for(int i=1;;i++){ if(prime[i]*prime[i]>x) break; if(x%prime[i]==0) G[u].pb(prime[i]); while(x%prime[i]==0) x/=prime[i]; } if(x>1) G[u].pb(x); return; } bool fd(int u){ int len = sz(G[u]); rep(i,0,len){ int v = G[u][i]; if(vis[v]) continue; vis[v] = true; if(p[v]==-1||fd(p[v])){ p[v] = u; return true; } } return false; } int main() { getprime(maxn-1); int n; scanf("%d",&n); rep(i,0,n) { scanf("%d",&a[i]); getedge(a[i]); } int ans = 0; mt(p,-1); rep(i,0,n){ mt(vis,false); if(fd(a[i])) ans++; else break; } printf("%d ",ans); return 0; }