6

与えられた問題はhttp://www.spoj.com/problems/TOPOSORT/です 。出力形式は次のように特に重要です。

Print "Sandro fails." if Sandro cannot complete all his duties on the list. 
If there is a solution print the correct ordering, 
the jobs to be done separated by a whitespace. 
If there are multiple solutions print the one, whose first number is smallest, 
if there are still multiple solutions, print the one whose second number is smallest, and so on.

私がやっていることは、単にエッジを逆にして dfs を実行することです。つまり、ジョブ A がジョブ B の前に終了した場合、 B から A への有向エッジがあります。作成した隣接リストをソートし、後で正しい順序で出力できるように、制約のないノードを個別に保存することで順序を維持しています。2 つのフラグ配列が使用されます。1 つは発見されたノードをマークするためのもので、もう 1 つはすべてのネイバーが探索されたノードをマークするためのものです。

今、私の解決策はhttp://www.ideone.com/QCUmKY (重要な機能は訪問機能です) であり、10 のケースで正しく実行された後に WA を与えるため、実行されてからどこが間違っているのかを理解するのは非常に困難です。私が手作業で行ったすべてのテストケースに対して。

4

3 に答える 3

5

ここでの問題は、DFS トポロジカル ソート アルゴリズムが有効なトポロジ ソートを生成することだけが保証されており、辞書編集的に最初のトポロジ ソート (必要なもの) ではないことだと思います。

これを修正できる可能性がある 1 つの方法は、トポロジカル ソートの実行に使用しているアルゴリズムを変更することです。DFS を使用する代わりに、他の標準アルゴリズムを使用することを検討してください。これは、すべてのノードのセットを indegree 0 で維持し、1 つを繰り返し削除して、indegree 0 でノードのセットを更新することによって機能します。プライオリティ キューを使用してノードを選択する場合次数 0 で、反復ごとに最小の数値を使用すると、問題によって与えられた制約を満たすトポロジカル ソートが返されます。

お役に立てれば！

于 2013-07-01T18:14:30.430 に答える
2

この特定の質問では、dfs アルゴリズムがタイムアウトします。いくつかの巧妙なトリックを使用すると、解の複雑さを O(m) にすることができます。すべてのエッジを順番に並べ替えるために使用している並べ替えを削除する必要があります。私はリバース エッジのリストを維持しました。つまり、2 つのエッジ u->v と w->v について、最初にそれらをリスト li[v]->u->w に追加しました。その後、1 から n までトラバースして、修正された有向エッジを作成しましたが、今回は自動的に順番に並んでいます。

とにかく、これはタイムアウトします（私にとってはテストケース12で）。これには、非常に最適化されたアルゴリズムが必要です。templatetypedef で言及されているアルゴリズムは正常に機能します。おそらく、dfs の再帰オーバーヘッドは、dfs アルゴリズムでは少し多すぎます。

アイデアは非常に単純です。これについては、ここで読むことができますhttp://en.wikipedia.org/wiki/Topological_sorting

基本的に、次数がゼロのタスクを完了することができます。タスクが完了したら、すべての出力エッジを削除してすべての内角を更新し、次数がゼロの別のタスクを見つけます。物事を整理するには、プライオリティ キューを使用できます。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int indeg[10005];
int topo[10005];
vector <int> g[10005];
int main(){
        int n,m;
        int cur= 0;
        cin >> n >> m;
        for (int i = 0; i < m; i++){
                int x,y;
                scanf("%d %d" ,&x, &y);
                indeg[y]++;
                g[x].push_back(y);
        }
        priority_queue <int> q;
        for(int i = 1; i <= n; i++)
                if (!indeg[i]) q.push(-1*i);
        while(!q.empty()){
                int nd = -1 * q.top();
                q.pop();
                for(int i = 0; i < g[nd].size(); i++){
                        indeg[g[nd][i]]--;
                        if (!indeg[g[nd][i]])
                                q.push(-1*g[nd][i]);
                }
                topo[cur++] = nd;
        }
        if (cur!= n){
                cout << "Sandro fails." << endl;
                return 0;
        }

        for(int i = 0; i < n-1; i++)
                printf("%d ", topo[i]);
        printf("%d\n", topo[n-1]);


        return 0;
}
于 2013-07-02T19:25:56.323 に答える