ZJUT2022入门题单Week5 程序简注
|
505
|
0
|
解题日志

2212 字
|
39 分钟

练后总结

A-E 最短路
F-I 最小生成树
J 最近公共祖先（LCA）
K 传递闭包
L 拓扑排序
M 欧拉回路

感谢学长不卡之恩，可能是做的比较舒服的一张题单，只需要看知识点，几乎没对具体题目看过题解，除非卡在了莫名其妙的地方。（洛谷树题单直接暴毙（雾）
因为学长的目的似乎是为了让我们初步认识图论题和图论题的做题逻辑，所以个人感觉题目最难的部分是读题和建模，但难度其实也还好，属于是告诉你用什么算法然后直接套的难度，变形不多。算法本身不算难，所以就不细写了，把精力重点留给数论和数学分析（

A – Stockbroker Grapevine

按照谣言传递链建有向图，由于数据范围不大且需要将所有人都判断一遍才能确定，用FLOYD最短路。

namespace lovelive{
    int f[105][105],ans;
    int n,m,to,va,tmp,ansi;
    bool main(){
        memset(f,-1,sizeof(f));
        cin>>n;ans = 114514;ansi = -1;
        if(n==0)return false;
        for(int i=1;i<=n;i++){
            f[i][i] = 0;
            cin>>m;
            for(int j=1;j<=m;j++){
                cin>>to>>va;
                if(f[i][to]!=-1){
                    f[i][to] = min(f[i][to],va);
                }else{
                    f[i][to] = va;
                }
            }
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(f[i][k]!=-1&&f[k][j]!=-1){
                        if(f[i][j] == -1)f[i][j] = 114514;
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            tmp = -1;
            for(int j=1;j<=n;j++){
                tmp = max(tmp,f[i][j]);
                if(f[i][j]==-1) {tmp = -1;break;}
            }
            if(tmp != -1 and tmp < ans){
                ans = tmp;
                ansi = i;
            }
        }
        if(ansi == -1){
            cout<<"disjoint"<<endl;
        }else{
            cout<<ansi<<" "<<ans<<endl;
        }
        return true;
    }
}

B – 昂贵的聘礼

注意酋长有可能会是人下人（上面可能还有宗教领袖什么的），所以要将酋长可被在内的所有的等级范围都判断一遍才能得出答案。按照商品交易链（原商品->替代品，边权为替代交易价格）建有向图，求最短路的时候注意一下等级范围即可。注意在遍历到每一个商品的时候要考虑到以原价购买该商品结束交易链，所以在遍历到合法商品之后立刻比较一次答案。

#define ull unsigned long long
namespace lovelive{
    priority_queue<pair<ull,int> > q;
    vector<int> edge[10005];
    vector<ull> dis[105];
    int n,m,s,ui,vi,wi,pi[105],li[105],x;
    ull d[105];
    bool v[105];
    int main(){
        scanf("%d%d",&m,&n);
        s = 1;
        ull ans = 1ull<<32;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&pi[i],&li[i],&x);
            d[i]=0x3f3f3f3f;
            for(int j=1;j<=x;j++){
                scanf("%d%d",&vi,&wi);
                edge[i].push_back(vi);
                dis[i].push_back(wi);
            }
        }
        for(int _i = li[1] - m; _i<=li[1]; _i++){
            int l = _i,r = _i + m;
            for(int i=1;i<=n;i++){d[i]=0x3f3f3f3f;}
            d[s]=0;
            q.push(make_pair(0,s));
            memset(v,0,sizeof(v));
            while(!q.empty()){
                int x=q.top().second;q.pop();
                ans = min(ans,d[x] + pi[x]);
                if(v[x]){
                    continue;
                }
                v[x]=true;
                for(int i=0;i<edge[x].size();i++){
                    if(li[edge[x][i]]>=l && li[edge[x][i]]<=r && d[edge[x][i]]>d[x]+dis[x][i]){
                        d[edge[x][i]]=d[x]+dis[x][i];
                        q.push(make_pair(-d[edge[x][i]],edge[x][i]));
                    }
                }
            }
        }
        printf("%lld\n",ans);
        return 0;
    }
}

C – Invitation Cards

