![](https://iknow-base.cdn.bcebos.com/lxb/notice.png)
一道C/c++编程题目求解答
晴天小猪有一张n*m的矩形大披萨,披萨上点缀着k个小甜点。晴天小猪是一只吃货,他一次可以吃一行或者一列披萨。晴天小猪想吃掉所有的小甜点,现在给你每个小甜点分布的坐标,问晴...
晴天小猪有一张n*m的矩形大披萨,披萨上点缀着k个小甜点。晴天小猪是一只吃货,他一次可以吃一行或者一列披萨。晴天小猪想吃掉所有的小甜点,现在给你每个小甜点分布的坐标,问晴天小猪至少吃几次可以吃掉所有的小甜点。
展开
2个回答
展开全部
分析:将行做表看作一个集合的点,列坐标看作一个集合的点,每个点就连接两个集合的边,求出最大匹配就是所要的答案。。。
参考代码:
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int map[505][505];
int vis[1001];
int flag[1001]; //flag[i]记录与i相连的边。
int n,m;
bool dfs(int s) //一般也写作find(int s)
{
int i,j;
for(i=1;i<=n;i++)
{
if(!vis[i] && map[s][i])
{
vis[i]=1;
if(flag[i]==0 || dfs(flag[i])) //若i没有于别的边相连,或者与i相连的那条边于变得边相连。
{
flag[i]=s;
return true;
}
}
}
return false;
}
int main()
{
int k,x,y,i,j;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
if(n<m)
n=m;// n取较大的数
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
for(i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=1;
}
int result=0;
for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) result++;
}
cout<<result<<endl;
}
return 0;
}
这个是能AC的代码,欢迎交流哈。满意请采纳。
追问
能再详细点吗,
不是特别懂..
追答
这个是图论中的最大匹配问题,你学习一下图论吧。
展开全部
//摄氏度转换成华氏温度
#include<stdio.h>
//温度计算公式
float f1(float ab)
{
float huash;
huash=1.8*ab+32;
return huash;
}
void main()
{
float f,result;
//提示输入摄氏温度;
printf("请输入温度:\n");
scanf("%f",&f);
result=f1(f);
printf("转换成华氏温度");
printf("%2f",result);
scanf("%f",&f);
}
#include<stdio.h>
//温度计算公式
float f1(float ab)
{
float huash;
huash=1.8*ab+32;
return huash;
}
void main()
{
float f,result;
//提示输入摄氏温度;
printf("请输入温度:\n");
scanf("%f",&f);
result=f1(f);
printf("转换成华氏温度");
printf("%2f",result);
scanf("%f",&f);
}
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询