?Problem J. Triatrip

Time Limit: 20 Sec

Memory Limit: 256 MB

題目連接

http://codeforces.com/gym/100342/attachments

Description

The travel agency “Four Russians” is offering the new service for their clients. Unlike other agencies that only suggest one-way or roundtrip for airline tickets to their customers, “Four Russians” offers the brand new idea — triatrip. Triatrip traveler starts in some city A, flies to some city B, then flies to some city C, and returns to the city A.
Now the managers of the agency started to wonder, how many different triatrips they can offer to their customers. Given a map of all possible flights, help them to find that out.

Input

The first line of the input file contains two integer numbers n — the number of cities that are served by airlines that agree to sell their tickets via the agency (3 ≤ n ≤ 1500). The following n lines contain a sequence of n characters each — the j-th character of the i-th line is ‘+’ if it is possible to fly from the i-th city to the j-th one, and ‘-’ if it is not. The i-th character of the i-th line is ‘-’.

Output

Output one integer number — the number of triatrips that the agency can offer to its customers.

Sample Input

4
--+-
+--+
-+--
--+-

Sample Output

2

HINT

?

題意

? ? ? 給出鄰接矩陣，有向圖，找出三元環的個數

題解：

? ? bitset 暴力枚舉一條邊，出度入度的集合用到bitset

代碼：

1 //作者:1085422276 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <ctime> 6 #include <iostream> 7 #include <algorithm> 8 #include <set> 9 #include <vector> 10 #include <sstream> 11 #include <queue> 12 #include <typeinfo> 13 #include <fstream> 14 #include<bits/stdc++.h> 15 #include <map> 16 #include <stack> 17 typedef long long ll; 18 using namespace std; 19 const int inf = 10000000; 20 inline ll read() 21 { 22 ll x=0,f=1; 23 char ch=getchar(); 24 while(ch<'0'||ch>'9') 25 { 26 if(ch=='-')f=-1; 27 ch=getchar(); 28 } 29 while(ch>='0'&&ch<='9') 30 { 31 x=x*10+ch-'0'; 32 ch=getchar(); 33 } 34 return x*f; 35 } 36 ll exgcd(ll a,ll b,ll &x,ll &y) 37 { 38 ll temp,p; 39 if(b==0){ 40 x=1;y=0; 41 return a; 42 } 43 p=exgcd(b,a%b,x,y); 44 temp=x;x=y;y=temp-(a/b)*y; 45 return p; 46 } 47 //******************************* 48 #define N 1510 49 bitset<N> in[N],out[N],he; 50 char mp[1501][1501]; 51 int main() 52 { 53 54 freopen("triatrip.in","r",stdin); 55 freopen("triatrip.out","w",stdout); 56 int n; 57 n=read(); 58 for(int i=1;i<=n;i++) 59 scanf("%s",mp[i]); 60 for(int i=1;i<=n;i++) 61 { 62 for(int j=1;j<=n;j++) 63 { 64 if(i==j)continue; 65 if(mp[i][j-1]=='+') 66 { 67 in[i][j]=true; 68 out[j][i]=true; 69 } 70 } 71 } 72 ll ans=0; 73 for(int i=1;i<=n;i++) 74 { 75 for(int j=1;j<=n;j++) 76 { 77 if(i==j)continue; 78 if(mp[i][j-1]=='+') 79 he=(in[j])&(out[i]),ans+=he.count(); 80 } 81 } 82 cout<<ans/3<<endl; 83 return 0; 84 }

?

轉載于:https://www.cnblogs.com/zxhl/p/4710171.html

總結

以上是生活随笔為你收集整理的Codeforces Gym 100342J Problem J. Triatrip 求三元环的数量 bitset的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。