csp 2017 09-4 通信网络
程序员文章站
2022-05-12 12:03:43
...
题目如上,最简单的思路就是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算法,用矩阵的传递闭包来算的。算法原理如下:
参考链接: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直接暴力算法啥也不想就行。 推荐阅读