图论题目集一（代码 注解）

news/2024/7/15 17:21:02 标签: 图论, 算法

目录

题目一： 

题目二：

题目三：

题目四：

题目五：

题目六：

题目七：

题目一： 

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int g[15][15], vis[15] = { 0 };
int n, m;
queue<int> q;
void dfs(int k)//深度
{
    cout << k << " ";
    vis[k] = 1;
    for (int i = 0; i < n; i++)
    {
        if (i == k)
            continue;
        if (vis[i] == 0 && g[k][i])
        {
            dfs(i);
        }
    }
    return;
}
void bfs(int k)//广度
{
    q.push(k);
    while (!q.empty())
    {
        k = q.front();
        q.pop();
        if(vis[k]==0)
        {
            cout<<k<<" ";
            vis[k]=1;
        }
        for (int i = 0; i < n; i++)
        {
            if (vis[i] == 0 && g[k][i] == 1)
            {
                q.push(i);
            }
        }
    }
    return;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)//构建邻接矩阵
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1, g[y][x] = 1;
    }
    for (int i = 0; i < n; i++)//深度
    {
        if (vis[i] == 0)
        {
            cout << "{ ";
            dfs(i);
            cout << "}" << endl;
        }
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)//广度
    {
        if(vis[i]==0)
        {
            cout << "{ ";
            bfs(i);
            cout << "}" << endl;
        }
    }
}

 题目二：

#include<iostream>
#include<algorithm>
using namespace std;
int g[10005][10005];
float n, k;
typedef struct node
{
	int data;
	int w = 0;
}node;
void warshall()//传递闭包
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				if (g[i][k] && g[k][j])//连通
				{
					if (i == j)
						continue;
					if (g[i][j] == 0 || g[i][j] > g[i][k] + g[k][j])//没有直接连通或者新通路距离小于之前通路
						g[i][j] = g[i][k] + g[k][j];
				}
			}
}
bool cmp(node a, node b)
{
	return a.w < b.w;
}
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			g[i][j] = 0;
	for (int i = 0; i < k; i++)//无向图，初始距离都为1
	{
		int v1, v2;
		cin >> v1 >> v2;
		g[v1][v2] = 1;
		g[v2][v1] = 1;
	}
	warshall();
	/*for (int i = 1; i <= n; i++)//输出邻接矩阵
	{
		for (int j = 1; j <= n; j++)
			cout << g[i][j] << " ";
		cout << endl;
	}*/
	float ans[10005] ;
	for (int i = 1; i <= n; i++)
	{
		ans[i] = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				ans[i]++;
			if (g[i][j]>0 && g[i][j] <= 6)//符合条件
				ans[i]++;
		}
	}
	for (int i = 1; i <= n; i++)
		printf("%d:% .2f%%\n", i, ans[i] / n * 100);
}

题目三：

#include<iostream>
using namespace std;
int g[1010][1010];
int n,m,s;
int vis[1010];
int path[1010];
int cnt=0;
void dfs(int k)//深度
{
    //cout<<k<<" ";
        path[cnt++]=k;//记录去的路径
    vis[k]=1;
    for(int i=0;i<=n;i++)
    {
        if(i==k)
            continue;
        if(vis[i]==0&&g[k][i]==1)
        {
            dfs(i);
            path[cnt++]=k;//记录回的路径
        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)//构建邻接矩阵
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }
    dfs(s);
    int flag=1;//标记是否可以遍历完所有
    for(int i=1;i<=n;i++)//查询是否遍历完所有
    {
        if(vis[i]==0)
        {
           flag=0;
            break;
        }
    }
    if(flag==1)//输出序列
    {
        for(int i=0;i<cnt;i++)
        {
            cout<<path[i];
            if(i!=cnt-1)
                cout<<" ";
        }
    }
    else
    {
        for(int i=0;i<cnt;i++)
            cout<<path[i]<<" ";
        cout<<0;
    }
}

题目四：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{
    ll v, w;
    bool operator <(const node& y) const//重载一个<,用于优先队列排序
    {
        return w > y.w;//小到大
    }
};
int n, m, t;
priority_queue<node>q;
vector<node> e[N];
ll dis[N], vis[N];
void Dij(int t)
{
    dis[t] = 0;//从t号点出发，表示从t到t距离为0
    q.push({ t,dis[t] });//t号点以及到t的距离入队
    while (q.size())
    {
        int u = q.top().v;//取最小边相连的点出队
        q.pop();
        if (vis[u])//访问过则跳过
            continue;
        vis[u] = 1;//没访问赋为访问
        for (auto i : e[u])//遍历以u为出发点的边
        {
            int v = i.v, w = i.w;//取其相连的点及权值
            if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
            {
                dis[v] = dis[u] + w;
                q.push({ v,dis[v] });//v点以及到v的距离
            }
        }
    }

}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, w=1;
        cin >> x >> y;
        e[x].push_back({ y,w });//存入以x出发到y，权值为w
        e[y].push_back({ x,w });//存入以x出发到y，权值为w
    }
    int N;
    cin >> N;
    while (N--)
    {
        cin >> t;
        float ans = 0,sum=0;
        memset(dis, 0x3f3f3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        Dij(t);//从t点出发
        for (int i = 1; i <= n; i++)
        {
            sum += dis[i];//求和
        }
        //cout << sum;
        ans = (n - 1) /sum;
        printf("Cc(%d)=%.2f\n", t, ans);
    }
}

