ZOJ Problem Set - 1060 Sorting It All Out

這題終于過了~~搞了很久的題啊~~N久啊~~

過了真他媽的爽啊~~

整理下思路~

1、邊輸入邊判斷是否沖突，這是我今天搞的最久的操作。一開始的做法是輸入A<B,就隻判斷所有比A小的數要小于B，其實還有一些情況也會出現的，我也舉不出例子，但是肯定這是會遺漏某些情況的做法。後來改成全部的A<B都進行處理！如果出現沖突則記錄起來。

有的人了解成判斷是否存在回路的方法也可以，一開始我的思路就是這樣的，然後用dfs（）判斷一下，發現有些資料會坑爹地循環。也可以用傳遞閉包的算法做。

2、用數組來記錄第幾個操作。要拓撲排序的話，如果每次的輸入都排一次那就太浪費時間，有可能會TLE。是以先把操作數記錄起來，最後一次拓撲排序找出最後的順序，然後按照順序找出最大的操作數，就是結果啦！

3、拓撲排序~這裡我用我自己的做法拓撲~ 不多說。

這題要是沒有poj ,discuss 裡神牛的測試資料的話，搞不出什麼頭緒~

http://poj.org/showmessage?message_id=133905

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <queue>
#include <stack>
using namespace std;

int mp[27][27];
bool cot[27][27];
bool top[27][27];
int in[27];
int main()
{
    int i,j,n,m;
    string str;
    int f1,f2,f3;
    //freopen("a.txt","r",stdin);
   // freopen("b.txt","w",stdout);
    while(cin>>n>>m)
    {
        if(n==0&&m ==0) break;
        memset(mp,0,sizeof(mp));
        memset(cot,0,sizeof(cot));
        memset(top,0,sizeof(top));
        memset(in,0,sizeof(in));
        f1 = -1;f2 = -1;f3 = -1;
        for(i = 1;i <= m;i ++)
        {
            cin>>str;
            if(cot[str[2]-'A'][str[0]-'A'] == 1) {f1 = i;continue;}
            cot[str[0]-'A'][str[2]-'A'] = 1;
            if(mp[str[0]-'A'][str[2]-'A']==0){mp[str[0]-'A'][str[2]-'A'] = i;top[str[0]-'A'][str[2]-'A'] = 1;}
            for(int ii = 0;ii < n;ii ++){
            for(j = 0;j < n;j ++)
            {
                if(cot[ii][j]){
                for(int  k = 0;k < n;k ++)
                {
                    if(cot[k][ii]) cot[k][j] = 1;
                }
                }
            }
            }
        }

        string ans = "";
            int c =0,pos;
        for(i = 0;i < n;i ++)
        {
            for(j = 0;j < n;j ++)
            {
                if(top[j][i]) in[i] ++;
            }
        }
        //cout<<f2<<endl;
        for(i = 0;i < n;i ++)
        {
            c = 0;
            for(j = 0;j < n;j ++)
            {
                if(in[j] == 0) {c ++;pos = j;}
            }
            if(c > 1) {f2 = 1;break;}
            else if(c == 0) {f2 = 1;break;}
            else
            {
                ans += char(pos+'A');
                in[pos] = -1;
                for(int k =0;k < n;k ++)
                {
                    if(top[pos][k]) in[k] --;
                }
            }
        }
        if(f2==-1)
        {
            int len = ans.size();
            int ans1 = 0;
            for(i = 1;i < len;i ++)
            {
                if(mp[ans[i-1]-'A'][ans[i]-'A']>ans1) ans1 =mp[ans[i-1]-'A'][ans[i]-'A'];
            }
            if(f1 != -1){
                if(ans1 < f1)
            cout<<"Sorted sequence determined after "<<ans1<<" relations: "<<ans<<"."<<endl;
            else cout<<"Inconsistency found after "<<f1<<" relations."<<endl;
            }else{
            cout<<"Sorted sequence determined after "<<ans1<<" relations: "<<ans<<"."<<endl;
            }
        }
        else
        {
            if(f1 != -1) cout<<"Inconsistency found after "<<f1<<" relations."<<endl;
            else cout<<"Sorted sequence cannot be determined."<<endl;
        }


    }

}