最小生成树

定义 : 对于图 $ G = (V,E) $, 有 $n$ 个点, $m$ 条边, 由 $V$ 中所有 $n$ 个点和 $E$ 中 $n-1$ 条边构成的一个连通子图(即一棵树),称为 $G$ 的一个生成树, 边权值最小的为最小生成树.

求解方法:

1. prim算法 $O(n^2)$
2. kruskal算法 $O(mlogn)$

prim算法 :

一般用于稠密图:

#include <iostream>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510;
int n,m;
int g[N][N];    //稠密图
int dist[N];    //表示某个结点到当前集合的最小距离(与dijkstra不同)
int st[N];      //是否在集合内

int prim()
{
    memset(dist, INF, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ ){

        int t = -1; 
        for (int j = 1; j <= n; j ++ )          //寻找不在集合内，且到集合距离最小的结点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;      //进入集合

        if (i && dist[t] == INF)    return INF; //不存在生成树
        if (i)  res += dist[t];

        for (int j = 1; j <= n; j ++ )      //更新其它结点
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;

    memset(g, INF, sizeof g);

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        g[a][b] = g[b][a] = min(g[a][b], v);    //无向图
    }

    int t = prim();

    if (t == INF)
        puts("impossible");
    else    
        cout << t << endl;

    return 0;
}

kruskal算法 :

一般用于稀疏图

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

const int N = 1e5 + 10;
const int M = 2 * N;
int n,m;

int f[N];       //并查集的操作

struct Edge{
    int a, b;
    int v;
}edge[M];

bool comp(Edge x, Edge y)       //自定义比较
{
    return x.v < y.v;
}

int find(int x)                 //寻找祖宗结点
{
    if (f[x] != x)  return f[x] = find(f[x]);
    return f[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1, comp);

    for (int i = 1; i <= n; i ++ )      //并查集的初始化
        f[i] = i;

    int res = 0;        //记录距离之和
    int cnt = 0;        //存储结点数量
    for (int i = 1; i <= m; i ++ ){      //枚举每条边

        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int fa = find(a);
        int fb = find(b);

        if (fa != fb){           //合并集合
            f[fa] = fb;
            res += v;
            cnt ++;
        }
    }
    if (cnt < n - 1)
        puts("impossible");
    else
        cout << res << endl;

    return 0;

}

AcWing 1140. 最短网络 原题链接

算法思路:

最小生成树的模板题, 输入矩阵形式, 采用prim算法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int g[N][N];
int n;
int dist[N];
int st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;

    for (int i = 1; i <= n; i ++ ){
        int t = -1;

        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;

        res += dist[t];

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];

    cout << prim() << endl;

    return 0;
}

AcWing 1141. 局域网 原题链接

算法思路 :

kruakal算法求最小生成树, 注意每次当两个点需要删边时, 将结果加上权值.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 220;

struct Edge{
    int a, b, v;

    bool operator < (const Edge &t)const 
    {
        return v < t.v;
    }
}edge[M];
int fa[N];
int n ,m;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}


int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= m; i ++ )
        cout << edge[i].v << endl;
    for (int i = 1; i <= m; i ++ ){
        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int aa = find(a);
        int bb = find(b);

        if (aa != bb)   fa[aa] = bb;
        else
            res += v;
    }

    cout << res << endl;

    return 0;
}

AcWing 1142. 繁忙的都市 原题链接

算法思路 :

同样是模板题, 注意理解题意, 要求被改造的道路能够连通整个图(被选入生成树里的点)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

struct Edge{
    int a, b, v;
    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];

int n,m;
int fa[N];
int sum;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}


int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int aa = find(a);
        int bb = find(b);
        //cout << aa << ' ' << bb << endl;
        if (aa == bb)
            continue;
        else{
            sum ++;
            fa[aa] = bb;
            res = v;

        }
    }

    cout << sum << ' ' << res << endl;

    return 0;

}

AcWing 1143. 联络员 原题链接

算法思路 :

图中含有必选边和非必选边, 对于必选边我们直接加入到生成树中, 然后再根据kruskal算法加入非必选边

• kruskal算法求最小生成树可以从中间开始

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, M = 10010;

