（以“ 分类:拓扑排序 ==摘要== {{信息题|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 ← 存放答案的数组 | |
| − | + | 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的性质，回溯时顺序一定是从最深处的点向浅处的点，也就满足了拓扑序。 | 由于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" | + | #题目要求"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~ | + | #在多解的情况下，题目要求输出随意解而非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代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| Weighings | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-18 00:08:13 | 无解情况,数组太小（0） |
（AC 1035）
n个盒子，每个盒子装有一个硬币（面值分别为1~n），给出若干组盒子p的硬币面值小于盒子q的信息，求解每个盒子装有的硬币数目。 将盒子抽象为图，很容易知道这是一道拓扑排序裸题，拓扑排序最简单的做法是dfs，摘录一段伪代码[1][2]：
CloudLunarL ← 存放答案的数组
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，这题恶心在各种细节。
| 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;
}
|