拓扑排序以及关键路径总结

发布于 2018-12-06  790 次阅读

 

拓扑排序以及关键路径的总结

拓扑排序：首先纠正一个读音问题：拓扑(tuopu)话说我好几次都读成(tabu) (tuobu)好吗！

      拓扑排序是针对AOV图（即有向无边图，且图中不允许环的存在）的一种排序算法，它用于将一个AOV图按照顺序排成线性序列

       基本操作如下：

1.记录每个节点的入度

2.每次找到入度为零的点入栈，并将与之相连的节点入度减一

3.重复2的动作，直到栈为空

4.判断当前操作进行的次数，少于n次则有环，否则输出拓扑序列

家谱树

【问题描述】

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。

给出每个人的孩子的信息。

输出一个序列，使得每个人的后辈都比那个人后列出。

【输入格式】

第1行一个整数N（1<=N<=100），表示家族的人数。

接下来N行，第I行描述第I个人的儿子。

每行最后是0表示描述完毕。

【输出格式】

输出一个序列，使得每个人的后辈都比那个人后列出。

如果有多解输出任意一解。

【输入样例】

5

0

4 5 1 0

1 0

5 3 0

3 0

【输出样例】

2 4 5 3 1

#include
#include
#include
using namespace std;
const int MAX=10000;
int first[MAX],nxt[MAX],go[MAX],arcnum=1;
int rd[MAX],stack[MAX],top;
void addarc(int a,int b){
    nxt[arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum++]=b;
}

int main()
{
//   freopen("in.txt","r",stdin);
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        while(scanf("%d",&m)!=EOF &&m!=0)
            addarc(i,m),rd[m]++;
    for(int i=1;i<=n;i++)
        if(rd[i]==0)
            stack[++top]=i;
    do{
        int now=stack[top--];
        printf("%d ",now);
        for(int p=first[now];p!=0;p=nxt[p]){
            rd[go[p]]--;
            if(rd[go[p]]==0)
                stack[++top]=go[p];
        }
    }while(top!=0);
    
    
    return 0;
}

该题是明显的拓扑排序题，按照标准格式写程序即可

 

奖金

（http://fzoj.xndxfz.com/JudgeOnline/problem.php?id=1624）

描述

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。

输入

第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。

输出

若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。

样例输入

2 1

1 2

样例输出

201

提示

80％的数据满足n<=1000，m<=2000；100％的数据满足n<=10000，m<=20000。

此题比上一题多加入了点的权值

也就是计算拓扑序列中权值和最小是多少

标准做法：使用拓扑排序，在去掉某个点后，遍历它的相连节点时，计算该点的权值，是在(val[v],val[u]+1),其中u为起点，v为中点，中取最大值，开始我的理解出现的偏差，不能在那个点入度为0的时候才计算那个点的权值，因为那个点要满足的条件是比它之前的所有点权值都要小

#include
#include
#include
using namespace std;
const int MAX=300000;
int first[MAX],nxt[MAX],go[MAX],arcnum=1,rd[MAX];
int stack[MAX],val[MAX],top;
void addarc(int a,int b){
    nxt[arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum++]=b;
}
int main()
{
//   freopen("in.txt","r",stdin);
    int n,m,a,b,k=0,tot=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        addarc(b,a);//b比a工资低 
        rd[a]++;//入度+1 
    }
    for(int i=1;i<=n;i++)
        if(rd[i]==0)//将入度为0的点入栈 
            stack[++top]=i;
    while(top!=0){
        int now=stack[top--];//当前点 
        k++; tot+=100+val[now]; 
        for(int p=first[now];p!=0;p=nxt[p]){
            val[go[p]]=max(val[go[p]],val[now]+1);//不应当在入度为0时才更新val[]，而应当每次都更新，取最大值 
            if(--rd[go[p]]==0)
                stack[++top]=go[p];
            }
    }
    
    if(k==n) printf("%d",tot);
    else printf("Poor Xed");
    
    
    return 0;
    
}

fzoj1621:烦人的幻灯片

题目描述

李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己做演讲要用的幻灯片随便堆放在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。情况是这样，教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1，2，…，n在上面编上了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。

现在我们用大写字母A，B，C，。。。再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母对应不起来，我们就称对应是无法实现的。

输入

第一行：只有一个数n，表示有n张幻灯片。

接下来的n行：包括4个整数Xmin，Xmax，Ymin，Ymax（整数之间用空格分开），为幻灯片的坐标（该区域为幻灯片），这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，...再接下来的n行依次为n个数字编号的坐标X，Y，显然在幻灯片之外是不会有数字的。

输出

