精华内容
下载资源
问答
  • 连接格

    2020-03-22 21:07:07
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 格式 输入格式 第一行输入个正整数m和n。(m,n≤1000) 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2...

    P1105 连接格点
    描述
    有一个M行N列的点阵,相邻两点可以相连。一条纵向的连线花费一个单位,一条横向的连线花费两个单位。某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。

    格式
    输入格式
    第一行输入两个正整数m和n。(m,n≤1000)

    以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1−x2|+|y1−y2|=1。
    输出格式
    输出使得连通所有点还需要的最小花费。
    样例
    输入样例
    2 2
    1 1 2 1
    输出样例
    3
    思路
    将矩阵的位置按照从左到右,从上到下进行排序得到点
    这样的点就是一维的了,点连接是图,只不过这一次的图是一个矩形;

    坑点:这个数据m,n<=1000,就要注意一下了。那么最多可能有1000000个点,那么,我所用的保存edge边的信息的结构体就可能有3000000或者4000000个信息,然后我以为这个数太大了,数组或者结构体会爆炸,sort不能用,结果居然可以

    跨考小白有话说:欢迎大家说说更好的方法让我借鉴一下

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <math.h>
    using namespace std;
    //todo 连接格点    将矩阵的位置按照从左到右,从上到下进行排序得到点
    int f[1000002];
    struct node
    {
        int u, v, w;
    } edge[4000002]; //!定义边的信息    注意这里的数据大小
    int m, n, r1, r2, s1, s2, z = 0, ans = 0;
    find(int x)
    {
        if (f[x] != x)
        {
            return find(f[x]);
        }
        else
        {
            return x;
        }
    }
    bool cmp(node a, node b)
    {
        return a.w < b.w;
    }
    int main()
    {
        scanf("%d", &m);
        scanf("%d", &n);
        for (int i = 1; i <= m * n; i++) //*初始化并查集
        {
            f[i] = i;
        }
        for (int i = 1; i <= m; i++) //*初始化横向权值
        {
            for (int j = 1; j < n; j++)
            {
                int x = (i - 1) * n + j;
                int y = x + 1;
                edge[++z].u = x;
                edge[z].v = y;
                edge[z].w = 2;
            }
        }
        for (int i = 1; i <= n; i++) //*初始化纵向权值
        {
            for (int j = 1; j < m; j++)
            {
                int x = (j - 1) * n + i;
                int y = x + n;
                edge[++z].u = x;
                edge[z].v = y;
                edge[z].w = 1;
            }
        }
        while (scanf("%d%d%d%d", &r1, &s1, &r2, &s2) != EOF) //*同上
        {
            int x = (r1 - 1) * n + s1;
            int y = (r2 - 1) * n + s2;
            edge[++z].u = x;
            edge[z].v = y;
            edge[z].w = 0;
        }
        sort(edge + 1, edge + 1 + z, cmp); //*对边进行排序
        for (int i = 1; i <= z; i++)       //*merge  kruskal算法
        {
            int a = find(edge[i].u);
            int b = find(edge[i].v);
            if (a != b)
            {
                f[a] = b;
                ans += edge[i].w;
            }
        }
        printf("%d\n", ans);
        return 0;
    }
    
    展开全文
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列点和第 x2 行第 y2 列点...

    Kruskal(缩点) + 并查集 - 连接格点 - AcWing 1144

    有一个 m 行 n 列的点阵,相邻两点可以相连。

    一条纵向的连线花费一个单位,一条横向的连线花费两个单位。

    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。

    输入格式

    第一行输入两个正整数 m 和 n。

    以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点已经有连线。

    输入保证|x1−x2|+|y1−y2|=1。

    输出格式

    输出使得连通所有点还需要的最小花费。

    数据范围

    1m,n10000线100001≤m,n≤1000, 0≤已经存在的连线数≤10000

    输入样例:

    2 2
    1 1 2 1
    

    输出样例:

    3
    

    分析:

    首先将已经连接好的点加入到对应的连通块中,接着在各个连通块之间跑最小生成树即可。

    主要问题有:

    便①、二维坐标点转化到一维坐标上去,方便建图。

    ②、各点与相邻点之间的边如何建立。

    \qquad事实上,只要把点都加入连通块中去即可,故每条无向边我们仅需建立一次。

    \qquad为了节约空间,我们对每个点,将该点与其相邻的右、下两个点建立一条边。

    n×m106③、本题最多有n×m条边,极限在10^6级别。排序的话时间限制仍然较紧。

    121\qquad但是我们发现,边权仅有1和2两种情况,故我们可以优先建立边权为1的竖边。

    \qquad这仅需在循环所有点建图的时候循环两次,第一次建立每个点下方的边,第二次建立右方的边。

    O(M)M=n×m\qquad这就把求最小生成树的时间复杂度优化到了O(M),其中M=n×m,即边的数量。

    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N=1010, M=N*N, K=2*M;
    
    int n,m,res,ecnt;
    int p[M];
    int ids[N][N];
    struct edge
    {
        int u,v,w;
    }E[K];
    
    int Find(int x)
    {
        if(p[x]!=x) return p[x]=Find(p[x]);
        return p[x];
    }
    
    void get_edges()
    {
        int dir[2][2]{{1,0},{0,1}}, w[2]={1,2};  //一条边加一次就行,防数组越界,对每个点加右、下两条边
        
        for(int z=0;z<2;z++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    int x=i+dir[z][0],y=j+dir[z][1];
                    if(x>0&&x<=n&&y>0&&y<=m)
                    {
                        int a=ids[i][j],b=ids[x][y];
                        E[ecnt++]={a,b,w[z]};   
                    }
                }
    }
    
    void kruskal()
    {
        int a,b;
        for(int i=0;i<ecnt;i++)
        {
            a=Find(E[i].u),b=Find(E[i].v);
            if(a!=b)
            {
                p[a]=b;
                res+=E[i].w;
            }
        }
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n*m;i++) p[i]=i;
        
        for(int i=1,idx=0;i<=n;i++)
            for(int j=1;j<=m;j++)
                ids[i][j]=++idx;
                
        int x0,y0,x2,y2;
        while(~scanf("%d%d%d%d",&x0,&y0,&x2,&y2))
        {
            int a=ids[x0][y0],b=ids[x2][y2];
            a=Find(a),b=Find(b);
            p[a]=b;
        }
        
        get_edges();
        
        kruskal();
        
        cout<<res<<endl;
        
        return 0;
    }
    
    展开全文
  • 题解-连接格

    2019-06-01 14:03:35
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入 第一行输入个正整数m和n, 其中 1 <= n,m <= 1000。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第...

    连接格点

    描述

    有一个M行N列的点阵,相邻两点可以相连。一条纵向的连线花费一个单位,一条横向的连线花费两个单位。某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。

    输入

    第一行输入两个正整数m和n, 其中 1 <= n,m <= 1000。

    以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。

    输出

    输出使得连通所有点还需要的最小花费。

    输入样例 1

    2 2
    1 1 2 1

    输出样例 1

    3

    此题使用并查集,最好用图表的形式来写。
    重要信息:

    • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通
    • 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。
    • 输出使得连通所有点还需要的最小花费。

    因为这道题格点为重要信息,因此,你最先想到的肯定是二维数组。
    二维数组图表:
    在这里插入图片描述
    这就只能用(x,y)的坐标来表示了,所以要用pair来写。但是,你是否想过,这会处理很长的一片。
    因此,我们用一维数组更好一些。
    但是,我们要怎么表示呢?——标记
    如图:
    在这里插入图片描述

    很简单,我们将行和列的数字一 一标记,这样,我们就方便了很多。
    一个问题,因为标记了,就是去了二维数组查找的功能,怎么办?

    x*m+y
    

    这是一个算术,我们用这个来表示位置。(但这是从2开始找的,习惯从1开始找,就改变成x*m+y-m)最好用函数来表示。
    实现此结构:

    int convert(int x,int y){
    	return x*m+y-m;
    }
    

    中间使用函数初始化:

    void init(){
    	for(int i=1;i<=m;i++){
    		for(int j=1;j<=n;j++){
    			fa[convert(i,j)]=convert(i,j);
    		}
    	}
    }
    

    然后,我们就要处理并查集的结构了:

    int get(int x){
    	if(fa[x]==x){
    		return x;
    	}
    	fa[x]=get(fa[x]);
    	return fa[x];
    }
    void merge(int x,int y){
    	fa[get(x)]=get(y);
    }
    

    接下来,在main函数里写下:

    while(cin>>a>>b>>c>>d){
    		merge(convert(a,b),convert(c,d));
    }
    

    merge用来合并两个点,就变成了线。
    接下来处理行(m为行,n为列):

    for(int j=1;j<=n;j++){
    		for(int i=1;i+1<=m;i++){
    			if(get(convert(i,j))!=get(convert(i+1,j))){
    				merge(get(convert(i,j)),get(convert(i+1,j)));
    				ans++;
    			}
    		}
    	}
    

    这样,使行后面就合并了,如果他们不相等,就无法连接,于是就然他们是连接的。统计行的个数。
    接下来统计列:

    for(int i=1;i<=m;i++){
    		for(int j=1;j+1<=n;j++){
    			if(get(convert(i,j))!=get(convert(i,j+1))){
    				merge(get(convert(i,j)),get(convert(i,j+1)));
    				ans+=2;
    			}
    		}
    	}
    

    与行类似,但这里每次加两次,因为列上在数组里有2n次。
    注意,范围大,数组要超过1000000。
    实现代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=10000010;
    int m,n;
    long long a,b,c,d;
    long long fa[maxn];
    int convert(int x,int y){
    	return x*m+y-m;
    }
    void init(){
    	for(int i=1;i<=m;i++){
    		for(int j=1;j<=n;j++){
    			fa[convert(i,j)]=convert(i,j);
    		}
    	}
    }
    int get(int x){
    	if(fa[x]==x){
    		return x;
    	}
    	fa[x]=get(fa[x]);
    	return fa[x];
    }
    void merge(int x,int y){
    	fa[get(x)]=get(y);
    }
    int main(){
    	cin>>m>>n;
    	init();
    	long long ans=0;
    	while(cin>>a>>b>>c>>d){
    		merge(convert(a,b),convert(c,d));
    	}
    	for(int j=1;j<=n;j++){
    		for(int i=1;i+1<=m;i++){
    			if(get(convert(i,j))!=get(convert(i+1,j))){
    				merge(get(convert(i,j)),get(convert(i+1,j)));
    				ans++;
    			}
    		}
    	}
    	for(int i=1;i<=m;i++){
    		for(int j=1;j+1<=n;j++){
    			if(get(convert(i,j))!=get(convert(i,j+1))){
    				merge(get(convert(i,j)),get(convert(i,j+1)));
    				ans+=2;
    			}
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    

    作者:rebirth.death

    展开全文
  • UPC-连接格

    2020-03-17 11:29:13
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入 第一行输入个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经有连线。输...

    山再高,往上爬,总能登顶;
    路再长,走下去,定能到达。

    链接各点

    题目描述

    有一个M行N列的点阵,相邻两点可以相连。一条纵向的连线花费一个单位,一条横向的连线花费两个单位。某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。

    输入

    第一行输入两个正整数m和n。
    以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。

    输出

    输出使得连通所有点还需要的最小花费。

    Sample Input

    2 2
    1 1 2 1

    Sample Output

    3

    Hint

    30%数据:n*m<=1000
    100%数据:m,n<=1000

    题解分析
    首先用一张动态图描写思路
    在这里插入图片描述
    首先因为竖着连的价格最小,所以先竖着连如果这两个点不在一个树内,即根不相同那么就把这两个链接,如图所示。
    走完竖向之后走横向,就像图像所示,如果发现这两个的根是一个,那么就不连接,如果不是就连接。

    但是这个是二维的并查集怎么办呢,其实这和一维的没有区别,咱们只需要确定好坐标,有点哈希的意思 就可以了。
    咱们可以这样编号,以此图为例
    1 2 3 4 5
    6 7 8 9 10
    11 12 13 14 15
    16 17 18 19 20
    21 22 23 24 25
    是不是一下子就知道怎么肥4了
    好嘞,这样我们就可以AC了
    AC时间到

    PS注意不要数指针漂移也不要数组越界。
    数组至少开到1001*1001吧

    #include<unordered_map>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    #include<utility>
    #include<stdio.h>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<map>
    #pragma warning(disable:4244)
    #define PI 3.1415926536
    #pragma GCC optimize(2)
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const ll ll_inf = 9223372036854775807;
    const int int_inf = 2147483647;
    const short short_inf = 32767;
    const char char_inf = 127;
    inline ll read() {
        ll c = getchar(), Nig = 1, x = 0;
        while (!isdigit(c) && c != '-')c = getchar();
        if (c == '-')Nig = -1, c = getchar();
        while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
        return Nig * x;
    }
    inline void out(ll a)
    {
        if (a < 0)putchar('-'), a = -a;
        if (a >= 10)out(a / 10);
        putchar(a % 10 + '0');
    }
    ll qpow(ll x, ll n, ll mod) {
        ll res = 1;
        while (n > 0) {
            if (n & 1)res = (res * x) % mod;
            x = (x * x) % mod; n >>= 1;
        }
        return res;
    }
    #define read read()
    int fa[1010025];
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy)fa[fx] = fy;
    }
    int main()
    {
        for (int i = 1; i < 1010025; i++)fa[i] = i;
        int x = read, y = read;
        int x1, x2, y1, y2;
        int tot = 0;
        int num1, num2;
        while (scanf("%d%d%d%d", &x1, &y1, &x2, &y2) != EOF)
        {
            num1 = (x1 - 1) * y + y1;
            num2 = (x2 - 1) * y + y2;
            merge(num1, num2);
        }
        for (int j = 1; j <= y; j++)
            for (int i = 1; i < x; i++)
            {
                num1 = (i - 1) * y + j;
                num2 = num1 + y;
                if (find(num1) != find(num2))
                {
                    tot++;
                    merge(num1, num2);
                }
            }
        for (int i = 1; i <= x; i++)
            for (int j = 1; j < y; j++)
            {
                num1 = (i - 1) * y + j;
                num2 = num1 + 1;
                if (find(num1) != find(num2))
                {
                    tot += 2;
                    merge(num1, num2);
                }
            }
        cout << tot << endl;
    }
    

    By-轮月

    展开全文
  • 福大OJ 连接格

    2018-12-18 11:27:54
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 Input 第一行输入个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经有连线。...
  • Acwing1144. 连接格

    2020-09-21 18:59:02
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列点和第 x2 行第 y2 列点...
  • AcWing 1144 连接格

    2020-08-09 21:42:58
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数m和n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经...
  • 1144. 连接格题解

    2021-01-27 15:34:57
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列点和第 x2 行第 y2 列点...
  • 1394:连接格(grid)

    2020-04-27 11:38:13
    某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 【输入】 第一行输入个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点...
  • 连接格题解

    2017-09-01 16:19:15
    描述 ...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。  输入格式  第一行输入个正整数m和n。   以下若干行每行四个正整数x1,y1,x2,y2,表示
  • 问题 B: 连接格点(并查集) 题目描述 一个M行N列点阵,相邻两点可以相连。...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入 第一行输入两个正整数m和n。 以下...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。Input 第一行输入个正整数m和n,以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经有连线。输入...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列点和第 x2 行第 y2 列点...
  • Fzoj1616连接格

    2016-08-18 11:27:54
    Fzoj1616连接格点 ... 题目描述  一个M行N列点阵,相邻两点可以相连。...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通?   输入 第1行:输入两个正整数m和n。   以下若干行
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。输入格式第一行输入个正整数 mm 和 nn 。以下若干行每行四个正整数 x1,y1,x2,y2x1,y1,x2,y2 ,表示第 x1x1 行第 y1y1 列点和第 ...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。  输入格式  第一行输入个正整数m和n。   以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 【输入】 第一行输入个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入 第一行输入个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经有连线。...
  • 连接格 解题报告

    2015-08-11 16:53:52
    连接格点 时间限制: 1 Sec 内存限制: 128 MB ...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入  第一行输入个正整数m和n。(0   以下若干行每行四个正整数x1,y1,x
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 【输入】 第一行输入个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列点和第x2行第y2列点已经有连线。...
  • 连接格点(最小生成树) 时间: 1000ms / 空间: 65536KiB / Java类名: Main ...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数m和n。
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 分析:容我解释测试点 所以,既然求最小生成树,纵向优先。 那怎样连呢。 Kruskal 首先一...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。 输入格式 第一行输入个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列点和第 x2 行第 y2 列点...
  • 某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有点全部连通。      【输入格式】    第一行输入个正整数m和n。  以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1

空空如也

空空如也

1 2 3
收藏数 60
精华内容 24
关键字:

两点之间的连线有多少条