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

HDU 1498 50 years,50 colors

题意

n*n的矩形中放入颜色值为[1,50]的气球，要求每一个人扎k次，每扎一次，可将同行或者同列相同颜色的气球全部扎破。求是否存在不可能全部扎破的气球，按照升序规律输出气球的颜色。

思路

每种颜色进行最小点覆盖运算，如果最小覆盖点num>k，则该颜色气球不能全部扎破。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 105;int map[N][N]; //气球的总图int link[N]; //link[j]:第j列被扎过时，扎的气球位置的行(无则-1)int useif[N]; //第i列是否被扎过int ans[N]; //记录不能全部扎破的气球，ans[i]为某颜色数值int len;int n, k;int dfs(int t, int col){
       for(int i = 0; i < n; i++)    {
           if(!useif[i] && map[t][i] == col)        {
               useif[i] = 1;            //寻找增广路，如果有增广路，说明该位置需要扎气球            if(link[i] == -1 || dfs(link[i], col))            {
                   link[i] = t;//说明i列被扎过，初始扎的气球位置在t行                return 1;            }        }    }    return 0;}int maxMatch(int col){
       memset(link, -1, sizeof(link));    int num = 0;    for(int i = 0; i < n; i++)    {
           memset(useif, 0, sizeof(useif));//对每一行都要初始化        if(dfs(i, col)) num ++;    }    return num;}int main(){
       while(scanf("%d %d", &n, &k) && n && k )    {
           memset(map, 0, sizeof(map));        len = 0;        for(int i = 0; i < n; i++)            for(int j=0;j
       
         k)//每种颜色都判断一次，执行n次最小点覆盖                ans[len ++] = i;        }        if(!len)            printf("-1\n");        else        {
               for(int i=0;i
       
      
     
    
   

转载地址：https://blog.csdn.net/qq_43826794/article/details/102843937 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！