因为公交车按人数计费，而不是拼车之后只需要付一张票钱，所以需要用最短路解决。可以在按照题目建图的同时再建一张反向图，将学生回到中心的过程转化为中心逆着公交开行路线找到学生的回中心过程，这样判断学生回中心只需要做一次以中心为源的最短路。

莫名被卡，所以重构了一次代码。

namespace lovelive{
    int head[2000005],val[2000005],to[2000005],nxt[2000005];
    int cnt,a,b,c,n,m,dis[2000005];bool vis[2000005];
    int edge[2000005][3];long long ans;
    typedef pair<int,int> P;
    void init(){
        memset(head,0,sizeof(head));
        memset(nxt,0,sizeof(nxt));
        memset(vis,0,sizeof(vis));
        memset(dis,-1,sizeof(dis));
        cnt = 0; dis[1] = 0;
    }
    void addEdge(int a,int b,int c){
        nxt[++cnt] = head[a];
        to[cnt]    = b;
        val[cnt]   = c;
        head[a]    = cnt;
    }
    void dijstra(){
        priority_queue<P,vector<P>,greater<P> > q;
        q.push(make_pair(dis[1],1));
        while(!q.empty()){
            a = q.top().second;
            q.pop();
            if(vis[a])continue;
            vis[a] = true;
            for(int i=head[a];i;i=nxt[i]){
                b = to[i];
                c = val[i];
                if(dis[b]==-1 || dis[b] > dis[a] + c){
                    dis[b] = dis[a] + c;
                    q.push(make_pair(dis[b],b));
                }
            }
        }
    }
    void main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);
        }
        init();
        for(int i=1;i<=m;i++){
            addEdge(edge[i][0],edge[i][1],edge[i][2]);
        }
        dijstra();
        ans = 0;
        for(int i=1;i<=n;i++){
            ans += dis[i];
        }

        init();
        for(int i=1;i<=m;i++){
            addEdge(edge[i][1],edge[i][0],edge[i][2]);
        }
        dijstra();
        for(int i=1;i<=n;i++){
            ans += dis[i];
        }

        printf("%lld\n",ans);
    }
}

D – Big Christmas Tree

由于每一个节点都会对从节点到根的所有边的造价产生影响，并且与所有边是否直接与该节点相连无关，所以将题目转化为为每一个节点找到一条到根最短路，然后乘上该节点的重量。

这个最大值大啊，真的大啊，如果真的很像设个极大值当做初值，建议直接LONG_LONG_MAX(9223372036854775807ll)，实测11451419181000过不了。

虽然大佬们逐鹿Ranking，不过这题自己莫名其妙拿了个一血。

namespace lovelive{
    int head[50005],e[50005],val[100005],to[100005],nxt[100005];
    int cnt,a,b,c,n,m;bool vis[50005];
    int edge[100005][3];long long ans,tmp,dis[50005];
    typedef pair<int,int> P;
    void init(){
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt = 0;
    }
    void addEdge(int a,int b,int c){
        nxt[++cnt] = head[a];
        to[cnt]    = b;
        val[cnt]   = c;
        head[a]    = cnt;
    }
    void dijstra(int s){
        priority_queue<P,vector<P>,greater<P> > q;
        q.push(make_pair(dis[s],s));
        while(!q.empty()){
            a = q.top().second;
            q.pop();
            if(vis[a])continue;
            vis[a] = true;
            for(int i=head[a];i;i=nxt[i]){
                b = to[i];
                c = val[i];
                if(dis[b]==-1 || dis[b] > dis[a] + c){
                    dis[b] = dis[a] + c;
                    q.push(make_pair(dis[b],b));
                }
            }
        }
    }
    void main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&e[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);
        }
        init();
        for(int i=1;i<=m;i++){
            addEdge(edge[i][1],edge[i][0],edge[i][2]);
            addEdge(edge[i][0],edge[i][1],edge[i][2]);
        }
        ans = 9223372036854775807ll;
        for(int i=1;i<=1;i++){
            memset(dis,-1,sizeof(dis));
            dis[i] = 0;
            dijstra(i);
            tmp = 0;
            for(int j=1;j<=n;j++){
                if(dis[j]==-1){
                    tmp = -1;break;
                }
                tmp += dis[j] * e[j];
            }
            if(tmp != -1)ans = min(ans,tmp);
        }
        if(ans == 9223372036854775807ll) printf("No Answer\n");
        else printf("%lld\n",ans);
    }
}