struct Edge{
    int op, a, b, v;
    bool operator < (const Edge &t)const
    {
        if (op == t.op)
            return v < t.v;
        return op < t.op;
    }
}edge[M];
int fa[N];
int n, m;


int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}

int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int op, a, b, v;
        cin >> op >> a >> b >> v;
        edge[i] = {op, a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= m; i ++ ){
        int op = edge[i].op;
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        int v = edge[i].v;

        if (op == 1){
            res += v;
            if (aa != bb)
                fa[aa] = bb;
        }else{
            if (aa == bb)
                continue;
            else{
                res += v;
                fa[aa] = bb;
            }
        }
    }


    cout << res << endl;

    return 0;
}

AcWing 1144. 连接格点 原题链接

算法思路 :

原图中有 $m * n$ 个点, 其中横向点之间、纵向点之间都有边, 根据kruskal算法,先加入纵向边(权值小),再加入横向边(权值大).
我们可以直接在加边时进行排序,避免sort().

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2 * 1e6 + 10, M = 2 * 1e6 + 10;
int g[1010][1010];
struct Edge{
    int a, b, v;

    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];
int fa[N];
int n, m;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1, t = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            g[i][j] = t ++;

    for (int i = 1; i <= n * m; i ++ )
        fa[i] = i;

    int cnt = 0;
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j < n; j ++ ){
            int a = g[j][i], b = g[j + 1][i];
            int v = 1;
            //cout << a << ' ' << b << endl;
            edge[cnt ++] = {a, b, v};
        }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j < m; j ++ ){
            int a = g[i][j], b = g[i][j + 1];
            int v = 2;
            //cout << a << ' ' << b << endl;
            edge[cnt ++] = {a,b,v};
        }
    int x1, y1, x2, y2;
    while (~scanf("%d%d%d%d",&x1, &y1, &x2, &y2)){
        int a = g[x1][y1];
        int b = g[x2][y2];
        int aa = find(a);
        int bb = find(b);
        fa[aa] = bb;
    }

    int res = 0;

    for (int i = 0; i < cnt; i ++ ){
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        int v = edge[i].v;
        if (aa == bb)
            continue;
        else{
            res += v;
            fa[aa] = bb;
        }
    }

    cout << res << endl;

    return 0;

}

算法模型：贪心 + dp

思想：分类讨论

由于题目要求的是任意长度为K的区间的异或和都为0，如果存在这样的两个区间seq[a,a+k-1]和seq[b,b+k-1]
其中a<b，异或运算的推导可以得到，这两个区间不重叠的部分是一样的，换句话说就是最终答案一定是以k为周期的序列 。
先考虑一种简单的情况，先将异或和为0的条件去掉，如何修改序列中的元素使得序列变成周期是k的序列，可以采用贪心的方法。在一个周期内，对于每一列来说是独立的，因此求出每一列元素的众数，然后修改行数-众数就是这列的最小的修改次数了。
然后我们想想怎么把异或和为0的限制加上，这里需要分情况讨论。第一种情况采用贪心的方法求得最优解。因为修改后的元素可能是原序列中没有出现过的元素。如果修改的某一列的元素是原序列中没有出现过的元素，那么这种情况下一定可以用贪心的办法求出最优解，做法是将众数最小的一列中的每个数变成一个全新的，该列中没有出现的，使得每个周期内的元素的异或和为0的数。第二种情况采用dp的方法求得最优解在这种情况下，由于没有最终修改后的元素是原数组中存在的数，因此可以从前往后枚举每一列，然后枚举选择第几行的数作为这列元素修改后的元素，由于异或具有交换性质，因此不具有顺序的问题，所以可以采用dp的方法递推出将序列变成数组中本来存在的某个数的情况。边界，f[0][0] = 0，目标状态是f[k][0]，状态表示f[i][j]为前i列异或和为j的情况下的最小值。

class Solution {
public:
    const int N = 1024, INF = 1e8;
    int s[1024];    //求众数的数组

