精华内容
下载资源
问答
  • 被samlpe output 坑惨了啦…… samlpe output里面 REMOVE BROWSER Removing BROWSER (echo) ... Removing TCPIP  ...总之我就是按书上思路敲了一遍 代码略有不同但是大体意思是一样。捣...

    被samlpe output 坑惨了啦……

    samlpe output里面

    REMOVE BROWSER

    Removing BROWSER (echo)

    Removing HTML 

    Removing TCPIP 

    对 这两行的顺序我一直搞不定 然后心想 难道要把遍历倒过来?当然不是 然而我还真这么干了。……

     

    总之我就是按书上的思路敲了一遍 代码略有不同但是大体意思是一样的。捣鼓了半天实际上这是一个拓扑图我感觉。但是要用图的话可能链式结构会不考思维一点,但是逻辑感觉能爆炸。但其实从出入度角度也能写……明天或者今天晚上再看看。

     

    看个吉尔!每次安装卸载整个图就会变动,出入度也会变,也就是说每次都要给他整一遍出度多少入度多少铁定超时呀。

     

    诶 不对 每次安装的时候出入度+1卸载的时候出入度-1还是可以的呀……woc……

     

    不会再研究了,出入度太蠢了,不管怎么想都觉得不如根据依赖关系来的爽快,实在是不愿意再想了,就这样过吧

    #include<iostream>
    #include<cstring>
    #include<string>
    #include<sstream>
    #include<vector>
    #include<algorithm>
    #include<map>
    using namespace std;
    
    const int maxn = 10000;
    
    int idx = 0;
    
    map<int, string>id_name;
    map<string, int>name_id;
    vector<int>depend[maxn], depended[maxn];
    vector<int>list;
    int state[maxn];
    
    int getid(string s)
    {
    	if (name_id.count(s));
    	else
    	{
    		int id = idx;
    		name_id[s] = id;
    		id_name[id] = s;
    		idx++;
    	}
    	return name_id[s];
    }
    
    void install(int id, bool flag)
    {
    	if (state[id] && flag)
    	{
    		cout << "   " << id_name[id] << " is already installed." << endl;
    		return;
    	}
    	if (state[id])return;
    	int len = depend[id].size();
    	for (int i = 0; i < len; i++)
    	{
    		install(depend[id][i], false);
    	}
    	list.push_back(id);
    	state[id] = flag ? 1 : 2;
    	cout << "   Installing " << id_name[id] << endl;
    }
    
    int remove(int id, bool flag)//1-- not install 2-- still needed 0-- everything ok removing
    {
    	if (state[id] == 0)return 1;
    	int num = depended[id].size();
    
    	for (int i = 0; i < depended[id].size(); i++)
    	{
    		if (state[depended[id][i]] == 0)
    			num--;
    	}
    	if (num)return 2;
    	else if (num == 0)
    	{
    		state[id] = 0;
    		list.erase(find(list.begin(), list.end(), id));
    		cout << "   Removing " << id_name[id] << endl;
    		//for (int i = depend[id].size() - 1; i >= 0; i--)
    		for(int i=0;i<depend[id].size();i++)
    		{
    			if(state[depend[id][i]]==2)
    				int res = remove(depend[id][i], false);
    		}
    	}
    	return 0;
    }
    
    void print()
    {
    	//if (list.empty())cout << "   just test" << endl;
    	for (int i = 0; i < list.size(); i++)
    	{
    		int id = list[i];
    		if (state[id])cout << "   " << id_name[id] << endl;
    	}
    }
    
    int main()
    {
    	//freopen("D:\\in.txt", "r", stdin);
    	//freopen("D:\\out.txt", "w", stdout);
    	string s;
    	memset(state, 0, sizeof(state));
    	while (getline(cin, s))
    	{
    		cout << s << endl;
    		stringstream ss(s);
    		string op;
    		ss >> op;
    		if (op == "DEPEND")
    		{
    			string item1, item2;
    			ss >> item1;
    			int id1 = getid(item1);
    			while (ss >> item2)
    			{
    				int id2 = getid(item2);
    				depend[id1].push_back(id2);
    				depended[id2].push_back(id1);
    			}
    		}
    		else if (op == "INSTALL")
    		{
    			string item;
    			ss >> item;
    			int id = getid(item);
    			install(id, true);
    		}
    		else if (op == "REMOVE")
    		{
    			string item;
    			ss >> item;
    			int id = getid(item);
    			int result = remove(id, true);
    			if (result == 1)
    				cout << "   " << id_name[id] << " is not installed." << endl;
    			else if (result == 2)
    				cout << "   " << id_name[id] << " is still needed." << endl;
    			//else if(result==0)
    		}
    		else if (op == "LIST")
    		{
    			print();
    		}
    		else if (op == "END")
    		{
    			break;
    		}
    	}
    	//fclose(stdin);
    	//fclose(stdout);
    	return 0;
    }

     

    展开全文
  • 非线性结构在传统意义上确实不太好排序,而拓扑排序它是对有向图顶点排成一个线性序列。并且不一定唯一。 什么是拓扑排序? 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成...

    原创不易,帅哥美女呢请三连支持一波

    前言

    大家好,我是bigsai。

    拓扑排序,很多人都可能听说但是不了解的一种算法。不知者大多会提出这样的疑问:

    这是某种排序算法?这好像是一种图论算法?图也能排序?

    非线性结构在传统意义上确实不太好排序,而拓扑排序它是对有向图的顶点排成一个线性序列。并且不一定唯一。

    什么是拓扑排序?

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序

    拓扑排序有何作用?

    拓扑排序的应用其实还是蛮多的,拓扑排序在一些工程有多道工序时候可以获取一个有效的加工顺序、还有些游戏里的任务成就必须满足一个符合的拓扑排序才能解锁下一关、还有一些项目或者环境的依赖关系集……

    当然上面的例子可能不够具体,离我们稍微近一点的就是课程学习上,比如你学习数据结构之前基本要学习C或者C++这门课,因为数据结构中需要懂和会用C++的代码;学习操作系统、计算机网络之前要学习数据结构这门课,因为里面涉及到很多数据结构和算法;学习Java Web开发前要学习JavaSE和HTML这两门课;不同院校课程安排截然不同但均能很好的连接起来,就是因为安排的课程满足一个拓扑排序。

    拓扑排序还是不能理解?我举个更详细的例子,学习Java系列的教程部分,可能有下面这个顺序:

    代号 科目 学前需掌握
    A1 JavaSE
    A2 HTML
    A3 JSP A1,A2
    A4 Servlet A1
    A5 SSM A3,A4
    A6 SpringBoot A5

    就比如学习Java系类(部分)从Java基础,到JSP/Servlet,到SSM,到SpringBoot,SpringCloud等是个循序渐进、且有前提依赖的过程。在JSP学习要首先掌握Java基础和HTML基础。学习框架要掌握JSP/Servlet和JDBC之类才行。那么,这个学习过程即构成一个拓扑序列。当然这个序列也不唯一你可以对不关联的学科随意选择顺序(比如Html和Java可以随便先开始哪一个)

    那上述序列可以简单表示为:

    image-20210607113325346

    这五种均为可以选择的学习方案,对课程安排可以有参考作用,这五个都是上面有向无环图(DAG)的拓扑序列,只是小的选择的策略不同(先学Java或者先学HTML不要紧,但是要满足整个顺序要求),不影响满足规则顺序!

    对于拓扑排序,还有一些比较专业的名词需要铭记:

    DAG:有向无环图
    AOV网:数据在顶点,顶点表示活动,边表示活动的先后关系,可以理解为一种面向对象。
    AOE网:数据在边上,顶点表示事件,有向边表示活动,边上的权值表示该活动持续的时间,可以理解为面向过程。

    很多人不知道AOE网干啥用的,拓扑排序是解决一个工程能否顺序进行的问题,但有时还需解决工程完成需要的最短时间。而AOE经常使用在求关键路径中(这里就先不进行详细介绍内容和算法了),图片来源https://www.cnblogs.com/svod5306/p/14723338.html)。

    img

    我们今天讲的拓扑排序就是在AOV中找到不破坏图结构的序列,对于有向无环图,需要注意一下图中:若A在B前面,则不存在B在A前面的路径(不能成环)。图中两个相邻节点在拓扑序列中只需要满足前后关系而不一定需要相邻(节点只需满足相对的前后关系,所以拓扑排序并不一定唯一)。

    算法分析

    上面简单的介绍了拓扑排序,下面详细讲讲拓扑排序的求法。

    image-20210607152545338
    正常步骤为(方法不一定唯一)

    1.从DAG图中找到一个没有前驱的顶点输出。可以遍历入度为0的节点,也可以用优先队列维护。

    2.删除以这个点为起点的边。删除一条边,其指向节点的入度减1,这样为了找到下个没有前驱节点的顶点。

    3.重复上述,直到最后一个顶点被输出。如果还有顶点未被输出,则说明有环!

    对于上图的简单序列,可以简单描述步骤为:

    step1:删除节点1(或者2)及其指向的边,将节点输出
    image-20210607153332186

    step2:删除节点2(或者3)及其指向的边,将节点输出
    image-20210607153733105

    step2(这里进行两步):删除节点3(或者4)及其指向的边,将节点输出,紧接着删除节点3(或者6)其指向的边,将节点输出。

    image-20210607155359497

    step3:按照上述规则重复进行,直到所有节点都被删除。
    image-20210607160806485

    这样就完成一次拓扑排序流程,得到一个拓扑序列,但是这个序列并不唯一,从算法执行过程中也看到有很多选择方案,具体得到结果看你算法的设计了,但只要满足DAG图中前后相对关系。

    另外观察 1 2 4 3 6 5 7 8 这个序列满足我们所说的有关系的节点指向的在前面,被指向的在后面。如果完全没关系那不一定前后(例如1,2)

    代码实现

    对于拓扑排序,如何用代码实现呢?

    虽然在上面详细介绍了思路和流程,也很通俗易懂,但是实际上代码的实现还是很需要斟酌的,如何在空间和时间上能够得到较好的平衡且取得较好的效率?

    首先要考虑存储,对于节点,是用邻接矩阵还是邻接表存储呢,通常拓扑排序如果使用矩阵存储都是比较稀疏的,比较浪费内存空间,这里还是使用邻接表来存储节点。

    另外,如果图中节点是1,2,3,4,5,6这样的有序编号,我们可以直接用数组,但是如果遇到1,2,88,9999类似不连续跨度很大编号节点,也可以考虑用Map存储映射一下位置。

    那么我们具体的代码思想为:

    ①新建node类,包含节点数值和它的指向节点集合(这里直接用List集合)

    ②初始化一个人node数组,输入/枚举节点之间关系,被指向的节点入度+1!(例如A—>C)那么C的入度+1;

    扫描所有node(这里扫描数组)。将所有入度为0的点加入一个容器栈(队列)中。

    ④当栈(队列)不空的时候,抛出其中任意一个node(只要入度为零可以随便选择顺序)。将node输出,并且node指向的所有节点入度减1。如果某个点的入度被减为0,那么就将它加入栈(队列)

    ⑤重复上述操作,直到栈(队列)为空。

    这里主要是利用栈或者队列储存入度只为0的节点,只需要初次扫描表将入度为0的放入栈(队列)中。

    因为节点之间是有相关性的,一个节点若想入度为零,那么它的前驱节点点肯定在它前入度为0,拆除关联箭头将自己入度减1,在一个有向无环图中总会有大于等于1个入度为0的节点。

    在具体实现上,方式是有多样的,我的这个只是一个简单的演示,效率不一定很高,大家参考一下即可。

    具体实现代码为:

    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Stack;
    
    public class tuopu {
    	static class node
    	{
    		int value;
    		List<Integer> next;
    		public node(int value) {
    			this.value=value;
    			next=new ArrayList<Integer>();
    		}
    		public void setnext(List<Integer>list) {
    			this.next=list;
    		}
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		node []nodes=new node[9];//储存节点
    		int a[]=new int[9];//储存入度
    		List<Integer>list[]=new ArrayList[10];//临时空间,为了存储指向的集合
    		for(int i=1;i<9;i++)
    		{
    			nodes[i]=new node(i);
    			list[i]=new ArrayList<Integer>();
    		}
    		initmap(nodes,list,a);
    		
    		//主要流程
    		//Queue<node>q1=new ArrayDeque<node>();
    		Stack<node>s1=new Stack<node>();
    		for(int i=1;i<9;i++)
    		{
    			//System.out.print(nodes[i].next.size()+" 55 ");
    			//System.out.println(a[i]);
    			if(a[i]==0) {s1.add(nodes[i]);}
    			
    		}
    		while(!s1.isEmpty())
    		{
    			node n1=s1.pop();//抛出输出
    			System.out.print(n1.value+" ");
    			List<Integer>next=n1.next;
    			for(int i=0;i<next.size();i++)
    			{
    				a[next.get(i)]--;//入度减一
    				if(a[next.get(i)]==0)//如果入度为0
    				{
    					s1.add(nodes[next.get(i)]);
    				}
    			}
    		}
    	}
    
    	private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
    		list[1].add(3);
    		nodes[1].setnext(list[1]);
    		a[3]++;
    		list[2].add(4);list[2].add(6);
    		nodes[2].setnext(list[2]);
    		a[4]++;a[6]++;
    		list[3].add(5);
    		nodes[3].setnext(list[3]);
    		a[5]++;
    		list[4].add(5);list[4].add(6);
    		nodes[4].setnext(list[4]);
    		a[5]++;a[6]++;
    		list[5].add(7);
    		nodes[5].setnext(list[5]);
    		a[7]++;
    		list[6].add(8);
    		nodes[6].setnext(list[6]);
    		a[8]++;
    		list[7].add(8);
    		nodes[7].setnext(list[7]);
    		a[8]++;
    		
    	}
    }
    
    

    输出结果

    2 4 6 1 3 5 7 8

    image-20210607163813249
    当然,上面说过用栈和队列都可以!如果使用队列就会得到1 2 3 4 5 6 7 8 的拓扑序列

    至于图的构造,因为没有条件可能效率并不高,算法也可能不太完美,如有优化错误还请大佬指正!

    拓扑排序找环

    前面说到,拓扑排序需要在有向无环图中才能得到一个拓扑序列,但是如果给定一个有向图,怎么知道它是否可以形成一个拓扑序列呢?

    当然是在拓扑排序算法上进行改动,我们在进行拓扑排序会删除所有入度为0的节点,但是如有有环那么删除节点个数就小于所有节点个数,在具体实现上,我们只需要在栈或者队列抛出时候通过一个计数器统计数字即可。

    当然这个问题力扣207有原题可以看看自己代码是否能够ac,问题描述:

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

    在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

    例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
    请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

    分析上面已经给出,不过在具体实现代码的时候比较灵活,不一定非得创建node类,思路上理的清即可。

    实现代码:

    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int indegree[]=new int[numCourses];
            List<Integer> next[]=new ArrayList[numCourses];
            
            for(int i=0;i<numCourses;i++){
                next[i]=new ArrayList();
            }
            for(int i=0;i<prerequisites.length;i++) {
                int preid=prerequisites[i][1];
                int courseid=prerequisites[i][0];
                indegree[courseid]++;//入度加一
                next[preid].add(courseid);//next指向
            }
            Queue<Integer>queue=new ArrayDeque<>();
            for(int i=0;i<numCourses;i++) {//加入入度为0的节点
                if(indegree[i]==0){
                    queue.add(i);
                }
            }
            int nodeNum=0;//判断删除节点数量 入度为0删除 如果删除所有那么返回true
            while (!queue.isEmpty())
            {
                nodeNum++;
                int nodeId=queue.poll();
                for(int i=0;i<next[nodeId].size();i++)
                {
                    int nodeIndex=next[nodeId].get(i);
                    indegree[nodeIndex]--;
                    if(indegree[nodeIndex]==0) {
                        queue.add(nodeIndex);
                    }
                }
            }
            if(nodeNum==numCourses)
                return true;
            return false;
        }
    }
    

    好了,到这里拓扑排序内容讲解完毕,如果有帮助还请大家关注、点赞、在看分享一波,谢谢!

    关于作者:bigsai,专注于Java、数据结构与算法知识分享,微信搜一搜【bigsai】关注这个分享干货的小伙子,欢迎职业规划、学习、考研有疑惑或想法的前来交流。

    展开全文
  • 读懂题目后可以看出拓扑的意思,因为形成环会计算不出表达式的值。所有按照拓扑dfs即可。 使用一个结构体存储一个点:表达式,值,以及一个bool值判断他是否为数字。 比较麻烦的地方便是对表达式的求值,细心模拟...

    题目链接

    分析:

    读懂题目后可以看出拓扑的意思,因为形成环会计算不出表达式的值。所有按照拓扑dfs即可。

    使用一个结构体存储一个点:表达式,值,以及一个bool值判断他是否为数字。

    比较麻烦的地方便是对表达式的求值,细心模拟!!

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 10010;
    struct Node
    {
    	int num;
    	bool is_num;
    	string exp;
    	Node() {num = maxn; is_num = false; exp="";}
    };
    
    int vis[25][15];
    Node node[25][15];
    bool is_circle[25][15];
    bool dfs(int x, int y) {
    	if(is_circle[x][y]) { 
    		node[x][y].is_num = false;
    		return false;
    	}
    	if(vis[x][y]==-1) {
    		node[x][y].is_num = false;
    		is_circle[x][y] = true;
    		return false;
    	}
    	vis[x][y] = -1;//-1表示正在访问
    	string str = node[x][y].exp;
    	int res = 0;
    	int is_plus = 1;
    	for(int i = 0; i < (int)str.length();) {
    		if(str[i]=='+') {
    			i++;
    			is_plus = 1;
    			continue;
    		}
    		if(str[i]=='-') {
    			i++;
    			is_plus = -1;
    			continue;
    		}
    		if(isdigit(str[i])) {
    			int num = 0;
    			while(isdigit(str[i]) && i<(int)str.length()) { 
    				num = num*10 + str[i]-'0';
    				i++;
    			}
    			res += is_plus*num;
    		}
    		else {
    			int x1 = str[i]-'A', y1 = str[i+1]-'0';
    			i += 2;
    			if(dfs(x1,y1)) 
    				res += is_plus*node[x1][y1].num;
    			else {
    				node[x1][y1].is_num = false;
    				is_circle[x1][y1] = true;
    				return false;
    			}
    		}
    	}
    	node[x][y].is_num = true;
    	node[x][y].num = res;
    	vis[x][y] = 0;//访问结束,恢复为0
    	return true;
    }
    
    int main() {
    	freopen("i.txt","r",stdin);
        freopen("o.txt","w",stdout);
    	int m,n;
        while(cin >> m >> n && m && n) {
        	memset(vis, 0, sizeof(vis));
        	memset(is_circle, false, sizeof(is_circle));
        	for(int i = 0; i < m; i++) {
        		for(int j = 0; j < n; j++) {
        			node[i][j].is_num = false;
        			string str;
        			cin >> str;
        			node[i][j].exp = str;
        		}
        	}
        	bool flag = true;
        	for(int i = 0; i < m; i++) {
        		for(int j = 0; j < n; j++) {
        			if(!node[i][j].is_num)
        				dfs(i, j);
        		}
        	}
        	for(int i = 0; i < m; i++) {
        		for(int j = 0; j < n; j++) {
        			if(is_circle[i][j])
        				flag = false;
        		}
        	}
        	if(flag) {
        		cout << " ";
        		for(int i = 0; i < n; i++) 
        			cout << setw(6) << i;
        		cout << endl;
        		for(int i = 0; i < m; i++) {
        			cout << char(i+'A');
        			for(int j = 0; j < n; j++) 
        				cout << setw(6) << node[i][j].num;
        			cout << endl;
        		}
        	}
        	else {
        		for(int i = 0; i < m; i++) {
        			for(int j = 0; j < n; j++) {
        				if(!node[i][j].is_num || node[i][j].num>=maxn)
        				cout << char(i+'A') << j << ": " << node[i][j].exp << endl;
        			}
        		}
        	}
        	cout << endl;
        }
        return 0;
    }
    

     

    展开全文
  • 最全架构师拓扑

    2018-09-19 22:18:05
    史上最全架构师拓扑学习路线图,共勉之.资源分数是意思一下,最低就是1分。原本FREE分享.
  • 拓扑排序

    2020-07-16 16:35:03
    有些事情不是一次就可以完成,分很多个步骤,而且这些步骤是有顺序,也就是说,假设B顺序在A后面,那么你就必须要先完成A再完成B,但是也有些步骤不分顺序,意思是你先做哪一个都是可以。 比如大学课程...

    拓扑排序:有向图顶点的线性排序就是其拓扑排序

    有些事情不是一次就可以完成的,分很多个步骤,而且这些步骤是有顺序的,也就是说,假设B的顺序在A的后面,那么你就必须要先完成A再完成B,但是也有些步骤不分顺序,意思是你先做哪一个都是可以的。
    比如大学的课程,有些课是有先修课的,即需要先学习某个课程。如下图。有些事情不是一次就可以完成的,分很多个步骤,而且这些步骤是有顺序的,也就是说,假设B的顺序在A的后面,那么你就必须要先完成A再完成B,但是也有些步骤不分顺序,意思是你先做哪一个都是可以的
    拓扑排序的思路:
    1、 从 图中选择一个 没有前驱(即入度为0)的顶点并输出。
    2、从图中删除该顶点和所有以它为起点的有向边。
    3、重复 1 和 2 直到当前的图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
    拓扑排序图解:在这里插入图片描述
    拓扑排序代码:

    int in_deg[MAX];
    int ans[MAX];
    int n,m;	//n点数mb边数 
    queue<int> q;
    void topsort()
    {
    	for(int i = 1 ; i<=n;i++){
    		if(in_deg[i]==0){
    			q.push(i);			///把入度为0的点压入队列 
    		} 
    	}
    	int x=0;
    	while(!q.empty()){
    		int u=q.front();		
    		q.pop();
    		int ans[x++]=u;			///记录答案 
    		for(int i = head[u];~i;i=edge[i].next){		///链式向前星存的图 
    			int to=edge[i].to;
    			in_deg[to]--;			///入度减1 
    			if(in_deg[to]==0){
    				q.push(to);			///入度为0压入队列 
    			}
    		}
    	}
    	if(cnt!=n)	cout<<"有环"<<endl;			//ans中必须存n个点否则存在环 
    	else{
    		cout<<ans[0];						///输出其拓扑序 
    		for(int i = 1 ;i<n;i++)
    			cout<<" "<<ans[i];
    		cout<<endl;
    	} 
    }
    
    

    举几道模板题
    HDU 1285 确定比赛名次 http://acm.hdu.edu.cn/showproblem.php?pid=1285
    难点:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;
    解决方案:因为本菜鸡实在太菜了,不会优先队列,然后本菜鸡就想了个O(n^2)的方法,即每次都从1开始到n判断入度循环n次。
    AC代码

    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    int in[505],head[505],vis[505];
    int ans[505];
    int n,m,cnt;
    queue<int> q;
    struct node {
    	int to,next;
    }edge[250005];
    void init()
    {
    	cnt=0;
    	mem(head,-1);
    	mem(in,0);
    	mem(vis,0);
    }
    void addedge(int from,int to){
    	edge[cnt]={to,head[from]};	///有些可能不支持,拆出来写即可。
    	head[from]=cnt++;
    }
    void topsort(){
    	int x=0;
    	while(x<n){	//找到n个数
    		for(int i = 1 ; i<=n;i++){		///每次从1开始
    			if(in[i]==0 && vis[i]==0){	//入度为0且没有进入过队列
    				vis[i]=1;
    				q.push(i);
    				break;					///每次只找一个,为了保证最小的先入队
    			}
    		}
    		int u=q.front();	///删点和边,
    		q.pop();
    		ans[x++]=u;		//存答案
    		for(int i=head[u];~i;i=edge[i].next){
    			int to=edge[i].to;
    			in[to]--;		
    		}
    	}
    	cout<<ans[0];
    	for(int i = 1 ; i<x;i++)
    		cout<<" "<<ans[i];
    	cout<<endl;
    }
    int main()
    {
    	int a,b;
    	while(cin>>n>>m){
    		init();
    		for(int i=0;i<m;i++){
    			cin>>a>>b; 
    			in[b]++;
    			addedge(a,b);
    		}
    		topsort();
    	}
    	return 0;
    }
    

    HDU 2647 http://acm.hdu.edu.cn/showproblem.php?pid=2647
    题目大意,老板要给n个员工发工资,b的工资要比a的工资高(有m对),每个人最少发888元,老板想尽量省钱,问最少发出多少钱方可满足所有员工的需求,如果无法实现输出-1。
    尽量省钱,肯定是a比b多1块钱。无法实现即存在环,a>b>a,所以判断下环就可以了,然后我们就可以开开心心的套模板了。
    在这里插入图片描述
    这题,他输入的 a b 竟然是 b>a,一路模板下来全是 a>b,然后高高兴兴的wa了3次才注意到。
    所以我们反向建个边就好了。
    AC代码

    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define MAX 20004
    #define MAXN 10002
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    int in[MAXN],head[MAXN],money[MAXN];
    int n,m,cnt;
    queue<int> q;
    struct node {
    	int to,next;
    }edge[MAX];
    void init()
    {
    	cnt=0;
    	mem(head,-1);
    	mem(money,0); 
    	mem(in,0);
    	
    }
    void addedge(int from,int to){
    	edge[cnt]={to,head[from]};
    	head[from]=cnt++;
    }
    void topsort(){
    	int x=0;
    	for(int i = 1 ; i<=n;i++){
    		if(in[i]==0 ){
    			q.push(i);			//初始入度为0的点,钱为888
    			money[i]=888; 
    		}
    	}
    	while(q.size()){
    		int u=q.front();
    		q.pop();
    		x++;
    		for(int i=head[u];~i;i=edge[i].next){
    			int to=edge[i].to;
    			in[to]--;
    			if(!in[to]){
    				q.push(to);
    				money[to] = money[u]+1; 
    			}
    		}
    	}
    	if(x!=n)	cout<<"-1"<<endl;
    	else{
    		int ans=0;
    		for(int i = 1;i<=n;i++)
    			ans+=money[i];
    		cout<<ans<<endl;
    	}
    }
    int main()
    {
    	int a,b;
    	while(cin>>n>>m){
    		init();
    		for(int i=0;i<m;i++){
    			cin>>a>>b; 
    			in[a]++;		//a这时入度++
    			addedge(b,a);	//反向建边
    		}
    		topsort();
    	}
    	return 0;
    }
    

    就先写到这里把,小声bb其实是题还没补完。

    展开全文
  • 拓扑结构和几何结构区别

    千次阅读 2020-09-28 17:38:41
    最近在看数据结构中图,里面有一节叫做拓扑排序,不是很明白这个“拓扑”是什么意思,上网搜了一下,有个说法如下,感觉比较通俗易懂。 所谓“拓扑”就是把实体抽象成与其大小、形状无关“点”,而把连接实体...
  • 之前做了剑指offer的“树的子结构”和牛客网算法课“拓扑相同的子树”,发觉这其中还是有些微妙的地方需要注意的,总结如下:树的子结构和树的子树问题:子树的意思是包含了一个结点,就得包含这个结点下的所有节点...
  • 本文我打算用Java实现图论算法中的拓扑排序,并应用拓扑排序安排课程表。课程表就是很常规那种Java学习简单路线图,首先下图就是Java课程学习一个拓扑顺序图: 上面这张图是什么意思呢?黑色字就代表要学习...
  • 拓扑排序问题

    2019-10-04 01:47:59
    无环,即图中没有回路的意思。 2.拓扑排序介绍:在一个表示project的有向图中。用顶点表示活动,用弧表示活动之间的优先关系,这种有向图称为顶点表示活动的网,我们称之为AOV网(Activity On Vertex Network)。AOV...
  • 用于模拟直接网络拓扑的 NS3 扩展 Microsoft 扩展主要位于 src/tocino 中,版权归 Microsoft Corporation 所有。 我们的更改使使用优秀的 NS3 框架模拟直接网络(环、网格、环)成为可能。 模拟网络是无损的、基于 ...
  • 下面到电源三大拓扑中的Boost了,Boost在英文里是提高的意思,从字面就可看出,Boost拓扑就是升压,Boost电路的输出一定是大于输入的。说得无益,直接上图,先来认识一下Boost拓扑结构。    很容易看出,...
  • 网络拓扑

    2019-10-06 12:15:22
    在本地网络中,两个节点被称为“彼此近邻”是什么意思?在海量数据处理中,其主要限制因素是节点之间数据传输速率——带宽很稀缺。这里想法是将两个节点间带宽作为距离衡量标准。 节点距离:两个节点到达...
  • 一、实验拓扑图 二、实验目的 1.全网互通 2.为PC机划分不同vlan 3.运用链路捆绑实现三层交换机之间的通信 ...(和的意思) 设备 网关 链路捆绑接口 链路组号 SW1 192.168.10.254/24 GE0/...
  • 无环,即是图中没有回路的意思拓扑排序介绍 在一个表示工作的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样有向图为顶点表示活动的网,我们称为AOV网(Activity On Vertex Nextwork)。 AOV...
  • DDR走线拓扑

    千次阅读 2019-06-09 10:46:37
    DDR走线拓扑 DDR与SDRAM DDR=Double Data Rate双倍速率,DDR SDRAM=双倍速率同步动态随机存储器,人们习惯称为DDR,其中,...而DDR SDRAM是Double Data Rate SDRAM的缩写,是双倍速率同步动态随机存储器的意思。D...
  • 有向无环图(Directed Acyclic Graph, DAG)是有向图一种,字面意思的理解就是图中没有环。常常被用来表示事件之间驱动依赖关系,管理任务之间调度。拓扑排序是对DAG顶点进行排序,使得对每一条有向边(u, v)...
  • 分层图+虚拓扑

    2020-09-18 15:48:05
    拓扑: Q:虚拓扑是什么意思啊 A:虚拓扑,也称为逻辑拓扑,表征网络节点间业务分布情况 分层图: 详细介绍链接https://blog.csdn.net/qq_40736036/article/details/85041838

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 364
精华内容 145
关键字:

拓扑的意思