E – Heavy Transportation

最短路的变体，直接套dijkstra，然后把要转移的状态改成可以承受重量的最大值。

namespace lovelive{
    int cnt,a,b,c,n,m;bool vis[50005];
    int edge[1000005][3];int ans,tmp,dis[50005];
    typedef pair<int,int> P;
    void init(){
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt = 0;
    }
    void addEdge(int a,int b,int c){
        nxt[++cnt] = head[a];
        to[cnt]    = b;
        val[cnt]   = c;
        head[a]    = cnt;
    }
    void dijstra(int s){
        priority_queue<P> q;
        q.push(make_pair(dis[s],s));
        while(!q.empty()){
            a = q.top().second;
            q.pop();
            if(vis[a])continue;
            vis[a] = true;
            for(int i=head[a];i;i=nxt[i]){
                b = to[i];
                c = val[i];
                if(dis[b] < min(dis[a] , c)){
                    dis[b] = min(dis[a] , c);
                    q.push(make_pair(dis[b],b));
                }
            }
        }
    }
    void main(int ca){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);
        }
        init();
        for(int i=1;i<=m;i++){
            addEdge(edge[i][1],edge[i][0],edge[i][2]);
            addEdge(edge[i][0],edge[i][1],edge[i][2]);
        }
        memset(dis,0,sizeof(dis));
        dis[1] = 1145141919;
        dijstra(1);
        printf("Scenario #%d:\n",ca);
        printf("%d\n",dis[n]);
        printf("\n");
    }
}

F – Networking

最小生成树模板题，因为图快复制了三年前的智熄板子，所以会有一堆智熄注释。之后的最小生成树都是自己重新写过的版本了。

namespace lovelive{
    struct EDGE{
        int s,e,v;
    };
    EDGE edge[5005];
    int n,ans=0,dis[5005],father[5005];
    long long m;
    int honoka[55][55],cnt;
    int x,y,z,f1,f2,k=0,i;              //x,y,z用于读取变量，
                                        //f1,f2用于找父亲
                                        //k用于查找当前一共连接了几条边 
    inline bool comp(EDGE a,EDGE b){
        return a.v<b.v;
    }
    inline int getFather(int i){
        if(father[i]==i)return i;
        father[i]=getFather(father[i]);
        return father[i];
    }
    inline void initFather(){
        for(i=1;i<=m;i++){
            father[i]=i;
        }
    }
    bool main(){
        scanf("%d",&n);ans = 0;k = 0;cnt = 0;
        memset(honoka,-1,sizeof(honoka));
        if(n==0)return false;
        scanf("%lld",&m);
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            if(honoka[x][y] == -1){
                edge[++cnt].s=x;edge[cnt].e=y;edge[cnt].v=z;
                honoka[x][y] = cnt;
            }else if(z < edge[honoka[x][y]].v){
                edge[honoka[x][y]].v = z;
            }
        }
        sort(edge+1,edge+m+1,comp);         //将边按照权值由小到大排序 
        //------------------------------//核心部分 Kruskal
        initFather();
        for(i=1;i<=m;i++){
            f1=getFather(edge[i].s);
            f2=getFather(edge[i].e);
            if(f1!=f2){                 //如果没有合并
                ans = ans + edge[i].v;  //合并之前先登记
                father[f2]=f1;          //从此以后我们合并
                k++;                    //又有一对关系诞生了 
                if(k==n-1){             //最小生成树一共n-1条边 
                    break;              //合并结束 
                } 
            }
        }
        printf("%d\n",ans); 
        //------------------------------//核心部分结束 
        return true;
    }
}

G – Building a Space Station

预处理的时候算好每个cell之间建边的长度，有重合的按0计。

