Gym - 100342J Triatrip (bitset求三元环个数)
2024-09-01 06:54:42
https://vjudge.net/problem/Gym-100342J
题意:
给出一个邻接矩阵有向图,求图中的三元环的个数。
思路:
利用bitset暴力求解,记得最后需要/3。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn=+; char s[maxn];
bitset<maxn> bit1[maxn],bit2[maxn]; int main()
{
//freopen("in.txt","r",stdin);
freopen("triatrip.in","r",stdin);
freopen("triatrip.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%s",s);
for(int j=;j<n;j++)
{
if(s[j]=='+') bit1[i].set(j),bit2[j].set(i);
//bit1记录i能够到达的点,bit2记录能够到达j的点
}
}
ll ans = ;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(bit1[i][j])
{
ans+=(bit1[j]&bit2[i]).count();
}
}
}
printf("%lld\n",ans/);
return ;
}
最新文章
- intel82599在centos6.5下编译安装
- 关于js中空值比较和传值的问题
- Ubuntu系统如何查看硬件配置信息
- Shifting List Item Values From One List To Another In Oracle Forms
- java基础回顾(二)——内部类
- [转载]我读过最好的Epoll模型讲解
- Codeforces Round #248 (Div. 2) C. Ryouko&#39;s Memory Note (vector 替换)
- PhpExcel数组输出到Excel浏览器下载
- Servlet课程0426(八)Servlet分页技术
- MySQL5.6监控表之INNODB_METRICS
- FileGeodatabase和PersonalGeodatabase与ArcSDEGeodatabase三种数据库比较.
- C++ 一些容易忽略的基本点
- Linux C编程一站式学习读书笔记——socket编程
- JS 监听微信、支付宝等移动app及浏览器的返回、后退、上一页按钮的事件方法
- 《PHP制作个人博客》之四:分类添加及前端导航数据用php动态调取
- RESTful协议
- 执行shell文件是,提示chmod: 更改&#39;./shell1.sh&#39; 的权限: 不允许的操作。
- 家庭记账本之微信小程序(四)
- Java链式方法
- Servlet3.0 multipart 文件上传技术