首页 > 代码库 > POJ 1325

POJ 1325

2024-11-05 20:29:01   208人阅读

题目大意：

有A，B两种机器，A有1~n种模式 ， B有1~m种模式 ， 对于每一项任务，都要用到Ai 或 Bj中的一个 ， 将所有任务都做完，模式转换次数最少的次数

 

根据题目所给的x ， y的关系 ， 很容易画出二部图的基本框架， 这里不难看出是求一个最小的点覆盖集

在二部图中 ， 最小点覆盖数 = 二部图的最大分配数 ， 所以这题目直接看作是求一个二部图的最大分配

 

 1 #include <cstdio> 2 #include <cstring> 3  4 using namespace std; 5  6 int n , m , k; 7 int g[105][105] , visx[105] , visy[105] , cx[105] , cy[105]; 8  9 int dfs(int u)10 {11     visx[u] = 1;12     for(int v=1 ; v<=m ; v++){13         if(g[u][v] && !visy[v]){14             visy[v] = 1;15             if(cy[v] == -1 || dfs(cy[v])){16                 cx[u] = v;17                 cy[v] = u;18                 return 1;19             }20         }21     }22     return 0;23 }24 25 int MaxMatch()26 {27     int ans = 0;28     memset(cx , -1 , sizeof(cx));29     memset(cy , -1 , sizeof(cy));30     for(int i = 1 ; i<=n ; i++){31         if(cx[i] == -1 && !visx[i]){32             //每次都要进行能否找到增广路的判断，所以每次都memset33             memset(visx , 0 , sizeof(visx));34             memset(visy , 0 , sizeof(visy));35             ans += dfs(i);36         }37     }38     return ans;39 }40 41 int main()42 {43    // freopen("a.in" , "r" , stdin);44     while(scanf("%d" , &n) , n){45         scanf("%d%d" , &m , &k);46         int p , x , y ;47         memset(g , 0 , sizeof(g));48         for(int i = 0 ; i<k ; i++)49         {50             scanf("%d%d%d" , &p , &x , &y);51             g[x][y] = 1;52         }53         printf("%d\n" , MaxMatch());54     }55     return 0;56 }

 

POJ 1325


联系
我们