POJ 1962-Corporative Network

红太狼 2022-08-11 00:49 26阅读 0赞

题意：

一家大公司有多个子公司，原来每个公司都有自己的运算中心，为了提升服务质量，公司决定把一些公司的运算中心合并；

1.输入I ——I   J  代表把集合A的运算中心连接到集合B的一家公司，J不一定为集合B的运算中心，I到J 的距离为（I-J）%1000。

2.输入E-----I   问公司I到其运算中心的距离。

N不超过20000，其中询问次数不超过N，输入的数字最大不超过200000，输入O表示结束。

思路：

因为题意中明显有集合相关的信息，故而想到并查集，因牵扯到距离故考虑并查集加权......结果如下：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #define N 20005
    int f[N],rank[N],n;
    using namespace std;
    
    void initial()
    {
    	for(int i=0;i<=n;i++)
    	{
    		f[i]=i;rank[i]=0;
    	}
    } 
    int  find (int x)
    {
    
    	if(x==f[x])return x;
    	int r=f[x];
    	r=find(r);
    	rank[x]+=rank[f[x]];
    	return f[x]=r;
    }
    void Union(int x,int y)
    {
    		f[x]=y;
    		rank[x]=abs(y-x)%1000;
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d",&n);
    		initial();
    		char comm;
    		int x,y;
    		
    		while(scanf(" %c",&comm)&&comm!='O')
       		{
    			if(comm=='E')
    			{
    				scanf("%d",&x);
    				find(x);
    				printf("%d\n",rank[x]);
    			}
    			else if(comm=='I')
    			{
    				scanf("%d%d",&x,&y);
    				Union(x,y);
    			}
    		}
    	}
    	return 0; 
    }

其实abs可自己手写，可能更快些。赋值为0的语句可用memset，耗时小于O(n).

发表评论取消回复

表情：

评论列表（有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj 2531 -- Network Saboteur

Network Saboteur <table> <tbody> <tr> <td><strong>Time Limit:</strong> 20

心已赠人/ 2022年10月02日 14:57/ 0 赞/ 110 阅读

相关 POJ 1962-Corporative Network

题意：一家大公司有多个子公司，原来每个公司都有自己的运算中心，为了提升服务质量，公司决定把一些公司的运算中心合并； 1.输入I ——I J 代表把集合

红太狼/ 2022年08月11日 00:49/ 0 赞/ 27 阅读

相关 Corporative Network LA3027

include <stdio.h> include <string.h> include <algorithm> include <math.h

我不是女神ヾ/ 2022年08月07日 05:42/ 0 赞/ 107 阅读

相关 UVA 1329——Corporative Network

题意：有n个节点，然后执行I u，v（把u的父节点设为v）和E u（询问u到根节点的距离）。思路：并查集。加了信息的并查集，在路径压缩的同时维护距离d\[i

╰半橙微兮°/ 2022年07月29日 10:53/ 0 赞/ 115 阅读

相关 POJ - 1287 - Networking

-------------------- 题目连接：[http://poj.org/problem?id=1287][http_poj.org_problem_id_1287

青旅半醒/ 2022年06月10日 00:09/ 0 赞/ 227 阅读

相关 poj--1287--Networking

<table style="background-image:url("http://poj.org/images/table_back.jpg");fon

Dear 丶/ 2022年05月29日 01:55/ 0 赞/ 230 阅读

相关 POJ3694 Network

题目描述 A network administrator manages a large network. The network consists of N comp

向右看齐/ 2021年12月24日 16:27/ 0 赞/ 303 阅读

相关 POJ 2531, Network Saboteur

Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 3311 Accepted: 1346 Des

傷城~/ 2021年12月22日 06:43/ 0 赞/ 252 阅读

相关 LA3027:Corporative Network 合作网络 (并查集)

题意：有n个节点，有两个操作，I x y：把x作为y的子节点连上，他们的距离为abs(x-y)%1000；E x:查询x到根节点的距离。思路：加权并查集，其实这题就是

左手的ㄟ右手/ 2021年12月11日 12:51/ 0 赞/ 275 阅读

相关 POJ 1287 Networking

题目链接：[https://vjudge.net/problem/POJ-1287][https_vjudge.net_problem_POJ-1287] 题目大意

末蓝、/ 2021年10月18日 07:36/ 0 赞/ 325 阅读