青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

poj 1094 Sorting It All Out

Posted on 2009-04-12 23:13 lzmagic 閱讀(1672) 評論(5)  編輯 收藏 引用 所屬分類: OJ
    wa了很多次,終于過了,咔咔~笑一下先。
    第一次很快用拓撲排序把代碼敲出來,提交,wa,仔細分析后,發現忽略了重復邊的情況,插入邊(u, v),如果圖g已經存在了邊(u,v),就不能再增加v的入度。
    很快改過來,提交,還是wa,很無奈,上網看看大牛評論,原來是只要當前輸入數據能“確定唯一”,及時后面輸入數據“有環”,也是判定為“確定唯一”。也就是說,每輸入一條邊,如果判定有結果,忽略后面輸入數據,即使后面輸入數據能改變結果。
    再改,再提交,還是wa,幾度欲放棄之,還是堅持下來了,上google找別人代碼來分析,結果發選只要當前輸入數據“有環”,及時當前輸入數據“不能確定唯一”,也是判定為“有環”。
    把判定順序改過后,提交,終于ac!!!
    呼~~~爽YY中……
#include <iostream>
#include 
<fstream>
#include 
<sstream>
#include 
<string>
#include 
<vector>
#include 
<deque>
#include 
<list>
#include 
<queue>
#include 
<stack>
#include 
<set>
#include 
<map>
#include 
<bitset>
#include 
<iterator>
#include 
<algorithm>
#include 
<numeric>
#include 
<functional>
#include 
<climits>
#include 
<ctime>
#include 
<cstdlib>
#include 
<cctype>
using namespace std;

#define UNSURE 0 // 不能確定 
#define CYCLED 1 // 存在回路
#define SORTED 2 // 已經排序

int n;                            // n :頂點個數 
vector<list<int> > g;           // g :圖 
vector<int> top;                // top :拓撲序列 
vector<int> ins;                // ins :入度 

int Topsort()
{
    
bool unsure(false);
    queue
<int> que;
    vector
<int> cnt(ins.begin(), ins.end());    // 用cnt存儲ins,避免修改ins。 
    for (int j = 0; j < n; ++j)
        
if (cnt[j] == 0) que.push(j);            // 入度為0的頂點入隊。 
    int u;
    list
<int>::iterator it;
    top.clear();    
    
while (!que.empty())
    
{
        
if (que.size() != 1) unsure = true;        // 如果選擇頂點多余1個,不能確定。 
        u = que.front(); que.pop();
        top.push_back(u);
        
for (it = g[u].begin(); it != g[u].end(); ++it)
            
if (--cnt[*it] == 0) que.push(*it);
    }

    
if (top.size() != n) return CYCLED;        // 先判斷是否有環,即使不能確定, 
    if (unsure) return UNSURE;                // 再判斷是否不能確定。 
    return SORTED;         
}


