題目鏈接：點擊查看

題目大意：給出N個點以及M個比較關系，問在第幾個數字可以確定出唯一的序列，或者判斷出矛盾的序列，或者最后也無法確定出一個唯一的序列

題目分析：關于這個題目可以直接分類討論，可以直接用拓撲排序判環，判斷是否有唯一確定的順序，這里我用floyd寫了一下，可以直接傳遞閉包，然后根據題目的條件來判斷是否有唯一答案，在確定了唯一答案之后就可以跑一邊拓撲序輸出答案了

有個小坑需要注意一下，每次拓撲序或者傳遞閉包判斷的過程中，如果判斷出肯定無序，不要著急返回，因為矛盾的優先級要高于無序，無序的結果要等全部答案都判斷完畢后再返回

代碼：

拓撲排序：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=50;bool maze[N][N];int num[N];int ans[N];//存結果 int n,t,m;int toposort() {int cnt=0; int flag=1;int temp[N];for(int i=1;i<=n;i++)//備份入度 {temp[i]=num[i];}for(int i=1;i<=n;i++)//n個數 {int m=0;//存入度為零的個數int pos; //記錄位置 for(int j=1;j<=n;j++) //遍歷所有點 {if(temp[j]==0){pos=j;m++;}}if(m==0)//有環return 0;else if(m>1)//無序，但必須繼續遍歷，查找是否有環存在 flag=-1;ans[cnt++]=pos;temp[pos]=-1;for(int j=1;j<=n;j++)//將入度為0的點移除，并將所有與此點相連的點入度減一{if(maze[pos][j])temp[j]--;} }return flag; }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF&&n+m){char s[5];bool ok=false;memset(maze,false,sizeof(maze));memset(num,0,sizeof(num));for(int i=1;i<=m;i++){scanf("%s",s);if(ok)continue;int u=s[0]-'A'+1;int v=s[2]-'A'+1;maze[u][v]=true;num[v]++;int flag=toposort();if(flag==1){ok=true;printf("Sorted sequence determined after %d relations: ",i);for(int i=0;i<n;i++)putchar(ans[i]+'A'-1);putchar('.');cout<<endl;}else if(flag==0){ok=true;printf("Inconsistency found after %d relations.\n",i);}}if(!ok)printf("Sorted sequence cannot be determined.\n");}return 0; }

floyd傳遞閉包+拓撲排序：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=30;int n,m;int maze[N][N];//maze[a][b]:a<bint temp[N][N];int du[N];bool vis[N];int cal() {for(int i=0;i<n;i++)for(int j=0;j<n;j++)temp[i][j]=maze[i][j];for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)temp[i][j]|=temp[i][k]&temp[k][j];bool flag=true;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j&&temp[i][j]==temp[j][i]){if(temp[i][j]==1)//矛盾return 2;else//無法確定 flag=false;}return flag; }void print() {memset(vis,false,sizeof(vis));queue<int>q;string ans;for(int i=0;i<n;i++)if(!du[i]){q.push(i);vis[i]=true;}while(q.size()){int cur=q.front();q.pop();ans+=char(cur+'A');for(int i=0;i<n;i++){if(vis[i])continue;if(maze[cur][i])du[i]--;if(!du[i]){q.push(i);vis[i]=true;}}}printf("%s",ans.c_str()); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF&&n+m){memset(maze,0,sizeof(maze));memset(du,0,sizeof(du));bool flag=false;for(int i=1;i<=m;i++){char s[5];scanf("%s",s);if(flag)continue;maze[s[0]-'A'][s[2]-'A']=1;du[s[2]-'A']++;int ans=cal();if(ans==1){printf("Sorted sequence determined after %d relations: ",i);print();printf(".\n");flag=true;}if(ans==2){printf("Inconsistency found after %d relations.\n",i);flag=true;}}if(!flag)printf("Sorted sequence cannot be determined.\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 1094 Sorting It All Out(拓扑排序+floyd传递闭包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。