题目五：

#include<iostream>//并查集
using namespace std;
int fa[204], mp[102][102];
int find(int x)//查找
{
    if(fa[x]==x)  return x;
    return fa[x]=find(fa[x]);
}
void Merge(int x, int y)//合并
{
    int a=find(x), b=find(y);
    if(a==b) return;
    else fa[a]=fa[b];
}
int main()
{
    int n, m, k;
    cin>>n>>m>>k;
    int a, b, c;
    for(int i=1;i<=n;i++)//初始化
        fa[i]=i;
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>c;
        mp[a][b]=c,mp[b][a]=c;
        if(c==1)//为朋友则合并，因为朋友的朋友也是朋友
            Merge(a, b);
    }
    for(int i=0; i<k; i++)
    {
        cin>>a>>b;
        if(mp[a][b]==1) cout<<"No problem"<<endl;
        else if(mp[a][b]==-1)//是敌对关系
        {
            if(find(a)==find(b))    cout<<"OK but..."<<endl;//但是有相同的朋友，即在一个集合内
            else cout<<"No way"<<endl;
        }
        else cout<<"OK"<<endl;
    }
    return 0;
}

题目六：

#include<iostream>
using namespace std;
int n, m, mp[520][520], f[520];
void init() //初始化
{
	for (int i = 0; i < n; i++)
		f[i] = i;
}
int find(int x) //查询
{
	if (x == f[x]) return x;
	return f[x] = find(f[x]);
}
void merge(int x, int y)//合并 
{
	int xx = find(x);
	int yy = find(y);
	if (xx != yy) f[xx] = yy;
	return;
}
int sum()//统计连通块个数
{
	int cnt = 0;
	for (int i = 0; i < n; i++) //统计连通块个数 
	{
		if (i == find(i)) cnt++;
	}
	return cnt;
}
int main() 
{
	int a, b, k, x, cnt = 0, cnt2, flag = 0;
	cin >> n >> m;
	init();
	while (m--) 
	{
		cin >> a >> b;
		mp[a][b] = 1;
		mp[b][a] = 1;
		merge(a, b);
	}
	cin >> k;
	cnt = sum();
	if (k == n) flag = 1; //要输出Game Over; 
	while (k--) 
	{
		cin >> x;
		init();
		cnt2 = 0;  //x去掉后的连通区域个数 
		for (int i = 0; i < n; i++) 
			mp[x][i] = mp[i][x] = 0;
		for (int i = 0; i < n; i++) 
		{
			for (int j = 0; j < n; j++)
			{
				if (mp[i][j]) merge(i, j);
			}
		}
		cnt2 = sum();
		if (cnt2 < cnt + 2) cout << "City " << x << " is lost." << endl;
		else cout << "Red Alert: City " << x << " is lost!" << endl;//1、去掉i点后，一个连通块至少被分为两个，增加了一个
		cnt = cnt2;                                                 //2、去掉i点后，再次统计cnt2时，就会把去掉的点i也加上，所以要大于cnt+1
		
	}
	if (flag) cout << "Game Over." << endl;
}

题目七：

