欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

csp 2017 09-4 通信网络

程序员文章站 2022-05-12 12:03:43
...

csp 2017 09-4 通信网络

csp 2017 09-4 通信网络

题目如上,最简单的思路就是dfs或者bfs,从每一点开始遍历图。设置一个标记矩阵,如果从i点出发可以达到点j,则标记matrix[i][j]和matrix[j][i]为1,表示i和j相互之间可知。

该思路正常通过。

代码如下:

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;

void clear(queue<int>& q) {
    queue<int> empty;
    swap(empty, q);
}

int main()
{
	int n,m;
	cin>>n>>m;
	vector<vector<int> > adj(n+1,vector<int>());
	vector<vector<bool> > matrix(n+1,vector<bool>(n+1,false));
	int a,b;
	for(int i=0;i<m;++i)
	{
		cin>>a>>b;
		adj[a].push_back(b);
	}
	vector<bool> visted;
	queue<int> q;
	for(int i=1;i<=n;++i)
	{
		clear(q);
		visted=vector<bool> (n+1,false);
		q.push(i);
		visted[i]=true;
		while(!q.empty())
		{
			int v=q.front();
			matrix[i][v]=true;
			matrix[v][i]=true;
			q.pop();
			visted[v]=true;
			int size=adj[v].size();
			for(int j=0;j<size;++j)
			{
				if(!visted[adj[v][j]])
				{
					q.push(adj[v][j]);
					visted[adj[v][j]]=true;
				}
				
			}
		}
		
	}
	int count=0;
	for(int i=1;i<=n;++i)
	{
		int sum=0;
		for(int j=1;j<=n;++j)
		{
			sum+=matrix[i][j];
		}
		if(sum==n)
			count++;
	}
	
	cout<<count;
	return 0;
} 

另一种思路:在实现上一种思路之前,想起了离散数学曾经教过一个Warshall算法,用矩阵的传递闭包来算的。算法原理如下:

csp 2017 09-4 通信网络

参考链接:https://blog.csdn.net/foreverzili/article/details/68481930

我的实现如下:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
void mutiply(vector<vector<int> > &mat1, vector<vector<int> >&mat2)
{
	vector<vector<int> > temp = mat1;
	int n = mat1.size();
	for (int i = 0; i<n; ++i)
	{
		for (int j = 0; j<n; ++j)
		{
			int sum = 0;
			for (int k = 0; k<n; ++k)
			{
				sum += mat1[i][k] * mat2[k][j];
			}
			if (sum>0) temp[i][j] = 1;
			else temp[i][j] = 0;
		}
	}
	mat1 = temp;
}
void add(vector<vector<int> > &mat1, vector<vector<int> >&mat2)
{
	int n = mat1.size();
	for (int i = 0; i<n; ++i)
	{
		for (int j = 0; j<n; ++j)
		{
			if (mat1[i][j] || mat2[i][j])
				mat2[i][j] = 1;
		}
	}
}
//void display(vector<vector<int> > &mat1)
//{
//	int n = mat1.size();
//	for (int i = 0; i<n; ++i)
//	{
//		for (int j = 0; j<n; ++j)
//		{
//			cout << mat1[i][j] << " ";
//		}
//		cout << endl;
//	}
//	cout << endl;
//}
int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> temp(n, 0);
	vector<vector<int> > matrix(n, temp);
	vector<vector<int> >addMatrix = matrix;


	int a, b;
	for (int i = 0; i<m; ++i)
	{
		cin >> a >> b;
		matrix[a - 1][b - 1] = 1;
	}
	vector<vector<int> >curMatrix = matrix;
	add(matrix, addMatrix);
	for (int i = 0; i<n - 1; ++i)
	{
		mutiply(curMatrix, matrix);
		//display(curMatrix);
		add(curMatrix, addMatrix);
	}
	int count = 0;

	
	for (int i = 0; i<n; ++i)
	{
		for (int j = 0; j<n; ++j)
		{
			if (addMatrix[i][j] == 1)
				addMatrix[j][i] = 1;
		}
	}
	for (int i = 0; i<n; ++i)
	{
		int sum = 0;
		for (int j = 0; j<n; ++j)
		{
			sum += addMatrix[i][j];
		}
		if (sum >= n - 1)
			count++;
	}
	cout << count;
	return 0;
}
但是因为是3重循环的原因,所以对大数据量的样例超时了,只能拿35分,果然csp直接暴力算法啥也不想就行。
相关标签: oj