分类 默认分类 下的文章

题意

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

朴素 & 优化

用 DFS 直接找环。

通过观察不难发现,在比较稠密的图上,长度为 $N$ 的环的数量相比长度为 $N-1$ 的环的数量是指数增长的(和结点的平均度数有关)。
如果能通过只搜索到第 6 层,而非第 7 层就得到所有的解,就能够将运行的时间有效的缩减到原先的1/6左右。
我们定义如下的数据结构: vector<unordered_map<int,vector<int>>> P2;
使用 P2[i][j][k] 来表示结点 $i$ 到达结点 $j$ ,中间经过结点 $k$ 的路径详情,如果 $k$ 不在我们已经搜索过的结点列表中,并且 $j$ 是起点,那么 $i-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 $ 的搜索,这时可以统计小于 $4$ 的环,对于 $ \ge 4 $ 的环,可以直接拼接。
问题:如何避免非简单环的情况,即考虑 4 与 4 的链是否有交点。直接判断?(常数*16)
问题:如何由长度为 $depth$ 的链拓展出 $depth+1$ 的链?长度为 $3$ 的由长度为 $2$ 的与长度为 $1$ 的拼接,长度为 $4$ 的由长度为 $2$ 的与长度为 $2$ 的拼接。
问题:如何合理存储链? 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 (求出有向图中所有的环)