洛谷P3386

我还是比较喜欢叫它——谈恋爱算法。。。详见  

注意：判断的条件是:if(f[x][i]==1&&used[i]==0)

　　　其他没什么了，如果每次用memset会超时，可以使用二维数组记录

 

1 #include
     
       2 using namespace std; 3 inline int sc() 4 {    int x=0,f=1;char ch=getchar(); 5     while(!isdigit(ch)){    if(ch==45)f=-1;ch=getchar();} 6     while(isdigit(ch)) {    x=x*10+ch-48;ch=getchar();} 7     return x*f; 8     } 9 int f[1010][1010],lk[1010],n,m,e;10 bool vis[1010];11 bool find(int x)12 {    for(int i=1;i<=m;i++)13     {    if(f[x][i]==1&&vis[i]==0)14         {    vis[i]=1;15             if(lk[i]==0||find(lk[i]))16                  return lk[i]=x,1;17              }18         }19     return false;20     }21 int main()22 {    n=sc();m=sc();e=sc();23     for(int i=1;i<=e;i++)24     {    int u=sc(),v=sc();25         if(u>n||v>m)continue;26         f[u][v]=1;27         }28     int cnt=0;29     for(int i=1;i<=n;i++)30     {    memset(vis,0,sizeof(vis));31         if(find(i)) cnt++;32         }33     cout<
      
       <