首页 > 代码库 > 二分图行列匹配---> hdu2119,hdu1498

二分图行列匹配---> hdu2119,hdu1498

2024-07-26 19:40:35   216人阅读

hdu2119

题意：给定一个矩形方格，每个格子里面的数字是0或者1，每次操作可以把一整行或列的1变成0，问最少多少次操作能将1全部变为0

一次可以消除某一行或者某一列的1
但是可以这么想，最多有多少个1即不在同一行，也不在同一列，有多少个，那么就要消多少次
那么就是求行和列的最大匹配

 1 #include <stdio.h> 2 #include <string.h> 3 const int N = 100 + 10; 4 int Map[N][N]; 5 bool vis[N]; 6 int cy[N]; 7 int n,m; 8 bool dfs(int u) 9 {10     for(int i=0; i<m; ++i)11     {12         if(!vis[i] && Map[u][i])13         {14             vis[i] = true;15             if(cy[i] == -1 || dfs(cy[i]))16             {17                 cy[i] = u;18                 return true;19             }20         }21     }22     return false;23 }24 int MaxMatch()25 {26     memset(cy, -1, sizeof(cy));27     int ans = 0;28     for(int i=0; i<n; ++i)29     {30         memset(vis, 0, sizeof(vis));31         ans += dfs(i);32     }33     return ans;34 }35 int main()36 {37     int i,j;38     while(true)39     {40         scanf("%d",&n);41         if(n == 0)42             break;43         scanf("%d",&m);44         for(i=0; i<n; ++i)45             for(j=0; j<m; ++j)46             {47                 scanf("%d",&Map[i][j]);48             }49         int ans = MaxMatch();50         printf("%d\n",ans);51     }52 }

 hdu1498

比上面那题复杂一点，不过也是一样，每次只能消一行或者一列相同颜色的气球

一共就50中颜色，我们可以枚举每一种颜色构成的矩形，然后对其进行行列匹配，如果最大匹配 > k , 那么就不能在k次内完全消除该种颜色的气球

 1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 using namespace std; 5 const int N = 100 + 10; 6 const int M = 50 + 10; 7 int Map[M][N][N]; 8 int color[M]; 9 bool vis[N];10 int cy[N];11 int ans[M];12 vector<int> G[N];13 int cnt;14 int n,k;15 void init()16 {17     for(int i=0; i<n; ++i)18         G[i].clear();19     20 }21 bool dfs(int u)22 {23     for(int i=0; i<G[u].size(); ++i)24     {25         int v = G[u][i];26         if(!vis[v])27         {28             vis[v] = true;29             if(cy[v] == -1||dfs(cy[v]))30             {31                 cy[v] = u;32                 return true;33             }34         }35     }36     return false;37 }38 int MaxMatch()39 {40     memset(cy, -1, sizeof(cy));41     int cnt = 0;42     for(int i=0; i<n; ++i)43     {44         memset(vis, 0, sizeof(vis));45         cnt += dfs(i);46     }47     return cnt;48 }49 int main()50 {51     //freopen("in.txt","r",stdin);52     int i,j;53     while(true)54     {55         scanf("%d%d",&n,&k);56         if(n == 0 && k==0)57             break;58         int t;59         memset(Map, 0, sizeof(Map));60         memset(color, 0, sizeof(color));61         cnt = 0;62         for(i=0; i<n; ++i)63             for(j=0; j<n; ++j)64             {65                 scanf("%d",&t);66                 Map[t][i][j] = 1;67                 color[t] = 1;68             }69         for(t=1; t<=50; ++t)70             if(color[t])//枚举每一种颜色构成的矩阵71             {72                 init();    73                 for(i=0; i<n; ++i)74                     for(j=0; j<n; ++j)75                     {76                         if(Map[t][i][j] == 1)77                             G[i].push_back(j);//用vector存储78                     }79                 int tmp = MaxMatch();80                 if(tmp > k)81                     ans[cnt++] = t;82             }83         if(cnt == 0)84             puts("-1");85         else86         {87             printf("%d",ans[0]);88             for(i=1; i<cnt; ++i)89                 printf(" %d",ans[i]);90             puts("");91         }92     }93     return 0;    94 }

 

二分图行列匹配---> hdu2119,hdu1498


联系
我们