Logo CloudLunar

“Sgu/230”的版本间的差异

（以“ 分类:拓扑排序 ==摘要== {{信息题|Weighings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}230|1|100|无解情况,数组太小|0|time=2015-2-1...”为内容创建页面）
 
小 （→‎题解： 排版）
第6行： 第6行：
 
==题意==
 
==题意==
 
n个盒子，每个盒子装有一个硬币（面值分别为1~n），给出若干组盒子p的硬币面值小于盒子q的信息，求解每个盒子装有的硬币数目。
 
n个盒子，每个盒子装有一个硬币（面值分别为1~n），给出若干组盒子p的硬币面值小于盒子q的信息，求解每个盒子装有的硬币数目。
−
==题解==
 
 
将盒子抽象为图，很容易知道这是一道拓扑排序裸题，拓扑排序最简单的做法是dfs，摘录一段伪代码<ref>http://blog.csdn.net/dm_vincent/article/details/7714519</ref><ref>http://en.wikipedia.org/wiki/Topological_sorting</ref>：
 
将盒子抽象为图，很容易知道这是一道拓扑排序裸题，拓扑排序最简单的做法是dfs，摘录一段伪代码<ref>http://blog.csdn.net/dm_vincent/article/details/7714519</ref><ref>http://en.wikipedia.org/wiki/Topological_sorting</ref>：
−
    L ← 存放答案的数组
+
L ← 存放答案的数组
−
    S ← 没有出度的节点集合
+
S ← 没有出度的节点集合
−
    foreach 节点 n in S do
+
foreach 节点 n in S do
−
        visit(n)  
+
    visit(n)  
−
    function visit(节点 n)
+
function visit(节点 n)
−
        if n从未被访问 then
+
    if n从未被访问 then
−
            标记n为访问过
+
        标记n为访问过
−
            foreach 节点m（存在m到n的边）do
+
        foreach 节点m（存在m到n的边）do
−
                visit(m)
+
            visit(m)
−
            将n添加到L
+
        将n添加到L
 
由于dfs的性质，回溯时顺序一定是从最深处的点向浅处的点，也就满足了拓扑序。
 
由于dfs的性质，回溯时顺序一定是从最深处的点向浅处的点，也就满足了拓扑序。
−
 
−
 
 
However，这题恶心在各种细节。
 
However，这题恶心在各种细节。
−
#题目要求"where the K-th number means the type of coin in K-th box"而非"where the K-th number means box whit k-th coins type"，并不是输出拓扑序，要转换一下；<ref>http://acm.sgu.ru/forum_action.php?id=4321</ref>
+
#题目要求"where the K-th number means the type of coin in K-th box"而非"where the K-th number means box whit k-th coins type"，并不是输出拓扑序，要转换一下<ref>http://acm.sgu.ru/forum_action.php?id=4321</ref>；
−
#在多解的情况下，题目要求输出随意解而非no solution，可能出现非连通图等情况，但依旧符合要求（e.g.输入"3 0"，输出1~3任意组合皆可）；<ref>http://acm.sgu.ru/forum_action.php?id=3716</ref>
+
#在多解的情况下，题目要求输出随意解而非no solution，可能出现非连通图等情况，但依旧符合要求（e.g.输入"3 0"，输出1~3任意组合皆可）<ref>http://acm.sgu.ru/forum_action.php?id=3716</ref>；
 
#由m，n范围容易知道图是十分稠密的，可能出现重边。邻接矩阵可能会有更好的复杂度。而若使用邻接链表，数组要开大一点。
 
#由m，n范围容易知道图是十分稠密的，可能出现重边。邻接矩阵可能会有更好的复杂度。而若使用邻接链表，数组要开大一点。
 +
 
==代码==
 
==代码==
 
{{折叠|230.cpp代码已折叠
 
{{折叠|230.cpp代码已折叠

2015年2月18日 (三) 00:12的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
Weighings ★☆☆☆☆ 答案正确 100 2015-2-18 00:08:13 无解情况,数组太小（0）

（AC 1035）

题意

n个盒子，每个盒子装有一个硬币（面值分别为1~n），给出若干组盒子p的硬币面值小于盒子q的信息，求解每个盒子装有的硬币数目。 将盒子抽象为图，很容易知道这是一道拓扑排序裸题，拓扑排序最简单的做法是dfs，摘录一段伪代码[1][2]：

显示/移除行号
  1. L ← 存放答案的数组
  2. S ← 没有出度的节点集合
  3. foreach 节点 n in S do
  4.     visit(n) 
  5. function visit(节点 n)
  6.     if n从未被访问 then
  7.         标记n为访问过
  8.         foreach 节点m（存在m到n的边）do
  9.             visit(m)
  10.         将n添加到L

由于dfs的性质，回溯时顺序一定是从最深处的点向浅处的点，也就满足了拓扑序。 However，这题恶心在各种细节。

  1. 题目要求"where the K-th number means the type of coin in K-th box"而非"where the K-th number means box whit k-th coins type"，并不是输出拓扑序，要转换一下[3]；
  2. 在多解的情况下，题目要求输出随意解而非no solution，可能出现非连通图等情况，但依旧符合要求（e.g.输入"3 0"，输出1~3任意组合皆可）[4]；
  3. 由m，n范围容易知道图是十分稠密的，可能出现重边。邻接矩阵可能会有更好的复杂度。而若使用邻接链表，数组要开大一点。

代码

230.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #define dsi(n) int n;scanf("%d",&n)
  3. #define si(n) scanf("%d",&n)
  4. #define f(i,n) for(int i=1;i<=n;++i)
  5. #define fi(n) f(i,n)
  6. #define f0(i,n) for(int i=0;i!=n;++i)
  7. #define fd(i,n) for(int i=n;i>=1;--i)
  8. #define ci const int&
  9. #define c(x) const x&
  10. int map[112][1112]={};//fixed:数组不够大//
  11. bool visited[112]={};
  12. int outI=0,out[112],n,m;
  13. void dfs(ci _at)
  14. {
  15.     if(visited[_at])
  16.         return;
  17.     visited[_at]=1;
  18.     f(i,map[_at][0])
  19.         dfs(map[_at][i]);
  20.     out[_at]=outI--;//fixed:修改输出//
  21. }
  22. int main()
  23. {
  24.     si(n);si(m);
  25.     outI=n;
  26.     f(i,m)
  27.     {
  28.         dsi(a);dsi(b);
  29.         map[a][++map[a][0]]=b;
  30.     }
  31.     fd(i,n)
  32.         dfs(i);
  33.     f(i,n)
  34.         f(j,map[i][0])
  35.             if(out[i]>=out[map[i][j]])
  36.             {
  37.                 printf("No solution");//fixed:修改无解条件，多解不代表无解//
  38.                 return 0;
  39.             }
  40.     f(i,n)
  41.         printf("%d ",out[i]);
  42.     return 0;
  43. }

参考资料和拓展阅读

  1. 跳转 ↑ http://blog.csdn.net/dm_vincent/article/details/7714519
  2. 跳转 ↑ http://en.wikipedia.org/wiki/Topological_sorting
  3. 跳转 ↑ http://acm.sgu.ru/forum_action.php?id=4321
  4. 跳转 ↑ http://acm.sgu.ru/forum_action.php?id=3716
取自“https://blog.CloudLunar.com/index.php?title=Sgu/230&oldid=1163”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]