int main()
{
    
int steps, ans;
    
string exp;
    
int m, u, v, i;    
    
    
while (cin >> n >> m, n != 0 || m != 0)    // 2 <= n <= 26
    {
        g.assign(n, list
<int>());
        ins.assign(n, 
0);
        ans 
= UNSURE;
        
for (steps = 0; ans == UNSURE && steps < m; ++steps)
        
{
            cin 
>> exp;
            u 
= int(exp[0- 'A'), v = int(exp[2- 'A');
            
if (find(g[u].begin(), g[u].end(), v) == g[u].end()) // 如果不存在邊(u, v),添加。 
                g[u].push_back(v), ++ins[v];
            ans 
= Topsort(); 
        }

        
for (i = steps; i < m; ++i) cin >> exp; // 處理剩下無用的輸入數據。 
        
        
if (ans == UNSURE) // Output()
            cout << "Sorted sequence cannot be determined." << endl; 
        
else if (ans == CYCLED)
            cout 
<< "Inconsistency found after " << steps << " relations." << endl;
        
else
        

            cout 
<< "Sorted sequence determined after " << steps << " relations: ";
            
for (i = 0; i < n; i++) cout << char('A' + top[i]);
            cout 
<< "." << endl;
        }
 // end Output()
    }

    system(
"pause");
    
return 0;
}


    ps.第一,要仔細看題,第二,還是要仔細看題。

Feedback

# re: poj 1094 Sorting It All Out  回復  更多評論   

2009-04-15 15:34 by brightcoder
期待繼續寫算法,比如通用的那種,算法導論上的

# re: poj 1094 Sorting It All Out  回復  更多評論   

2009-05-21 08:43 by dustman
你寫的方法 跟算法導論上的不一樣

算法導論上的是 DFS完記錄FINISH TIME 然后按遞減順序排序 排完后 檢查是否有沖突就可以判斷有沒環.

我一直沒找到怎么判斷無向圖有環, 還有最小環問題

# re: poj 1094 Sorting It All Out  回復  更多評論   

2009-05-27 23:57 by phidias
為什么我提交了你的程序是WA……

# re: poj 1094 Sorting It All Out  回復  更多評論   

2009-05-28 00:00 by Phidias
在poj上WA,acm上AC了……奇怪……

# re: poj 1094 Sorting It All Out  回復  更多評論   

2009-12-29 22:35 by Turn
原來是這樣判斷不確定的:
if (que.size() != 1) unsure = true; // 如果選擇頂點多余1個,不能確定。
謝謝了
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            在线视频你懂得一区二区三区| 亚洲成人资源| 一区二区三区色| 国产精品theporn88| 欧美亚洲三区| 久久久视频精品| 日韩性生活视频| 亚洲性av在线| 极品尤物av久久免费看| 免费永久网站黄欧美| 欧美国产第二页| 亚洲欧美国产精品专区久久| 亚洲欧美综合v| 亚洲国产精品国自产拍av秋霞| 91久久黄色| 国产日韩精品一区二区三区在线| 亚洲黄一区二区三区| 欧美视频一区二| 国产精品一区一区三区| 99精品欧美一区二区三区综合在线| 亚洲国产成人精品久久久国产成人一区 | 国产精品免费一区豆花| 性色av香蕉一区二区| 久久精品av麻豆的观看方式| 亚洲高清在线观看| 在线一区免费观看| 尤物网精品视频| 亚洲一区三区视频在线观看| 在线观看欧美精品| 亚洲制服欧美中文字幕中文字幕| 国内久久精品| 日韩午夜激情| 亚洲日韩成人| 欧美一区2区视频在线观看 | 亚洲第一黄色| 午夜精品福利在线| 这里只有精品在线播放| 久久久夜色精品亚洲| 午夜精品久久久久久久99黑人| 久久久久99| 欧美一级黄色录像| 欧美精品性视频| 亚洲第一页在线| 狠狠干综合网| 羞羞答答国产精品www一本| 99re热精品| 蜜臀av国产精品久久久久| 久久久一区二区| 国产三级精品在线不卡| 一本久久a久久精品亚洲| 亚洲欧洲日产国产综合网| 久久成人免费日本黄色| 欧美伊人久久| 国产美女精品一区二区三区| 一区二区三区鲁丝不卡| 99精品热视频| 欧美黄色免费| 最近看过的日韩成人| 亚洲黄色在线观看| 欧美成ee人免费视频| 欧美激情五月| 亚洲人www| 欧美极品aⅴ影院| 亚洲人成人99网站| 一区二区三区成人| 国产精品啊v在线| 亚洲中无吗在线| 久久久久久久综合色一本| 国产九九精品| 欧美一区二区视频97| 久久久久天天天天| 在线日韩中文| 欧美精品亚洲精品| 日韩一级精品| 欧美夜福利tv在线| 极品少妇一区二区| 欧美大片免费久久精品三p| 亚洲黄色在线看| 亚洲欧美日韩综合一区| 国产欧美日韩综合精品二区| 欧美在线综合| 亚洲国产精品激情在线观看| 亚洲天堂男人| 国产亚洲制服色| 欧美va天堂在线| 亚洲图片欧洲图片日韩av| 久久精品视频99| 亚洲另类视频| 国产精品一区毛片| 美日韩精品免费观看视频| 亚洲精品视频二区| 久久精品一区四区| 日韩小视频在线观看专区| 国产精品久久久久一区| 久久久久久九九九九| 亚洲激情精品| 欧美中文字幕在线视频| 亚洲人线精品午夜| 国产偷久久久精品专区| 免费日韩av片| 午夜精品福利一区二区三区av| 欧美成人有码| 久久精品国产综合精品| 日韩天堂在线视频| 国产一区视频观看| 欧美深夜福利| 欧美大胆a视频| 欧美自拍偷拍| 亚洲天堂av电影| 亚洲人被黑人高潮完整版| 久久精品一区蜜桃臀影院| 99re8这里有精品热视频免费 | 欧美日韩视频专区在线播放 | 正在播放亚洲| 亚洲国产91色在线| 欧美一区二区三区电影在线观看| 亚洲精品视频啊美女在线直播| 国产欧美日韩综合| 国产精品高潮呻吟久久av无限| 欧美成人一区在线| 六十路精品视频| 久久久国产精品一区| 亚洲欧美99| 亚洲先锋成人| 一区二区三区视频在线播放| 欧美激情第二页| 狼人天天伊人久久| 久久久久久9999| 久久福利一区| 久久精选视频| 久久黄金**| 欧美在线电影| 久久99伊人| 久久久久久九九九九| 欧美有码在线视频| 欧美一区二区私人影院日本| 亚洲一区二区三区在线| 在线一区观看| 亚洲一区二区三区久久| 在线午夜精品自拍| 亚洲一区二区伦理| 亚洲一区二区在线观看视频| 一区二区电影免费观看| 在线亚洲欧美专区二区| 一区二区三区鲁丝不卡| 亚洲午夜黄色| 欧美伊人久久久久久午夜久久久久| 亚洲一区区二区| 亚洲欧美综合另类中字| 久久国产精品一区二区三区| 久久aⅴ国产欧美74aaa| 久久视频免费观看| 美女精品一区| 亚洲国产一区视频| 999在线观看精品免费不卡网站| 日韩视频在线观看免费| 亚洲一级在线观看| 久久国内精品视频| 免播放器亚洲| 国产精品高精视频免费| 国产欧美日韩精品在线| 尤物yw午夜国产精品视频| 亚洲精华国产欧美| 亚洲欧美一区二区精品久久久| 欧美专区亚洲专区| 你懂的国产精品永久在线| 最近看过的日韩成人| 一本一本大道香蕉久在线精品| 亚洲欧美清纯在线制服| 美女91精品| 国产精品久久久久毛片大屁完整版 | 韩国一区二区三区美女美女秀| 亚洲国产精品黑人久久久| 亚洲视频一区二区在线观看| 久久国产日本精品| 欧美国产先锋| 亚洲尤物在线| 欧美高清不卡在线| 国产区日韩欧美| 99av国产精品欲麻豆| 久久精品99国产精品酒店日本| 亚洲国产99精品国自产| 亚洲欧美日韩综合一区| 欧美大胆人体视频| 国产一区二区在线观看免费| 亚洲人成在线影院| 久久久久**毛片大全| 亚洲人成啪啪网站| 久久亚洲综合色一区二区三区| 国产精品电影网站| 亚洲美女电影在线| 美女国产一区| 性做久久久久久久免费看| 欧美深夜福利| 99在线精品视频| 欧美大片一区| 久久久久国色av免费看影院| 国产精品久久久久久久久| 亚洲精选视频在线| 欧美激情影音先锋|