若是对应可以实现，你的输出应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且各行以字母的升序排列，注意输出的字母要大写并且顶格；反之，若是对应无法实现，在第一行顶格输出None即可。行首行末无多余空格。

样例输入

4

6 22 10 20

4 18 6 16

8 20 2 18

10 24 4 8

9 15

19 17

11 7

21 11

样例输出

A 4

B 1

C 2

D 3

这道题并不完全是拓扑排序题，但却用到了拓扑排序的思想

读懂题意是关键，本题意思是每个数字都对应了一个或多个幻灯片，然后要求从中找出数字与幻灯片的一一对应关系

节点个数很少，直接用邻接矩阵存储

由于是数字对应幻灯片，所以我选择存储每个数字的出度，当某个数字出度为1时，寻找它所对应的幻灯片，记录，并且将与该幻灯片连接的其余数字全部断绝联系，出度也减1

这样，n次之后就可以得到完整的一一对应关系

 

#include
#include
#include
using namespace std;
const int MAX=1000;
int X1[MAX],X2[MAX],Y1[MAX],Y2[MAX],map[MAX][MAX],cd[MAX],ans[MAX];
int stack[MAX],top;

bool IsInside(int x,int y,int t){//第t张输入的幻灯片
    return x>X1[t]&&xY1[t]&&yint main()
{
//   freopen("in.txt","r",stdin);
    int n,x,y,k=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d",&X1[i],&X2[i],&Y1[i],&Y2[i]);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        for(int j=1;j<=n;j++)
            if(IsInside(x,y,j))
                map[i][j]=1,cd[i]++;//第i个数字在j-'A'+1的幻灯片中 
    }
    
    for(int i=1;i<=n;i++)
        if(cd[i]==1)
            stack[++top]=i;
    do{
        int u=stack[top--];
        k++;
        for(int v=1;v<=n;v++)  
            if(map[u][v]==1){//如果u到v有路径 则u属于v 
                ans[v]=u;
                for(int i=1;i<=n;i++)
                if(map[i][v]==1){
                    map[i][v]=0; cd[i]--;
                    if(cd[i]==1)
                        stack[++top]=i;
                }
                break;
            }
        
    }while(top!=0);
    if(k!=n) printf("None");
    else
        for(int i=1;i<=n;i++)
            printf("%c %d\n",'A'+i-1,ans[i]);

    return 0;
}

 

 

关键路径：

建立在一种新图上：AOV图（用点表示时间，边表示活动，边的权值表示活动持续的时间的一种图）

四个重要的量

  1. 事件最早发生时间ve[]
  2. 事件最晚发生时间vl[]
  3. 活动最早开始时间e[]
  4. 活动最晚开始时间l[]

各个量的求法及求解顺序：

  1. Ve，以Ve[1]=0开始，所有起点u终点v都按照ve[v]=max(ve[v],ve[u]+dis[u][v])的方法进行计算，并且记录下拓扑序列
  2. Vl，顺序：逆拓扑序列，以Vl[n]=Ve[n]开始，（因为终点是关键事件，所以最早和最晚开始时间相等）起点u终点v都按照vl[v]=min(vl[v],vl[u]-dis[u][v])的方法求解（此处注意，程序开头必须memset）
  3. e，事件的最早发生时间就等于活动的最早开始时间
  4. l，对于起点x终点y之间的活动i，l[i]=vl[y]-dis[x][y]

如果e[i]==l[i]则说它是关键活动

结束。

 

Question：活动的最早最晚开始时间和事件的最早最晚发生时间有什么关系，它们各自属于实际问题中的那一个量？（我只会求，但并不能完全明白它们的差别或者用途）

前面奖金一题所用的方法是不是关键路径中的求事件最早发生时间？

 

关键路径计算

（http://fz.openjudge.cn/graph/015/）

描述

给出一个AOE图，请输出其关键路径；

输入

第一行：n，m（n,m<=100分别表示节点个数与边的条数）

接下来m行，第i+1行，表示第i条边，每行三个数：ai,bi,ci，表示存在一条ai指向bi权值为ci的边。

注意：起点为结点1，终点为结点n

输出

将关键路径的边的编号从小到大输出

样例输入

9 11

1 2 6

1 3 4

1 4 5

2 5 1

3 5 1

4 6 2

5 7 9

5 8 7

6 8 4

7 9 2

8 9 4

样例输出

1

4

7

8

10

11

标准问题，注意在输出之前要排序

