Sgu/230 2015年2月18日 (三) 00:10云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

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

（AC 1035）

题意

n个盒子，每个盒子装有一个硬币（面值分别为1~n），给出若干组盒子p的硬币面值小于盒子q的信息，求解每个盒子装有的硬币数目。

题解

将盒子抽象为图，很容易知道这是一道拓扑排序裸题，拓扑排序最简单的做法是dfs，摘录一段伪代码：

   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"，并不是输出拓扑序，要转换一下；
2. 在多解的情况下，题目要求输出随意解而非no solution，可能出现非连通图等情况，但依旧符合要求（e.g.输入"3 0"，输出1~3任意组合皆可）；
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; }