hdu 1045 Fire Net 二分图匹配 && HDU-1281-棋盘游戏

╰半夏微凉° 2023-10-11 09:33 28阅读 0赞

题意：任意两个个‘车’不能出现在同一行或同一列，当然如果他们中间有墙的话那就没有什么事，问最多能放多少个‘车’

代码+注释：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //二分图最大匹配问题
     2 //难点在建图方面，如果这个图里面一道墙也没有，那么可以说就是在横坐标（1...n）和纵坐标(1...n)
     3 //中个挑选出来一个，那个点就是我们要放置炮台的地方，么个点只能用一次，这样就能保证正确性
     4 //现在现在里面有墙了，在横坐标方面那么看到一个墙就把横坐标的选择数加1，每次换行也加1
     5 //纵坐标也做相应处理，那么我们就可以得到两个集合，一个横坐标集合，一个纵坐标集合
     6 //我们现在就是从这两个集合中选取元素，集合中元素的意义和没有墙时候的一样
     7 //但是他们并不是随意搭配，只有从两个集合中拿去的两个值，在原图中出现的位置相同才可以搭边
     8 #include<stdio.h>
     9 #include<algorithm>
    10 #include<string.h>
    11 #include<iostream>
    12 #include<queue>
    13 using namespace std;
    14 const int maxn=20;
    15 char maps[maxn][maxn];
    16 int link[maxn][maxn],used[maxn],id1[maxn][maxn],flag[maxn],id2[maxn][maxn];
    17 int n,lcnt,rcnt;
    18 bool dfs(int x)
    19 {
    20     for(int i=1;i<=lcnt;i++)
    21     {
    22         if(link[x][i] && !used[i])
    23         {
    24             used[i]=1;
    25             if(flag[i]==0 || dfs(flag[i]))
    26             {
    27                 flag[i]=x;
    28                 return 1;
    29             }
    30         }
    31     }
    32     return 0;
    33 }
    34 int match()
    35 {
    36     int ans=0;
    37     memset(flag,0,sizeof(flag));
    38     for(int i=1;i<=rcnt;++i)
    39     {
    40         memset(used,0,sizeof(used));
    41         ans+=dfs(i);
    42     }
    43     return ans;
    44 }
    45 int main()
    46 {
    47     while(~scanf("%d",&n)&&n)
    48     {
    49         rcnt=lcnt=0;
    50         memset(link,0,sizeof(link));
    51         memset(id1,0,sizeof(id1));
    52         memset(id2,0,sizeof(id2));
    53         for(int i=1;i<=n;++i)
    54             scanf("%s",maps[i]+1);
    55         for(int i=1;i<=n;++i)
    56         {
    57             for(int j=1;j<=n;++j)
    58             {
    59                 if(maps[i][j]=='.')
    60                 {
    61                     if(j-1==0 || maps[i][j-1]=='X') rcnt++;
    62                     id1[i][j]=rcnt;
    63                 }
    64             }
    65         }
    66         for(int j=1;j<=n;++j)
    67         {
    68             for(int i=1;i<=n;++i)
    69             {
    70                 if(maps[i][j]=='.')
    71                 {
    72                     if(i-1==0 || maps[i-1][j]=='X') lcnt++;
    73                     id2[i][j]=lcnt;
    74                 }
    75             }
    76         }
    77         for(int i=1;i<=n;++i)
    78         {
    79             for(int j=1;j<=n;++j)
    80             {
    81                 link[id1[i][j]][id2[i][j]]=1;
    82             }
    83         }
    84         printf("%d\n",match());
    85     }
    86     return 0;
    87 }

HDU-1281-棋盘游戏：

题意：这道题黑心那个一道题可不是完全一样，这上面可是没有墙这个东西，所以就是明显的二分图最大匹配，一个集合是对应的列，另一个集合是行

一个匹配边在棋盘上面就是一个具体的位置（因为行和列已经确定而且每个点只能使用一次）

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<algorithm>
     3 #include<string.h>
     4 #include<iostream>
     5 #include<queue>
     6 using namespace std;
     7 const int maxn=1005;
     8 int match[maxn],visit[maxn],n,id1,id2,m,grap[maxn][maxn],w[maxn][maxn],w1[maxn][maxn],w2[maxn][maxn];
     9 int dfs_solve(int x)
    10 {
    11     for(int i=1;i<=id2;++i)
    12     {
    13         if(grap[x][i] && !visit[i])
    14         {
    15             visit[i]=1;
    16             if(match[i]==0 || dfs_solve(match[i]))
    17             {
    18                 match[i]=x;
    19                 return 1;
    20             }
    21         }
    22     }
    23     return 0;
    24 }
    25 int hungan()
    26 {
    27     memset(match,0,sizeof(match));
    28     int sum=0;
    29     for(int i=1;i<=id1;++i)
    30     {
    31         memset(visit,0,sizeof(visit));
    32         sum+=dfs_solve(i);
    33     }
    34     return sum;
    35 }
    36 int main()
    37 {
    38     int n,m,k,e=0;
    39     while(~scanf("%d%d%d",&n,&m,&k))
    40     {
    41         memset(grap,0,sizeof(grap));
    42         while(k--)
    43         {
    44             int a,b;
    45             scanf("%d%d",&a,&b);
    46             grap[a][b]=1;
    47         }
    48         id1=n;  //这个题目和A题的区别就在于，本题目上的一句话“注意不能放车的地方不影响车的互相攻击”
    49         id2=m;  //所以这个题目可以看做简单的(1..n)和(1...m)的匹配
    50         int ans=hungan();
    51         int temp=0;
    52         for(int i=1;i<=n;++i)
    53         {
    54             for(int j=1;j<=m;++j)
    55             {
    56                 if(grap[i][j])
    57                 {
    58                     grap[i][j]=0;
    59                     int su=hungan();
    60                     if(su<ans) temp++;//,printf("%d\n",su);
    61                     grap[i][j]=1;
    62                 }
    63             }
    64         }
    65         printf("Board %d have %d important blanks for %d chessmen.\n",++e,temp,ans);
    66     }
    67     return 0;
    68 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11494301.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif