（男生喜欢特定的女生，女生可以嫁给任何男生=

先按题意求出最大匹配，然后在左边增加n-res个虚拟男生喜欢所有女生，m-res个虚拟女生喜欢所有男生，再求最大匹配，这个时候肯定是个完全匹配，求匹配只是确定新的二分图里面每个男生对应的女生是谁=

在所有女生女生里面建有向图，将某男生匹配的女生连向所有他喜欢的女生一条边，求一遍tarjan，这样所有和他匹配的女生在一个连通分量里面的女生都可以选=

为什么？因为可以间接交换而不改变匹配数！

本来明白思路之后很快就打完了，却一直TLE，T了一个下午wocao！百思不得其解！

然后在一下午的修改，查找后终于发现了bug，在代码的92行，刚开始我没加&&g[i][j]这个条件，当时打代码没细想，觉得在一个环就肯定能交换，忘了男生要喜欢这个女生==but！艹！特么给我wa还能解释，TLE我现在还是不能接受，好醉===

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 stack
           
            s; 8 vector
            
             G[1105]; 9 int g[1105][1105],y[1105],link[1105],linky[1105]; 10 int dfs_clock,scc_cnt,pre[1105],lowlink[1105],sccno[1105]; 11 int n1,n2,d[1105],ans[1105][1105]; 12 int dfs(int u){ 13 for (int i=1;i<=n2;i++) 14 if (g[u][i]&&!y[i]){ 15 y[i]=1; 16 if (!link[i]||dfs(link[i])){ 17 link[i]=u; 18 return 1; 19 } 20 } 21 return 0; 22 } 23 int maxmatch(){ 24 memset(link,0,sizeof(link)); 25 int ans=0; 26 for (int i=1;i<=n1;i++){ 27 memset(y,0,sizeof(y)); 28 if (dfs(i)) ans++; 29 } 30 return ans; 31 } 32 void tarjan(int u){ 33 int v; 34 pre[u]=lowlink[u]=++dfs_clock; 35 s.push(u); 36 for (int i=0;i
            
           
          
         
        
       
      

题目链接：