#include
#include
#include
using namespace std;
const int MAX=1000;
int first[MAX],go[MAX],nxt[MAX],dis[MAX][MAX],arcnum=1;
int stack[MAX],top,ve[MAX],vl[MAX],e[MAX],l[MAX],rd[MAX];
int order[MAX],ans[MAX],sum;
void addarc(int a,int b,int c){
    nxt[arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum++]=b;
    dis[a][b]=c;
}
int main(){
//   freopen("in.txt","r",stdin);
    int n,m,a,b,c,k=0;
    scanf("%d%d",&n,&m);
    memset(vl,127,sizeof(vl));
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        addarc(a,b,c);
        rd[b]++;
    }
    for(int i=1;i<=n;i++)
        if(rd[i]==0)
            stack[++top]=i;//入栈 
    do{//第一次，求事件最早发生时间 
        int u=stack[top--],v; k++;
        order[k]=u;//记录顺序 
        for(int p=first[u];p!=0;p=nxt[p]){
            v=go[p]; rd[v]--;
            ve[v]=max(ve[v],ve[u]+dis[u][v]);
            if(rd[v]==0)
                stack[++top]=v;
        }
    }while(top!=0);
    
    vl[n]=ve[n];//中点的事件最晚发生时间等于最早发生时间 
    for(int i=n-1;i>=1;i--){
        int u=order[i],v;
        for(int p=first[u];p!=0;p=nxt[p]){
            v=go[p];
            vl[u]=min(vl[u],vl[v]-dis[u][v]);
        }
    }
    
    for(int i=1;i<=n-1;i++){//计算活动的最早发生时间和最晚发生时间 
        int u=order[i],v;
        for(int p=first[u];p!=0;p=nxt[p]){
            v=go[p];
            e[p]=ve[u];//活动最早发生时间等于起始点的最早发生时间 
            l[p]=vl[v]-dis[u][v];//活动最晚发生时间等于终点最晚发生时间减去活动的长度 
            if(e[p]==l[p]) ans[++sum]=p;
        }
    }
    
    sort(ans+1,ans+1+sum);
    for(int i=1;i<=sum;i++)
        printf("%d\n",ans[i]);
    return 0;
}

HDU4109 Instrction Arrangement

http://acm.hdu.edu.cn/showproblem.php?pid=4109

Problem Description

阿狸这个学期学了计算机组织结构课程。他知道了指令之间可能有依存关系，像WAR（write after read，读之后写），WAW，RAW。如果两个指令之间的时间小于安全时间，它就会导致危险，从而引起错误的结果。所以我们需要设计特殊的回路去消除危险。然而，解决这个问题最简单的方法是添加等待时间（或者由其它的操作填充），如果没有其它的操作填充就意味着需要浪费时间去保证两个指令之间的时间不小于安全时间。

两个指令之间的时间的定义就是它们起始时间差。

现在我们有很多指令，并且我们知道依存关系和指令之间的安全事件。我们也有非常强大的无限核的CPU。所以你可以在同一时间想跑多少指令就跑多少指令。这个CPU可以只消耗1ns就完成任何指令。

你的工作就是重新安排这些指令顺序所以CPU就可以用最短时间完成所有的指令。

Input

输入包括几个测试案例

头两行有两个整数N,M（N<=1000,M<=1000），其中N表示N条指令和M表示M个依存关系

接下来的M行，每行包括3个整数X,Y,Z，意思是X和Y之间的安全时间是Z，而且Y必须在X之后运行。这些指令从0到N-1标号。

Output

打印一个整数，CPU运行的最短时间

Sample Input

5 2

1 2 1

3 4 1

Sample Output

2

HINT

在第1ns中，指令0，1和3被执行了。

在第2ns中，指令2,和4被执行了

所以答案是2

也是求事件最早发生时间（这些指令什么时候最早全部执行完）的题

注意：

  1. memset！！！！！！！
  2. 指令由0到n-1编号，注意转换
#include
#include
#include
using namespace std;
const int MAX=1020;
int first[MAX],nxt[10200],go[10200],arcnum;
int dis[MAX][MAX],rd[MAX],val[MAX],stack[10200],top;
void addarc(int a,int b,int c){
    nxt[arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum++]=b;
    dis[a][b]=c;
}

int main()
{
//   freopen("in.txt","r",stdin);
    int n,m,x,y,z,maxx;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(dis,0,sizeof(dis));
        memset(rd,0,sizeof(rd));
        memset(val,0,sizeof(val));
        memset(first,0,sizeof(first));
        maxx=-1; arcnum=1;
        for(int i=1;i<=n;i++)
            val[i]=1;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            addarc(++x,++y,z);
            rd[y]++;
        }
        for(int i=1;i<=n;i++)  
            if(rd[i]==0)
                stack[++top]=i;
        do{
            int u=stack[top--],v;
            for(int p=first[u];p!=0;p=nxt[p]){
                v=go[p];
                val[v]=max(val[v],val[u]+dis[u][v]);
                maxx=max(val[v],maxx);
                if(--rd[v]==0)
                    stack[++top]=v;
            }
            
        }while(top!=0);
        printf("%d\n",maxx);
    }
    return 0;
}

 

