题意

  • 给定一个有向图,求出图中所有长度在 [3,7][3,7] 之间的简单环。
  • 输入:格式为 [IDu,IDv,(Unused)][ID_u,ID_v,(Unused)] 的边表, $ ID \leq 2^{31} $ , $ E \leq 280000 $ , 结点平均度数小于 1010 。环中同一个 IDID 不可以重复出现(若大环包括小环,则需要分开统计),环的个数 $ \leq 3 \times 10^7 $ 。
  • 输出:按照环长度与环的数字字典序输出所有环。

朴素 & 优化

用 DFS 直接找环。

通过观察不难发现,在比较稠密的图上,长度为 NN 的环的数量相比长度为 N1N-1 的环的数量是指数增长的(和结点的平均度数有关)。
如果能通过只搜索到第 6 层,而非第 7 层就得到所有的解,就能够将运行的时间有效的缩减到原先的1/6左右。
我们定义如下的数据结构: vector<unordered_map<int,vector<int>>> P2;
使用 P2[i][j][k] 来表示结点 ii 到达结点 jj ,中间经过结点 kk 的路径详情,如果 kk 不在我们已经搜索过的结点列表中,并且 jj 是起点,那么 ikji-k-j 就是符合要求的路径的一部分。
具体来说,就是提前做深度为 2 的搜索(保存最后一层结点的入边),在第 6 层时直接根据现有结果进行判断,不进入第 7 层。

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <stdlib.h>
#define DEBUG
const int MAXN=(560000+5);
const int MAXE=(280000+5);
typedef unsigned int uInt32;

struct Path{
	int length;
	std::vector<uInt32> path;
	Path(int length, const std::vector<uInt32> &path) : length(length), path(path) {}
	bool operator<(const Path&rhs)const{
		if(length!=rhs.length) return length<rhs.length;
		for(int i=0;i<length;i++) if(path[i]!=rhs.path[i]) return path[i]<rhs.path[i];
	}
};

std::vector <uInt32> I;
std::vector <uInt32> _T; // ID -> Account
std::unordered_map<uInt32,int> Id; // Account -> ID
std::vector <Path> ans;
int tot=0,nodeCnt;
int h[MAXN],edge[MAXE],nxt[MAXE],inDegrees[MAXN];
void addEdge(int u,int v){edge[++tot]=v,nxt[tot]=h[u],h[u]=tot;}

bool vis[MAXN];
void dfs(int head,int now,int depth,std::vector<int> &path){
	vis[now]=true;
	path.push_back(now);
	for(int e=h[now];e!=-1;e=nxt[e]){
		register int v=edge[e];
		if(v==head && depth>=3 && depth<=7){
			std::vector<uInt32> tmp;
			for(std::vector<int>::iterator it=path.begin();it!=path.end();++it) tmp.push_back(_T[*it]);
			ans.emplace_back(Path(depth,tmp));
		}
		if(depth<7 && !vis[v] && v>head) dfs(head,v,depth+1,path);
	}
	vis[now]=false;
	path.pop_back();
}

inline uInt32 ReaduInt(char **p){
	        register uInt32 ret=0;
		char c;
		while((**p)>'9'||(**p)<'0') ++(*p);
		while((**p)>='0'&&(**p)<='9'){
			ret=ret*10+(**p)-'0';
			++(*p);
		}
		return ret;
}

int main(){
	/* 使用 POSIX open() 和 mmap() 读入 */
	int in=open("test_data.txt",O_RDONLY);	
	char *addr= (char *) mmap(NULL,lseek(in,0,SEEK_END),PROT_READ,MAP_PRIVATE,in,0);
	#ifdef DEBUG
		printf("Open Success\n");
	#endif
	register uInt32 u,v,c;
	while(true){
		while((*addr)=='\n'||(*addr)==' '||(*addr)=='\r') ++addr;
		if((*addr)!=EOF&&(*addr)!='\0') u=ReaduInt(&addr),v=ReaduInt(&addr),c=ReaduInt(&addr);
		else break;
		I.push_back(u);
		I.push_back(v);
	}
	#ifdef DEBUG
		printf("READ OK\n");
	#endif
	
	/* 节点的离散化 */
	_T.assign(I.begin(),I.end());
	std::sort(_T.begin(),_T.end());
	_T.erase(std::unique(_T.begin(),_T.end()),_T.end());
	nodeCnt=0;
	for(std::vector<uInt32>::iterator it=_T.begin();it!=_T.end();++it) Id[*it]=nodeCnt++;
	int InputSize=I.size();
	#ifdef DEBUG
		printf("Relabel OK\n");
	#endif
	
	/* 建图 */
	memset(edge,0,sizeof(edge));
	for(int i=0;i<MAXN;++i) h[i]=-1;
	for(int i=0;i<MAXE;++i) nxt[i]=-1;
	for(int i=0;i<InputSize;i+=2){
		register int u=Id[I[i]],v=Id[I[i+1]];
		addEdge(u,v);
		++inDegrees[v];}
	#ifdef DEBUG
		printf("Construct Graph OK\n");
	#endif
	
	/* 搜索 */
	std::vector<int> __path;
	for(int i=0;i<nodeCnt;i++) if(h[i]!=-1) dfs(i,i,1,__path);
	
	/* 输出答案 */
	std::sort(ans.begin(),ans.end());
	printf("%u\n",ans.size());
	for(std::vector<Path>::iterator it=ans.begin();it!=ans.end();++it){
		printf("%d",it->path[0]);
		for(int i=1;i<it->length;i++) printf(",%d",it->path[i]);
	       	putchar('\n');
	}
	return 0;
}

乱搞

做深度为 $ 1 \leq Depth \leq 4 $ 的搜索,这时可以统计小于 44 的环,对于 $ \ge 4 $ 的环,可以直接拼接。
问题:如何避免非简单环的情况,即考虑 4 与 4 的链是否有交点。直接判断?(常数*16)
问题:如何由长度为 depthdepth 的链拓展出 depth+1depth+1 的链?长度为 33 的由长度为 22 的与长度为 11 的拼接,长度为 44 的由长度为 22 的与长度为 22 的拼接。
问题:如何合理存储链? struct link{uint account[7],head,tail;}; ,从小到大存储+归并?
Hash 考虑用 BKDRHash + hash_combine

Hi1620 (Kunpeng 920) 性能参数

  • 64 Cores 64 Threads
  • L1: 64KB L2: 512KB * 64C L3: 1MB * 64C
  • DDR4-3200
  • 强内存模型,单核较弱

比赛环境

  • 选手使用的练习资源:2U4G (2C2T L1 2KB L2 1MB L3 2MB)
  • 判题系统使用的判题资源:4U16G (4C4T L1 4KB L2 2MB L3 4MB)
  • EulerOS based on CentOS
  • 可以预计到虚拟化带来性能损失

参考文献

  1. 华为软件精英挑战赛-2020-初赛-题目分析/算法Baseline (求出有向图中所有的环)