namespace lovelive{
    typedef pair<double,pair<int,int> > P;
    double dis[105][105],ans;
    double xi[105],yi[105],zi[105],ri[105];
    int n,cnt,flag,fa[105],a,b,ta,tb;P edge[100005];
    int getfa(int p){
        if(fa[p]==p)return p;
        return fa[p] = getfa(fa[p]);
    }
    void main(int n){
        cnt = 0;flag = 0;ans = 0;
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&xi[i],&yi[i],&zi[i],&ri[i]);
            dis[i][i] = 0;fa[i] = i;
            for(int j=1;j<i;j++){
                dis[i][j] = dis[j][i] = max(0.0,sqrt(pow(fabs(xi[i]-xi[j]),2)
                    + pow(fabs(yi[i]-yi[j]),2) + pow(fabs(zi[i]-zi[j]),2)) - ri[i] - ri[j]);
                edge[++cnt] = make_pair(dis[i][j],make_pair(i,j));
            }
        }
        sort(edge+1,edge+cnt+1);

        for(int i=1;i<=cnt;i++){
            a = edge[i].second.first;
            b = edge[i].second.second;
            ta = getfa(a);
            tb = getfa(b);
            if(ta==tb)continue;
            fa[ta] = tb;
            ans += edge[i].first;
            flag ++;
            if(flag==n-1)break;
        }
        printf("%.3f\n",ans);
        return;
    }
}

H – Shichikuji and Power Grid

还以为然而，她在五年级时就去世了，所以她还不够聪明。是google翻译的问题，结果看了原文，发现是真的去世了……

建一个虚拟根节点，然后以建造发电站所需花费作为边权连接各个城市，剩下的根据题意建图即可。

由于最小生成树的所有题套的是一个板子，所以可能存在冗余变量。

namespace lovelive{
    typedef pair<long long,pair<int,int> > P;
    long long dis[2005][2005],ans,ki[2005];
    int xi[2005],yi[2005],ci[2005];
    int n,cnt,flag,fa[2005],a,b,ta,tb;
    P edge[4000005];int anse[2][2005];int ansi[2005],cnti,cnte;
    int getfa(int p){
        if(fa[p]==p)return p;
        return fa[p] = getfa(fa[p]);
    }
    void main(){
        scanf("%d",&n);
        cnt = 0;flag = 0;ans = 0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&xi[i],&yi[i]);
            dis[i][i] = 0;fa[i] = i;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&ci[i]);
            dis[0][i] = dis[i][0] = ci[i];
            edge[++cnt] = make_pair(dis[0][i],make_pair(0,i));
        }
        for(int i=1;i<=n;i++){
            scanf("%lld",&ki[i]);
            for(int j=1;j<i;j++){
                dis[i][j] = dis[j][i] = (ki[i] + ki[j]) * (abs(xi[j]-xi[i]) + abs(yi[j]-yi[i]));
                edge[++cnt] = make_pair(dis[i][j],make_pair(i,j));
            }
        }
        sort(edge+1,edge+cnt+1);
        cnti=cnte=0;

        for(int i=1;i<=cnt;i++){
            a = edge[i].second.first;
            b = edge[i].second.second;
            ta = getfa(a);
            tb = getfa(b);
            if(ta==tb)continue;
            fa[ta] = tb;
            ans += edge[i].first;
            flag ++;
            if(a==0){
                ansi[++cnti] = b;
            }else{
                anse[0][++cnte] = a;
                anse[1][  cnte] = b;
            }
            if(flag==n)break;
        }
        printf("%lld\n%d\n",ans,cnti);
        for(int i=1;i<=cnti;i++){
            printf("%d ",ansi[i]);
        }
        printf("\n%d\n",cnte);
        for(int i=1;i<=cnte;i++){
            printf("%d %d\n",anse[0][i],anse[1][i]);
        }
        return;
    }
}

I – Save your cats

脑筋急转弯题：

  1. 让图中不存在环 -> 把图的多余边裁掉，使其变成一棵树；
  2. 让裁边的花费最少 -> 让最后剩下的树边权之和最大；
  3. 最大生成树 -> 把Kruskal求最小生成树的判断符号改掉，原理是一致的。
