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

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>
            久久久亚洲一区| 鲁大师成人一区二区三区| 欧美日韩精品免费观看| 亚洲精品美女在线观看播放| 亚洲欧洲精品成人久久奇米网 | 日韩午夜在线播放| 欧美日韩在线不卡| 欧美中文在线免费| 久久午夜电影| 亚洲伊人网站| 久久精品九九| 亚洲理伦电影| 亚洲一区国产视频| 在线电影欧美日韩一区二区私密| 亚洲第一精品福利| 国产精品久久久久天堂| 卡通动漫国产精品| 欧美日韩一区二区三区在线视频| 午夜精品久久久久久久99热浪潮| 久久久久免费| 国产精品99久久久久久久vr| 性欧美video另类hd性玩具| 亚洲电影免费在线观看| 亚洲视频第一页| 亚洲麻豆国产自偷在线| 国产精品夜夜夜一区二区三区尤| 免费观看亚洲视频大全| 欧美午夜无遮挡| 快she精品国产999| 国产精品福利久久久| 欧美mv日韩mv国产网站| 国产精品人人爽人人做我的可爱| 欧美成熟视频| 国产区欧美区日韩区| 亚洲精品一品区二品区三品区| 国产午夜精品视频| 99国内精品| 亚洲乱码国产乱码精品精| 午夜免费日韩视频| 亚洲性图久久| 欧美激情在线观看| 欧美成ee人免费视频| 国产欧美日韩在线播放| 一本大道久久a久久精二百| 亚洲大胆美女视频| 香蕉乱码成人久久天堂爱免费| 一区二区三区免费观看| 久久嫩草精品久久久精品| 午夜精品久久久久久久蜜桃app| 奶水喷射视频一区| 麻豆成人综合网| 国产一区二区三区在线免费观看| 一本久道久久综合婷婷鲸鱼| 亚洲三级影片| 欧美.com| 亚洲电影在线播放| 亚洲日本va午夜在线影院| 久久婷婷影院| 欧美黄色aa电影| avtt综合网| 在线亚洲精品| 欧美无乱码久久久免费午夜一区| 91久久精品国产91久久| 日韩午夜三级在线| 欧美日韩国产一区二区三区地区| 亚洲区第一页| 亚洲四色影视在线观看| 国产精品久久久999| 亚洲午夜在线| 久久国内精品视频| 狠狠做深爱婷婷久久综合一区| 久久超碰97人人做人人爱| 久久久久久久网站| 亚洲福利一区| 欧美日韩a区| 制服丝袜激情欧洲亚洲| 午夜精品理论片| 国内精品免费午夜毛片| 玖玖视频精品| 日韩视频亚洲视频| 亚洲欧美中文日韩v在线观看| 国产精品天天摸av网| 久久国产精品一区二区三区| 欧美大片在线看免费观看| 亚洲日本久久| 国产精品黄视频| 久久国产精品免费一区| 欧美激情亚洲另类| 亚洲在线不卡| 狠狠色综合一区二区| 欧美精品一线| 欧美一级淫片aaaaaaa视频| 欧美粗暴jizz性欧美20| 亚洲一区二区免费在线| 国产一区二区三区在线观看视频| 欧美mv日韩mv亚洲| 亚洲特级片在线| 欧美电影免费观看高清完整版| 中文一区二区在线观看| 亚洲黄色在线| 午夜一级在线看亚洲| 在线欧美小视频| 国产精品chinese| 久久视频在线免费观看| 日韩小视频在线观看专区| 久久综合激情| 亚洲欧美日韩一区二区三区在线| 在线看欧美日韩| 国产精品免费一区豆花| 欧美成人资源| 欧美在线国产精品| 在线亚洲伦理| 亚洲国内高清视频| 久久三级视频| 性欧美大战久久久久久久久| 日韩视频一区| 亚洲二区免费| 狠狠噜噜久久| 国产精品一区二区三区四区五区| 欧美精品一区二区在线播放| 久久婷婷亚洲| 久久国产精品免费一区| 亚洲七七久久综合桃花剧情介绍| 久久婷婷av| 久久精品99国产精品酒店日本| 亚洲视频在线看| 99re国产精品| 亚洲国产婷婷香蕉久久久久久99| 国产一区二区高清视频| 国产精品麻豆成人av电影艾秋| 欧美精品久久99久久在免费线| 另类图片国产| 久久亚洲一区二区| 久久国产欧美| 久久久www成人免费精品| 亚洲欧美偷拍卡通变态| 亚洲一区中文| 亚洲女爱视频在线| 亚洲女性喷水在线观看一区| 亚洲伊人伊色伊影伊综合网| 一区二区三区免费观看| 一本色道综合亚洲| 国产精品99久久久久久久久| 一区二区免费在线播放| 亚洲性线免费观看视频成熟| 在线亚洲一区观看| 亚洲免费人成在线视频观看| 午夜视频久久久| 久久久久高清| 免费一区二区三区| 欧美精品一区二区三区蜜桃| 欧美日韩一区精品| 国产精品卡一卡二卡三| 国产视频一区二区在线观看| 黄色在线成人| 亚洲国产精品久久久久婷婷老年| 亚洲精品乱码久久久久| 夜夜精品视频一区二区| 久久中文字幕导航| 欧美高清你懂得| 欧美私人网站| 狠狠综合久久| 一区二区精品在线| 香蕉成人啪国产精品视频综合网| 久久久欧美一区二区| 欧美成人午夜激情视频| 亚洲日本欧美天堂| 亚洲专区在线| 免费av成人在线| 欧美日韩蜜桃| 国精品一区二区| 日韩一区二区精品| 久久大逼视频| 亚洲人成小说网站色在线| 亚洲影院在线观看| 模特精品在线| 国产精品综合| 亚洲美女一区| 久久蜜桃资源一区二区老牛 | 亚洲精品自在久久| 午夜在线视频一区二区区别| 美女诱惑黄网站一区| 国产精品99久久久久久久vr| 裸体女人亚洲精品一区| 国产精品久久久久9999吃药| 亚洲成色777777女色窝| 亚洲欧美中文另类| 亚洲国产一区二区a毛片| 欧美一二三区在线观看| 欧美日本一道本| 在线观看欧美日韩| 欧美在线啊v| 亚洲精品视频免费观看| 久久久久一区二区| 国产精品专区h在线观看| 一区二区三区精密机械公司 | 久久高清国产| 亚洲特级片在线| 欧美日韩一区二区三| 亚洲人成亚洲人成在线观看|