(以“ 分类:拓扑排序 ==摘要== {{信息题|Weighings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}230|1|100|无解情况,数组太小|0|time=2015-2-1...”为内容创建页面)
 
题意: 排版
 
(未显示1个用户的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]

L ← 存放答案的数组
S ← 没有出度的节点集合
foreach 节点 n in S do
    visit(n) 
function visit(节点 n)
    if n从未被访问 then
        标记n为访问过
        foreach 节点m(存在m到n的边)do
            visit(m)
        将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代码已折叠
展开折叠内容
#include<cstdio>
#define dsi(n) int n;scanf("%d",&n)
#define si(n) scanf("%d",&n)
#define f(i,n) for(int i=1;i<=n;++i)
#define fi(n) f(i,n)
#define f0(i,n) for(int i=0;i!=n;++i)
#define fd(i,n) for(int i=n;i>=1;--i)
#define ci const int&
#define c(x) const x&
int map[112][1112]={};//fixed:数组不够大//
bool visited[112]={};
int outI=0,out[112],n,m;
void dfs(ci _at)
{
    if(visited[_at])
        return;
    visited[_at]=1;
    f(i,map[_at][0])
        dfs(map[_at][i]);
    out[_at]=outI--;//fixed:修改输出//
}
int main()
{
    si(n);si(m);
    outI=n;
    f(i,m)
    {
        dsi(a);dsi(b);
        map[a][++map[a][0]]=b;
    }
    fd(i,n)
        dfs(i);
    f(i,n)
        f(j,map[i][0])
            if(out[i]>=out[map[i][j]])
            {
                printf("No solution");//fixed:修改无解条件,多解不代表无解//
                return 0;
            }
    f(i,n)
        printf("%d ",out[i]);
    return 0;
}

参考资料和拓展阅读

  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

著作权声明[编辑]

关于[编辑]