拓扑排序学习小记 HDU 1285 确定比赛名次 + HDU 2647 Reward

落日映苍穹つ 2022-08-25 08:46 110阅读 0赞

拓扑排序，以下摘自http://blog.csdn.net/midgard/article/details/4101025：

拓扑排序是对有向无环图(DAG图)的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环，则无法表示两个顶点的先后顺序。

在现实生活中，也会有不少应用例子，比如学校课程布置图，要先修完一些基础课，才可以继续修专业课。

一个简单的求拓扑排序的算法：首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑排序。

**HDU 1285 确定比赛名次**

#include <cstdio>
    #include <cstring>
    
    const int N=510;
    
    bool graph[N][N];
    int indegree[N];
    int n,m;
    
    void Topologicsort ()
    {
        for (int i=1;i<=n;i++) for (int j=1;j<n+1;j++)
            if (indegree[j]==0)
            {//入度为0,则输出
                printf(i==n?"%d\n":"%d ",j);
                indegree[j]--;
                for (int k=1;k<n+1;k++)
                if (graph[j][k])
                    indegree[k]--;
                break;
            }
    }
    
    int main ()
    {
        while (~scanf("%d%d",&n,&m))
        {
            memset(graph,false,sizeof(graph));
            memset(indegree,0,sizeof(indegree));
            for (int i=0;i<m;i++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if (graph[a][b]==false) //预防重边,会影响入度
                {
                    graph[a][b]=true;
                    indegree[b]++;
                }
            }
            Topologicsort();
        }
    }

**HDU 2647 Reward**

参考了：http://blog.csdn.net/zyy173533832/article/details/11483505

#include <cstdio>
    #include <cstring>
    
    const int N=10005;
    
    struct node
    {
    	int v,next;
    }edge[2*N];
    
    int head[N],e;
    
    void add(int a,int b)
    {
    	edge[e].v=b;
    	edge[e].next=head[a];
    	head[a]=e++;
    }
    
    int n,m;
    int indegree[N];
    int temp[N];//临时记录入度为0点,也就是分析中的在同一层次同一要求奖金额的工人
    
    int Topologicsort ()
    {
    	int reward=888;//初始奖励
    	int ans=0;//最后奖励总和
    	int cnt,j;
    	for (int i=0;i<n;i+=cnt)
    	{
    		cnt=0;//入度为0点的个数
    		for (j=1;j<=n;j++)
    			if (indegree[j] == 0)
    			{
    				temp[cnt++]=j;
    				indegree[j]=-1;
    			}
    		if (cnt==0) return -1;//没有找到就是形成了环，达不到要求
    		ans += reward*cnt;  //这一次入度为0的点数 *  此层的要求奖励额 
    		reward++;
    		for (j=0;j<cnt;j++) //可达边的删除
    			for (int k=head[temp[j]]; k!=-1; k=edge[k].next)
    			{
    				int v=edge[k].v;
    				indegree[v]--;
    			}
    	}
    	return ans;
    }
    
    int main ()
    {
    	while (~scanf("%d%d",&n,&m))
    	{
    		int a,b;
    		e=0;
    		memset(head,-1,sizeof(head));
    		memset(indegree,0,sizeof(indegree));
    		for (int i=0;i<m;i++)
    		{
    			scanf("%d%d",&a,&b);
    			add(b,a);
    			indegree[a]++;
    		}
    		printf("%d\n",Topologicsort());
    	}
    	return 0;
    }