解题报告——简单路径
题目描述
给定一个nn个点的无向图，求这个图中有多少条长度为4的简单路径。
n≤1500
输入
第一行一个数n
接下来n行每行n个0或1
第i行第j列是1表示i与j联通
输出
输出简单路径的个数
样例输入
5
00011
00000
00010
10100
10000
样例输出
2
提示
n<=1500
这道题目的朴素算法可以直接想到—枚举图中的4个点，判断是否构成一条简单路径，时间复杂度O（n^4）
那么必然要进行优化
如何优化呢？
我们枚举每一条边，统计连向该边左右两端的节点
如图所示
由乘法原理可得，简单路径的数量为n*m
同时我们不能忽略环的存在，所以还要减去环的数量
所以ans=ans+（节点u的入度-1）*（节点v的入读-1）-三元环的数量{注意本身枚举的那一条边}
此时时间复杂度为O（n^3）
似乎还是A不了诶
此时我们把目光放在了寻找三元环的n上
怎么才能将这个n降下来呢
嗯.......压位！！！
对于每个节点i，我们用f[i]数组来表示它的连接情况
其中里面所存放的是一个二进制数
数中的第k位表示的是点i是否与点k相连
我们发现n<=1500，那么就有1500个二进制位要存储
所以我们再加一维放入50个longint（c++是int 32位）
那么处理三元环就直接变成了n/30（对于f数组我们进行预处理）
时间复杂度就变成了（n^3/30）
n<=1500这个时间复杂度是可以接受的
接下来是代码
var
n,i,j,k,t,l,dd:longint;
ans,sum:int64;
f:array[1..3000,1..100] of longint;
a:array[1..1600,1..1600] of char;
GGG:array[0..1 shl 16] of longint;
u,v:array[1..1500*1500] of longint;
s:array[1..2000] of longint;
function find(q:longint):longint; //对于一个二进制数求解里面有几个1
var left,right:longint;
begin
left:=q shr 15; right:=q-left shl 15;//因为这个二进制数是30位的，而我们的表只有15位，那么就把这个数掰开
exit(GGG[left]+GGG[right]);
end;
procedure GG; //打表处理出2~2^16中所有二进制数中的1的数量
begin
for i:=2 to 1 shl 16 do
begin
GGG[i]:=GGG[i div 2]+i mod 2; //递推求解不解释
end;
end;
begin
readln(n);
GGG[1]:=1; //GGG[i]表示i的二进制中有几个一
GG;
for i:=1 to n do
begin
for j:=1 to n do
begin
read(a[i,j]);
if (a[i,j]='1') and (i<>j) then
begin
inc(l);
u[l]:=i;
v[l]:=j; //记录边两端的点
inc(s[i]);//记录入度
end;
end;
readln;
end;
for i:=1 to n do
begin
for j:=1 to n do
begin
t:=j div 30+1;
if a[i,j]='1' then f[i][t]:=f[i][t]+(1 shl (j-(t-1)*30+1));
end;
end; //构建f数组
for k:=1 to l do
begin
sum:=(s[u[k]]-1)*(s[v[k]]-1);
for i:=1 to n div 30+1 do
begin
dd:=0;
dd:=find(f[v[k]][i] and f[u[k]][i]); //and后二进制位上就直接保留了相同的点
sum:=sum-dd;
end;
ans:=ans+sum;
end;
writeln(ans);
end.