一道C/c++编程题目求解答

Question

晴天小猪有一张n*m的矩形大披萨，披萨上点缀着k个小甜点。晴天小猪是一只吃货，他一次可以吃一行或者一列披萨。晴天小猪想吃掉所有的小甜点，现在给你每个小甜点分布的坐标，问晴天小猪至少吃几次可以吃掉所有的小甜点。

Answer 1

分析：将行做表看作一个集合的点，列坐标看作一个集合的点，每个点就连接两个集合的边，求出最大匹配就是所要的答案。。。

参考代码：

#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的代码，欢迎交流哈。满意请采纳。

追问

能再详细点吗，
不是特别懂..

追答

这个是图论中的最大匹配问题，你学习一下图论吧。

Answer 2

//摄氏度转换成华氏温度

#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);
}