#include<iostream>
#include<queue>
using namespace std;
int n, id, fa, ma, k;
int f[10100], peo[10100], avgs[10100], avga[10100],st[10100];
struct node
{
	int a, b;
}e[10100];
struct family
{
	int id, peo, avgs, avga;
	bool operator<(const family& x)const
	{
		if (x.peo * avga == peo * x.avga)//人均相等,则升序排序
			return id > x.id;
		return x.peo * avga < peo * x.avga;//人均多的在前
	}
};
int find(int x)//查找
{
	if (f[x] == x) return x;
	return f[x] = find(f[x]);
}
void meger(int x, int y)//合并
{
	x = find(x), y = find(y);
	if (x != y)
	{
		f[max(x, y)] = min(x, y);//小号id的设为父亲
		peo[min(x, y)] += peo[max(x, y)];//家庭人数加到小号id
		avgs[min(x, y)] += avgs[max(x, y)];//房屋数量加到小号id
		avga[min(x, y)] += avga[max(x, y)];//服务面积加到小号面积

	}
}
int main()
{
	for (int i = 0; i < 10100; i++) f[i] = i, peo[i] = 1;//初始化，每个父亲节点是自己，自己家庭都有一个自己
	cin >> n;
	int count = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> id >> fa >> ma >> k;
		if (fa != -1) e[count++] = { id,fa };//存关系
		if (ma != -1) e[count++] = { id,ma };//存关系
		st[id] = 1;//存在这个人
		int kid;
		for (int j = 1; j <= k; j++)
		{
			cin >> kid;
			e[count++] = { id,kid };//存关系
		}
		cin >> avgs[id] >> avga[id];
	}
	for (int i = 0; i < count; i++)//合并家庭
	{
		int a = e[i].a, b = e[i].b;
		st[a] = st[b] = 1;
		meger(a, b);//合并二者为一个家庭
	}
	priority_queue<family>ans;//优先队列
	for (int i = 0; i < 10100; i++)
	{
		if (st[i] && f[i] == i)//这个人存在且父亲节点是自己
			ans.push({ i,peo[i],avgs[i],avga[i] });
	}
	//count << st[8888] << f[8888];
	cout << ans.size() << endl;
	while (!ans.empty())
	{
		family t = ans.top();
		ans.pop();
		printf("%04d %d %.3lf %.3lf\n", t.id, t.peo, (double)t.avgs / t.peo, (double)t.avga / t.peo);
	}
}


http://www.niftyadmin.cn/n/5436926.html

相关文章

蓝桥杯-带分数

蓝桥杯-带分数

法一 /* 再每一个a里去找c,他们共用一个st数组,可以解决重复出现数字 通过ac确定b,b不能出现<0 b出现的数不能和ac重复*/import java.util.Scanner;public class Main {static int n,res;static boolean[] st new boolean[15];static boolean[] backup new boolean[15];…
阅读更多...
linux开机启动设置方法

linux开机启动设置方法

开机启动最简单的方法是在/etc/rc.local启动脚本中写入需要执行的命令。另一种方式是在/etc/init.d中编写一个启动脚本。但是这两种方式都不是正规的启动模式。init.d是Linux最早的服务管理方案&#xff0c;命令service start xxx就是去调用init.d中的启动脚本。之后init机制被…
阅读更多...
rust - 计算文件的md5和sha1值

rust - 计算文件的md5和sha1值

本文提供了一种计算文件md5和sha1的方法。 添加依赖 cargo add file-hashing cargo add md-5 cargo add sha1添加功能函数 use file_hashing::get_hash_file; use md5::Md5; use sha1::{Digest, Sha1}; use std::io::Error; use std::path::Path;pub fn md5<P: AsRef<…
阅读更多...
【MLLM+轻量多模态模型】24.02.Bunny-v1.0-2B-zh: 轻量级多模态语言模型 （效果一般）

【MLLM+轻量多模态模型】24.02.Bunny-v1.0-2B-zh: 轻量级多模态语言模型 （效果一般）

24.02 北京人工智能研究院&#xff08;BAAI&#xff09;提出以数据为中心的轻量级多模态模型 arxiv论文&#xff1a;2402.Efficient Multimodal Learning from Data-centric Perspective 代码&#xff1a;https://github.com/BAAI-DCAI/Bunny 在线运行&#xff1a;https://wis…
阅读更多...
铝壳电阻的工艺结构原理及选型参数总结

铝壳电阻的工艺结构原理及选型参数总结

🏡《总目录》 目录 1，概述2，工作原理3，结构特点4，工艺流程4.1，原材料准备4.2，点胶4.3，高温烘烤4.4，组合4.5，焊接4.6，表面处理4.7，电气性能测试5，选型参数5.1，阻值（Resis
阅读更多...
项目中遇到的sql问题记录

项目中遇到的sql问题记录

有一张表&#xff0c;表结构及数据如下&#xff1a; INSERT INTO test.test_approve(approve_no, tra_date, tablename, part_dt) VALUES (approve001, 2021-02-18 00:00:00, tableA, 2024-03-18); INSERT INTO test.test_approve(approve_no, tra_date, tablename, part_dt) …
阅读更多...
Re62：读论文 GPT-2 Language Models are Unsupervised Multitask Learners

Re62：读论文 GPT-2 Language Models are Unsupervised Multitask Learners

诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文全名&#xff1a;Language Models are Unsupervised Multitask Learners 论文下载地址&#xff1a;https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learner…
阅读更多...
upload-lab 11-20解法

upload-lab 11-20解法

pass11 查看代码 这里我们先解读下代码 $is_upload false; $msg null; if(isset($_POST[submit])){# 定义了白名单数组$ext_arr array(jpg,png,gif);# 截取上传文件名最后一个带点的文件后缀 $file_ext substr($_FILES[upload_file][name],strrpos($_FILES[upload_file][n…
阅读更多...
最新文章

Copyright @ 2022~2023