1107 并查集:求簇的个数以及每个簇的元素个数

 

原题:https://www.patest.cn/contests/pat-a-practise/1107

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
const int maxn = 1000;
int isroot[maxn], father[maxn];
vector<int> hoby[maxn];
set<int, greater<int>> st;

int findfather(int a) //找根节点
{
    int x = a;
    while (a != father[a]) //因为初始化自己的父节点为自己,所以遍历到自己
    {
        a = father[a];
    }
    while (x != father[x]) //(可以省略)压缩路径:把所有节点的father都改为根节点a
    {
        int z = x;
        x = father[x];
        father[z] = a; //将结点的父亲都改为a;
    }
    return a;
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i; //初始化每个人的父节点为自己
        isroot[i] = 0; //每个簇的元素个数
    }
}

void _union(int a, int b) {
    int faa = findfather(a);
    int fab = findfather(b);
    if (faa != fab)
        father[faa] = father[fab];
}

int main() {
    int n, num, temp;
    cin >> n;
    init(n);
    for (int i = 0; i < n; i++) {
        scanf("%d:", &num);
        for (int j = 0; j < num; j++) {
            cin >> temp;
            hoby[i].push_back(temp);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < hoby[i].size(); k++) {
                if (find(hoby[j].begin(), hoby[j].end(), hoby[i][k])
                    != hoby[j].end()) {
                    _union(i, j);
                    break;
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
        isroot[findfather(i)]++; //相同根节点即为一簇,那么该蔟的数目++
    int ans = 0; //统计簇的数目
    for (int i = 0; i < n; i++) {
        if (isroot[i] != 0) //等于0表示不是根节点
            ans++;
    }
    cout << ans << endl;
    sort(isroot, isroot + n, greater<int>());
    for (int i = 0; i < ans; i++) {
        cout << isroot[i];
        if (i < ans - 1)
            cout << " ";
    }
    cout << endl;
    return 0;
}

 

 

0

1087. Dijkstra + DFS:解决四标尺

其中:第四标尺路径条数也可用num[]数组,放在Dijkstra中

#include<string>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int maxn = 200, INF = 1000000000;
int n, m, nump = 0, optvalue = 0, vis[maxn], g[maxn][maxn], d[maxn], w[maxn],
		weight[maxn], num = 0; //编号从0开始
double ave = 0;
map<int, string> int2string;
map<string, int> string2int;
vector<int> pre[maxn], path, temppath;
string start;
void dijkstra(int v) //第一标尺
		{
	int min, u;
	fill(d, d + maxn, INF);
//fill(num,num+maxn,0);
	d[v] = 0;
//num[v]=1;
	for (int i = 0; i < n; i++) {
		min = INF;
		for (int j = 0; j < n; j++) {
			if (vis[j] == 0 && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int k = 0; k < n; k++) {
			if (vis[k] == 0) {
				if (d[k] > d[u] + g[u][k]) {
					d[k] = d[u] + g[u][k];
					pre[k].clear();
					pre[k].push_back(u);
// num[k]=num[u];
				} else if (d[k] == d[u] + g[u][k]) {
					pre[k].push_back(u);
//num[k]+=num[u];
				}
			}
		}
	}
}
void dfs(int st, int ed) {
	if (ed == st) {
		num++; //第四标尺
		temppath.push_back(ed);
		int value = 0;
		for (int i = temppath.size() - 1; i >= 0; i--) {
			int id = temppath[i];
			value += weight[id];
		}
		if (value > optvalue) //第二标尺
				{
			optvalue = value;
			path = temppath;
			ave = value * 1.0 / (temppath.size() - 1);
		} else if (value == optvalue
				&& value * 1.0 / (temppath.size() - 1) > ave) //第三标尺
						{
			ave = value * 1.0 / (temppath.size() - 1);
			path = temppath;
		}
		temppath.pop_back();
		return;
	}
	temppath.push_back(ed);
	for (int i = 0; i < pre[ed].size(); i++)
		dfs(st, pre[ed][i]);
	temppath.pop_back();
}
int change(string str) {
	if (string2int.find(str) != string2int.end())
		return string2int[str];
	else {
		string2int[str] = nump;
		int2string[nump] = str;
		return nump++;
	}
}
int main() {
	cin >> n >> m >> start;
	string str, strr;
	string end = "ROM";
	fill(g[0], g[0] + maxn * maxn, INF);
	int st = change(start);
	int ed = change(end);
	weight[st] = 0;
	for (int i = 0; i < n - 1; i++) {
		cin >> str;
		int id = change(str);
		cin >> weight[id];
	}
	for (int i = 0; i < m; i++) {
		cin >> str >> strr;
		int id1 = change(str);
		int id2 = change(strr);
		cin >> g[id1][id2];
		g[id2][id1] = g[id1][id2];
	}
	dijkstra(st);
	dfs(st, ed);
	cout << num << " " << d[ed] << " " << optvalue << " " << int(ave) << endl;
	for (int i = path.size() - 1; i >= 0; i--) {
		cout << int2string[path[i]];
		if (i > 0)
			cout << "->";
	}
	return 0;
}

 

0

1072. Gas Station (30)-PAT甲级真题(Dijkstra)

 

原题:https://www.patest.cn/contests/pat-a-practise/1072

每次遍历d[],求所有最短路径中最小的;

#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
const int maxn = 1011, INF = 1000000000;
int n, m, k, ds, g[maxn][maxn], d[maxn], vis[maxn];

int string2int(string str) {
	stringstream ss;
	int a;
	ss << str;
	ss >> a;
	return a;
}
int dijkstra(int v, int &minds, int &add) {
	int min, u;
	fill(vis, vis + maxn, 0);
	fill(d, d + maxn, INF);
	d[v] = 0;
	for (int i = 0; i < n + m; i++) {
		min = INF;
		for (int j = 1; j <= n + m; j++) {
			if (vis[j] == 0 && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int k = 1; k <= n + m; k++) {
			if (vis[k] == 0 && d[k] > d[u] + g[u][k])
				d[k] = d[u] + g[u][k];
		}
	}
for(int i=1;i<=n;i++)/*遍历d[],不能在求d[]的过程中遍历,只能全部求完d[]之后
 {
 if(d[i]>ds)
 return 1;
 add+=d[i];
 if(minds>d[i])
 minds=d[i];
 }
 return -1;
 }
 int main()
 {
 int id1,id2;
 int ansid,ansds=0,ansadd=INF,minds,add;
 cin>>n>>m>>k>>ds;
 fill(g[0],g[0]+maxn*maxn,INF);
 string a,b;
 for(int i=0;i<k;i++)
 {
 cin>>a>>b;
 if(a[0]=='G')
 id1=n+string2int(a.substr(1));
 else
 id1=string2int(a);
 if(b[0]=='G')
 id2=n+string2int(b.substr(1,b.size()-1));
 else
 id2=string2int(b);
 cin>>g[id1][id2];
 g[id2][id1]=g[id1][id2];
 }
 for(int i=1;i<=m;i++)
 {
 minds=INF;
 add=0;
 if(dijkstra(n+i,minds,add)>0)
 continue;
 if(minds>ansds)
 {
 ansds=minds;
 ansid=n+i;
 ansadd=add;
 }
 else if(minds==ansds&&add<ansadd)
 {
 ansid=n+i;
 ansadd=add;
 }
 }
 if(ansadd==INF)
 cout<<"No Solution"<<endl;
 else
 {
 cout<<"G"<<ansid-n<<endl;
 printf("%0.1f %0.1f\n",ansds*1.0,ansadd*1.0/n);
 }
 return 0;
 }

 

0

1066. Root of AVL Tree (25)-PAT甲级真题(AVL树)左旋右旋四种类型

原题:https://www.patest.cn/contests/pat-a-practise/1066

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
	int v, height;
	node *lchild, *rchild;
};
int getheight(node *root) //获取高度
		{
	if (root == NULL)
		return 0;
	return root->height;
}
int getbalance(node *root) //获取平衡因子
		{
	return getheight(root->lchild) - getheight(root->rchild);
}
void L(node *&root) //左旋
		{
	node *temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	temp->height = max(getheight(temp->lchild), getheight(temp->rchild)) + 1;
	root = temp;
}
void R(node *&root) //右旋
		{
	node *temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	temp->height = max(getheight(temp->lchild), getheight(temp->rchild)) + 1;
	root = temp;
}
void insert(node *&root, int x) //建树并且调整
		{
	if (root == NULL) {
		root = new node;
		root->v = x;
		root->height = 1;
		root->lchild = root->rchild = NULL;
		return;
	}
	if (x < root->v) {
		insert(root->lchild, x);
		root->height = max(getheight(root->lchild), getheight(root->rchild))
				+ 1;
		if (getbalance(root) == 2) {
			if (getbalance(root->lchild) == 1) //LL型
				R(root);
			else if (getbalance(root->lchild) == -1) //LR型
					{
				L(root->lchild);
				R(root);
			}
		}
	} else {
		insert(root->rchild, x);
		root->height = max(getheight(root->lchild), getheight(root->rchild))
				+ 1;
		if (getbalance(root) == -2) {
			if (getbalance(root->rchild) == -1) //RR型
				L(root);
			else if (getbalance(root->rchild) == 1) //RL型
					{
				R(root->rchild);
				L(root);
			}
		}
	}
}
int main() {
	int n, x;
	node *root = NULL;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		insert(root, x);
	}
	cout << root->v << endl;
	return 0;
}

 

0

1053. Path of Equal Weight (30)-PAT甲级真题(普通树的遍历,保存dfs路径)

原题:https://www.patest.cn/contests/pat-a-practise/1053

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int n, m, s, path[maxn];
struct node {
	int weight; //点权
	vector<int> child; //每个(此题为非叶子)节点的孩子
} Node[maxn];
bool cmp(int a, int b) //注意类型int
		{
	return Node[a].weight > Node[b].weight; //按孩子结点的weeight从大到小排序
}
void dfs(int index, int numnode, int sum) //当前节点,路径节点个数,总权值
		{
	cout << "*" << index << "*" << endl;
	if (sum > s)
		return;
	if (sum == s) {
		if (Node[index].child.size() != 0) //还没到叶子结点
			return;
		for (int i = 0; i < numnode; i++) //到达叶子结点,进行输出
				{
			cout << Node[path[i]].weight;
			if (i < numnode - 1)
				cout << " ";
			else
				cout << endl;
		}
		return;
	}
	for (int i = 0; i < Node[index].child.size(); i++) //枚举所有子结点//不同于原版dfs { int child=Node[index].child[i]; path[numnode]=child;//将结点child加入path dfs(child,numnode+1,sum+Node[child].weight);//递归进入下一层 } } int main() { cin>>n>>m>>s;
		for (int i = 0; i < n; i++) {
			cin >> Node[i].weight;
		}
	int id, k, child;
	for (int i = 0; i < m; i++) {
		cin >> id >> k;
		for (int j = 0; j < k; j++) {
			cin >> child;
			Node[id].child.push_back(child);
		}
		sort(Node[id].child.begin(), Node[id].child.end(), cmp);
	}
	path[0] = 0; //路径的第一个结点设置为0号结点
	dfs(0, 1, Node[0].weight);
	return 0;
}

 

0