最小圆覆盖的C++代码

答：#include<stdio.h>
int main()
{
int x, y, r, p, q;
printf("输入圆心坐标和半径：\n");
scanf("%d %d %d", &x, &y, &r);
printf("圆心(%d, %d) 半径 %d\n", x, y, r);
for (p = x - r; p <= x + r; p++)
{
for (q = y - r; q <= y + r; q++)
{
if (p*p + q*q - 2*x*p - 2*y*q + x*x + y*y - r*r <= 0)
printf("*");
else
printf(" ");
}
printf("\n");
}
return 0;
}

相关问题

回溯解最小顶点覆盖问题C++伪代码

以下是回溯解最小顶点覆盖问题的C++伪代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;
int n, m;
int g[N][N];
bool st[N];
int ans = N;

void dfs(int u, int cnt)
{
    if (cnt >= ans) return; // 剪枝：如果当前已经选的点数大于等于之前的答案，就不用继续搜索了
    if (u == n) // 搜索到叶子节点
    {
        ans = cnt;
        return;
    }

    // 不选当前节点
    dfs(u + 1, cnt);

    // 选当前节点
    bool flag = true;
    for (int i = 0; i < u; i++)
        if (g[i][u] && st[i]) // 如果当前节点与之前已选的节点有连边，就不能选
        {
            flag = false;
            break;
        }
    if (flag)
    {
        st[u] = true;
        dfs(u + 1, cnt + 1);
        st[u] = false;
    }
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}

分支限界法之最小权顶点覆盖问题c++实现

最小权顶点覆盖问题可以转化为最大匹配问题，而最大匹配问题可以使用匈牙利算法解决。以下是使用分支限界法解决最小权顶点覆盖问题的c++代码示例：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m, ans = INF;
int w[MAXN][MAXN]; // 权值矩阵
int lx[MAXN], ly[MAXN], slack[MAXN]; // 顶标数组
int link[MAXN], visx[MAXN], visy[MAXN]; // 匈牙利算法中的变量

struct Node {
    int u, v, w;
    bool operator < (const Node& a) const {
        return w > a.w;
    }
};

void init() {
    memset(link, -1, sizeof(link));
    memset(lx, -INF, sizeof(lx));
    memset(ly, 0, sizeof(ly));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            lx[i] = max(lx[i], w[i][j]);
        }
    }
}

bool dfs(int u) {
    visx[u] = 1;
    for (int v = 1; v <= m; v++) {
        if (!visy[v]) {
            int tmp = lx[u] + ly[v] - w[u][v];
            if (tmp == 0) {
                visy[v] = 1;
                if (link[v] == -1 || dfs(link[v])) {
                    link[v] = u;
                    return true;
                }
            } else {
                slack[v] = min(slack[v], tmp);
            }
        }
    }
    return false;
}

void KM() {
    for (int i = 1; i <= n; i++) {
        memset(slack, INF, sizeof(slack));
        while (true) {
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if (dfs(i)) break;
            int d = INF;
            for (int j = 1; j <= m; j++) {
                if (!visy[j]) d = min(d, slack[j]);
            }
            for (int j = 1; j <= n; j++) {
                if (visx[j]) lx[j] -= d;
            }
            for (int j = 1; j <= m; j++) {
                if (visy[j]) ly[j] += d;
                else slack[j] -= d;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if (link[i] != -1) ans = min(ans, lx[link[i]] + ly[i]);
    }
}

void dfs(int u, int cnt, int sum) {
    if (cnt >= ans) return;
    if (u == n + 1) {
        ans = cnt;
        return;
    }
    priority_queue<Node> pq;
    for (int i = 1; i <= m; i++) {
        if (lx[u] + ly[i] == w[u][i]) {
            pq.push({u, i, w[u][i]});
        }
    }
    while (!pq.empty()) {
        int u = pq.top().u, v = pq.top().v, w = pq.top().w;
        pq.pop();
        if (visx[u] || visy[v]) continue;
        visx[u] = visy[v] = 1;
        link[v] = u;
        dfs(u + 1, cnt + 1, sum + w);
        link[v] = -1;
        visx[u] = visy[v] = 0;
    }
    dfs(u + 1, cnt, sum);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
        }
    }
    init();
    KM();
    memset(visx, 0, sizeof(visx));
    memset(visy, 0, sizeof(visy));
    dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}

其中，`w[i][j]`表示第i个点和第j条边之间的权值，`lx[i]`表示第i个点的顶标，`ly[j]`表示第j条边的顶标，`link[j]`表示第j条边匹配的点，`visx[i]`表示第i个点是否被访问过，`visy[j]`表示第j条边是否被访问过。`KM()`函数为求解最大权匹配的函数，`dfs()`函数为分支限界法的递归函数。