Poj3687 Labeling Balls

escription

Windy有N个不同重量的求，现在他打算给他们贴上1到N的标签：

没有两个相同的球

这些标签要符合规则例如“标签a球轻于标签b球”

你能帮他解决这个问题吗？

Input

第一行是数据个数.每组数据第一行是两个整数： N (1 ≤ N ≤ 200)和 M (0 ≤ M ≤ 40,000).接下来M行，每行两个整数a和 b表示 标签a球轻于标签b球. (1 ≤ a, b ≤ N) 每组数据后有一个空行

Output

每组测试数据输出一行，按照小球的1~N，小球的重量输出，如果有多组解： you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on...如果无解，输出-1。

Sample Input

5

4 0

4 1

1 1

4 2

1 2

2 1

4 1

2 1

4 1

3 2

Sample Output

1 2 3 4

-1

-1

2 1 3 4

1 3 2 4

这道题至今未通过。初步思路是建立小顶堆和拓扑排序，以便在几个球重量相等时输出编号最小的。

但是问题来了，在我操作入度为0的节点时，可能会又有新的节点加入堆，从而导致我整个答案完全不对。

#include
#include
#include
using namespace std;
int first[300],nxt[40200],go[40200],arcnum;
int rd[300],stack[40200],ans[300],heap[10000],len;
void addarc(int a,int b){
    nxt[arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum++]=b;
}

bool cmp(int a,int b){
    return aint Get(){
    int t=heap[1],now=1,next;
    heap[1]=heap[len--];
    while(now*2<=len){
        next=now*2;
        if(next1],heap[next])) next++;
        if(cmp(heap[now],heap[next])) break;
        swap(heap[now],heap[next]);
        now=next;
    }
    return t;
}

void Put(int p){
    int now=++len,next;
    heap[len]=p;
    while(now>1){
        next=now>>1;
        if(!cmp(heap[now],heap[next])) break;
        swap(heap[now],heap[next]); 
        now=next;
    }
}

int main()
{
    int t,n,m,a,b,k;
    scanf("%d",&t);
    while(t--){
        arcnum=1; k=0; len=0;
        memset(first,0,sizeof(first));
        memset(rd,0,sizeof(rd));
        memset(ans,0,sizeof(ans));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            addarc(a,b);
            rd[b]++;
        }
        for(int i=1;i<=n;i++)
            if(rd[i]==0)
                Put(i);
        do{
            int u=Get(),v;
            ans[u]=++k;
            for(int p=first[u];p!=0;p=nxt[p]){
                v=go[p];
                if(--rd[v]==0)
                    Put(v);
            }
        }while(len>0);
        if(k!=n) printf("-1\n");
        else{
            for(int i=1;i<=n;i++)
                printf("%d ",ans[i]);
            printf("\n");
        }
    }
    
    return 0;
}

又想到把拓扑排序后的点记录下来，来个快排，但是有的球没有限制条件，强行把权设为0又会错。

#include
#include
#include
using namespace std;
int first[300],nxt[40200],go[40200],arcnum;
int rd[300],stack[40200],top;
struct node{
    int val,id;
}ans[300];

void addarc(int a,int b){
    nxt[arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum++]=b;
}

bool cmp(node a,node b){
    if(a.val!=b.val)
        return a.valreturn a.idint main()
{
    int t,n,m,a,b,k;
    scanf("%d",&t);
    while(t--){
        arcnum=1; k=0; top=0;
        memset(first,0,sizeof(first));
        memset(rd,0,sizeof(rd));
        memset(ans,0,sizeof(ans));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            ans[i].id=i,ans[i].val=0;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            addarc(a,b);
            rd[b]++;
        }
        for(int i=1;i<=n;i++)
            if(rd[i]==0)
                stack[++top]=i;
        do{
            int u=stack[top--],v;
            k++;
            for(int p=first[u];p!=0;p=nxt[p]){
                v=go[p];
                ans[v].val=max(ans[v].val,ans[u].val+1);
                if(--rd[v]==0)
                    stack[++top]=v;
            }
        }while(top!=0);
        if(k!=n) printf("-1\n");
        else{
            sort(ans+1,ans+1+n,cmp);
            for(int i=1;i<=n;i++)
                printf("%d ",ans[i].id);
            printf("\n");
        }
    }
    
    return 0;
}

据说建立大顶堆就可以解决问题？？？？

 

CTFer|NOIPer|CSGO|摸鱼|菜鸡