查看Sgu/230的源代码 ←Sgu/230


[[分类:拓扑排序]]
==摘要==
{{信息题|Weighings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}230|1|100|无解情况,数组太小|0|time=2015-2-18 00:08:13}}
（AC 1035）
==题意==
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>：
    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，这题恶心在各种细节。
#题目要求"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>
#由m，n范围容易知道图是十分稠密的，可能出现重边。邻接矩阵可能会有更好的复杂度。而若使用邻接链表，数组要开大一点。
==代码==
{{折叠|230.cpp代码已折叠
|<pre>
#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;
}
</pre>
|sgu230}}
==参考资料和拓展阅读==
<references/>