hdu2063+hdu1083（最大匹配数）-白红宇

hdu2063+hdu1083（最大匹配数）

阅读量：6202 次

发布时间：2019-06-21

本文共 1899 字，大约阅读时间需要 6 分钟。

传送门：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 510#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair
                  
                   using namespace std;int g[N][N],vis[N],linker[N];int n,m;int dfs(int u){ for(int i=1;i<=m;i++) if(g[u][i]&&!vis[i]) { vis[i]=1; if(linker[i]==-1||dfs(linker[i])) { linker[i]=u; return 1; } } return 0;}int main(){ int k; while(scanf("%d",&k),k) { scanf("%d%d",&n,&m); FILL(g,0);FILL(linker,-1); while(k--) { int u,v; scanf("%d%d",&u,&v); g[u][v]=1; } int ans=0; for(int i=1;i<=n;i++) { FILL(vis,0); if(dfs(i))ans++; } printf("%d\n",ans); }}

View Code

传送门：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 310#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair
                  
                   using namespace std;int g[N][N],vis[N],match[N];int n,m;int dfs(int u){ for(int i=1;i<=m;i++) if(g[u][i]&&!vis[i]) { vis[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } return 0;}int main(){ int t,num,x; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); FILL(g,0);FILL(match,-1); for(int i=1;i<=n;i++) { scanf("%d",&num); while(num--) { scanf("%d",&x); g[i][x]=1; } } int sum=0; for(int i=1;i<=n;i++) { FILL(vis,0); if(dfs(i))sum++; } if(sum==n)puts("YES"); else puts("NO"); }}