namespace lovelive{
    typedef pair<double,pair<int,int> > P;
    double ans,tmp;
    int xi[10005],yi[10005];
    int n,m,cnt,flag,fa[10005],a,b,ta,tb;
    priority_queue<P> q;
    int getfa(int p){
        if(fa[p]==p)return p;
        return fa[p] = getfa(fa[p]);
    }
    void main(){
        scanf("%d%d",&n,&m);
        cnt = 0;flag = 0;ans = 0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&xi[i],&yi[i]);fa[i] = i;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            tmp = sqrt(pow(xi[a]-xi[b],2)+pow(yi[a]-yi[b],2));
            q.push(make_pair(tmp,make_pair(a,b)));
            ans += tmp;
        }

        while(!q.empty()){
            a = q.top().second.first;
            b = q.top().second.second;
            ta = getfa(a);
            tb = getfa(b);
            if(ta==tb){q.pop();continue;}
            fa[ta] = tb;
            //cout<<"D "<<a<<" "<<b<<endl;
            ans -= q.top().first;
            flag ++;
            if(flag==n-1)break;
            q.pop();
        }
        printf("%.3lf\n",ans);
        return;
    }
}

J – Nearest Common Ancestors

模板题。

namespace lovelive{
    int head[10005],nxt[20010],go[20010],cnt;
    int f[10005][21],dep[10005],cnti[10005];
    int n,m,s,a,b;
    inline void dfs(int u,int fa){
        dep[u]=dep[fa]+1;
        for(int i=0;i<=19;i++){
            f[u][i+1]=f[f[u][i]][i];
        }
        for(int i=head[u];i;i=nxt[i]){
            int v=go[i];
            if(v==fa)continue;
            f[v][0]=u;
            dfs(v,u);
        }
    }
    inline void insert(int u,int v){
        nxt[++cnt]=head[u];
        head[u]=cnt;
        go[cnt]=v;
        cnti[v]++;
        //nxt[++cnt]=head[v];
        //head[v]=cnt;
        //go[cnt]=u;
    }
    inline int lca(int x,int y){
        if(dep[x]<dep[y]){
            swap(x,y); 
        }
        for(int i=20;i>=0;i--){
            if(dep[f[x][i]]>=dep[y]){
                x=f[x][i];
            }
            if(x==y){
                return x;
            }
        }
        for(int i=20;i>=0;i--){
            if(f[x][i]!=f[y][i]){
                x=f[x][i];y=f[y][i];
            }
        }
        return f[x][0]?f[x][0]:s;
    }
    void main(){
        memset(head,0,sizeof(head));
        memset(nxt,0,sizeof(nxt));
        memset(cnti,0,sizeof(cnti));
        memset(dep,0,sizeof(dep));
        memset(f,0,sizeof(f));
        cnt = 0;
        scanf("%d",&n);
        for(int i=1;i<=n-1;i++){
            scanf("%d%d",&a,&b);
            insert(a,b);
        }
        scanf("%d%d",&a,&b);
        for(int i=1;i<=n;i++)
            if(cnti[i]==0){
                dfs(i,0);break;
            }
        printf("%d\n",lca(a,b));
    }
}

K – Cow Contest

题名：传递闭包及其应用。在OI-WIKI上传递闭包和最短路在一起，因为传递闭包的实现差不多就是floyd的变种。bitset的优化好神奇，让我再研究亿会。

确定等级的关键是知道有几头牛等级比当前牛高，有几头牛比当前牛低，如果所有除了当前牛以外的牛与当前牛的关系都知道了，这头牛的排名就能唯一确定。

namespace lovelive{
    bitset<105> f[105];
    int n,m,a,b,cnt=0;
    int in[105],out[105];
    int ans;
    void main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            f[a][b] = 1;
        }
        for(int k=1;k<=n;k++){
            in[k] = out[k] = 0;
            for(int i=1;i<=n;i++){
                if(f[i][k]) f[i] = f[i] | f[k];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(f[i][j]){
                    in[j]++;
                    out[i]++;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(in[i]+out[i]==n-1)ans++;
        }
        printf("%d\n",ans);
    }
}

L – Book

并不是纯粹的拓扑排序，因为你不能倒着读书，所以就算前置章节在当前章节的后面，你也还是需要再看一遍才能理解当前章节。

所以需要储存一个“最多第几次看书时，能够有机会看懂该章节”。如果看完当前章节之后解锁的章节在当前章节的前面，并且被解锁的章节机会计数小于当前章节+1（一个章节可能存在多个前置章节，并且需要读完所有前置章节才算完全看懂），就需要更新状态。