    int minChanges(vector<int>& nums, int k) {
        int n = nums.size(), m = (n + k - 1) / k;
        vector<vector<int>> f(k+1,vector<int>(N,INF));

        int cnt = 0, minv = INF;
        f[0][0] = 0;    //边界：第0列只有异或和为0是合法的状态
        for(int i=1;i<=k;i++){
            int len = m;
            memset(s,0,sizeof s);
            if(n % k && n%k < i) len --;
            for(int j=0;j<len;j++){
                s[nums[j * k + i - 1]] ++;
            }
            int maxv = 0;
            for(int j=0;j<N;j++){
                maxv = max(maxv,s[j]);
            }
            cnt += len - maxv;
            minv = min(minv,maxv);
            for(int j=0;j<N;j++){
                for(int u=0;u<len;u++){
                    int x = nums[u*k+i-1];
                    f[i][j] = min(f[i][j],f[i-1][j^x] + len - s[x]);    //将x作为修改后的值
                }
            }
        }
        return min(cnt + minv, f[k][0]);    //返回贪心解和dp解的最小值
    }
};

/*
给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

输入格式
第一行包含两个整数n和m

接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。
 */

import java.util.*;
import java.io.*;

class Main {

    static int N, M;
    static int idx;
    //e[i]:第i条边的终边 ne[i]:第i条边的下一条边起点 h[j]: j号点的第一条边
    static int[] e, ne, h;
    //a->b
    public static void add(int a, int b) {
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++; 
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        N = in[0]; M = in[1];
        e = new int[M+1]; h = new int[N+1]; ne = new int[M+1];
        int[] indeg = new int[N+1];
        Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br); //t[0]->t[1]
            add(t[0], t[1]);
            indeg[t[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (indeg[i] == 0) {
                queue.add(i);
            }
        }
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            sb.append(cur+" ");
            cnt++;
            for (int i = h[cur]; i != -1; i = ne[i]) {
                if (--indeg[e[i]] == 0) {
                    queue.add(e[i]);
                }
            }
        }
        out.println(cnt < N ? -1 : sb.toString());
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

算法1

思路：|A1-c|+|A2-c|+…+|An-c|求最小值
转化成(|Ai-c|+|A1+c|)+(|A2-c|+|An-1 +c|)+....+A中
组成两点之间建立一个仓库，最后每一组均取最小值，此时整个整式取最小值

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N=100010;

typedef long long LL;
int n;
int x[N];

int main(){

    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&x[i]);
    sort(x,x+n);

    int  c=x[n/2];//中点
    LL res=0;
    for(int i=0;i<n;i++)res+=abs(x[i]-c);//遍历一下每个店到中点的距离
    printf("%lld\n",res);


    return 0;
}

连通性状压DP

若将横着放的方格放置好，那么竖着放的方格如何放是固定的，即尽量塞满。

$ 时间复杂度O(M2^N2^N),空间复杂度O(2^NM)$
时间复杂度可以看成是指数级别的。

参考文献

算法基础课

AC代码

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

typedef long long LL;
const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
bool st[M];//为j|k服务,即对于j|k的状态,0是连续的偶数个是否成立

int main(){
    while (cin >> n >> m, n || m){
        memset(f, 0, sizeof f);
        //初始化st数组
        for (int i = 0 ; i < 1 << n ; i ++){
            st[i] = true;
            int cnt = 0;//记录连续0的个数
            for (int j = 0 ; j < n ; j ++){
                if (i >> j & 1){
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                } else cnt ++;
            }
            if (cnt & 1) st[i] = false;
        }


        //状态压缩DP
        f[0][0] = 1;
        for (int i = 1 ; i <= m ; i ++){
            for (int j = 0 ; j < 1 << n ; j ++){
                for (int k = 0 ; k < 1 << n ; k ++){
                    if ((j & k) == 0 && st[j | k] )
                        f[i][j] += f[i - 1][k];
                }
            }
        }

        cout << f[m][0] << endl;
    }
    return 0;
}

include [HTML_REMOVED]

int main()
{
int a,b;
scanf(“%d %d”,&a,&b);
int c;
c=a+b;
printf(“%d”,c);

return 0;

}

打卡失败....

C++ 代码

#include <iostream>
using namespace std;
int main()
{
    int x;
    cin>>x;
    for(int i=x+1-(x%2),j=6;j>=1;j--,i+=2)
    cout<<i<<endl;
    return 0;
}