namespace lovelive{
    int head[200005],nxt[200005],to[200005];
    int cnt,in[200005],n,m,ans,cur,ansi[200005];
    bool vis[200005];priority_queue<int,vector<int>,greater<int>> q;
    void add_edge(int a,int b){
        nxt[++cnt] = head[a];
        to[cnt] = b;
        head[a] = cnt;
    }
    void main(){
        scanf("%d",&n);
        cnt = 0;
        for(int i=1;i<=n;i++){
            head[i]=ansi[i]=0;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&in[i]);
            for(int j=1;j<=in[i];j++){
                scanf("%d",&m);
                add_edge(m,i);
            }
        }
        cnt = 0;ans = 0;
        for(int i=1;i<=n;i++){
            if(in[i]==0){
                ans += 1;
                q.push(i);
                ansi[i] = 1;
            }
        }
        while(!q.empty()){
            cur = q.top();q.pop();
            cnt++;
            for(int i=head[cur];i;i=nxt[i]){
                if(to[i] > cur) ansi[to[i]] = max(ansi[to[i]],ansi[cur]);
                else            ansi[to[i]] = max(ansi[to[i]],ansi[cur]+1);
                if(--in[to[i]]==0){
                    q.push(to[i]);
                }
            }
        }
        if(cnt<n){
            printf("-1\n");return;
        }
        ans = ansi[1];
        for(int i=2;i<=n;i++){
            ans = max(ans,ansi[i]);
        }
        printf("%d\n",ans);
    }
}

M – Watchcow

也许算知识盲区，但不完全是。因为前面WEEK_3 U – 卷王的测试（Hemose in ICPC ?）用到过“树的欧拉序”，应用领域和这里的欧拉回路差不多，但当时只是用来优化的，学的不深入。

这题因为在建双向边的时候，实际实现是建两个单向边，所以保证了图是欧拉图，就可以直接求欧拉回路。求法也是大同小异，但由于树每个节点只会被dfs执行一次，所以实际实现的时候不需要删边操作，但放到图中，删边是必要的。

namespace lovelive{
    const int MAXN = 10005, MAXM = 100005;
    int dfn[MAXN],low[MAXN],sta[MAXN];
    int statop,cnt;
    vector<stack<int> > edge;
    vector<int> ansi;
    int n,m,a,b;
    void __init(){
        statop = cnt = 0;
        edge.clear();
        edge.resize(n+1);
        ansi.clear();
        memset(dfn,0,sizeof(dfn));
    }
    void addEdge(int u,int v){
        edge[u].push(v);
        edge[v].push(u);
    }
    void dfs(int cur){
        while(!edge[cur].empty()){
            int to = edge[cur].top();
            edge[cur].pop();
            dfs(to);
        }
        ansi.push_back(cur);
    }
    void main(){
        scanf("%d%d",&n,&m);
        __init();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            addEdge(a,b);
        }
        dfs(1);
        for(vector<int>::iterator i=ansi.begin();i!=ansi.end();i++){
            printf("%d\n",*i);
        }
        return ;
    }
}
知识共享许可协议
《ZJUT2022入门题单Week5 程序简注》在文章中没有特殊说明的情况下采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。请在转载时注明作者（从现瑕疵）和来源（https://www.zhtg.net.cn/zjut2022-week5/）
传递闭包位运算图论并查集拓扑排序最小生成树最短路最近公共祖先欧拉回路算法
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

															
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
数论笔记

							
							

							
蚌埠住了的大模拟专题 (1)

							
							

							
ZJUT2022寒假集训3 字符串1 程序简注

							
							

							
Codeforces Round #841 (Div. 2) 赛后复盘

							
							

							
ZJUT2022寒假集训2 基础专题2 程序简注

							
							

							
ZJUT2022寒假集训1 基础专题1 程序简注

							
							

							
试图整一个自己的模板列表

							
							

							
ZJUT2022入门题单Week6 动态规划

							
							

							
Codeforces Round #832 (Div. 2) 解题日志

							
							

							
ZJUT 2022.11.02 Codeforces练习 程序简注