HDU 1258 链接:click here
HDU 3342 链接:click here
题意:
确定比赛名次
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14142 Accepted Submission(s): 5667
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
4 3 1 2 2 3 4 3
1 2 4 3
基础的拓扑排序应用:
/* 拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
*/
代码:
//HDU 1285 确定比赛名次 #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int maxn =550; int G[maxn][maxn]; int indegree[maxn]; int V,m; bool g[maxn]; void AOV_topsort( ) { int flag = 1; for( int i=1 ; i<V+1 ; i++ ) { for( int j=1 ; j<V+1 ; j++ ) { if(indegree[j] == 0 ) { if(i!=V) printf("%d ",j); else printf("%d\n",j); indegree[j]--; for(int k=1 ; k<V+1; k++ ) { if(G[j][k] == 1 ) { indegree[k]--; } } break; } } } } int main() { while(cin>>V>>m) { memset(G ,0 ,sizeof(G) ); memset(g,false,sizeof(g) ); memset(indegree ,0,sizeof(indegree) ); int a,b; for( int i=0 ; i<m ; i++ ) { scanf("%d%d",&a,&b); if(G[a][b]==0) { G[a][b]=1; indegree[b]++; } } AOV_topsort( ); } return 0; }
Legal or Not
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5041 Accepted Submission(s): 2311
someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are
too many masters and too many prentices, how can we know whether it is legal or not?
We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian
is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.
Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.
means x is y's master and y is x's prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.
If it is legal, output "YES", otherwise "NO".
3 2 0 1 1 2 2 2 0 1 1 0 0 0
YES NO
【解题思路】
跟上一题思路一样,注意判重
代码:
/* 拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止. */ //HDU 3342 Legal or Not #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int maxn =550; int G[maxn][maxn]; int indegree[maxn]; int V,m; bool g[maxn]; void AOV_topsort( ) { int flag = 1; for( int i=1 ; i<V+1 ; i++ ) { for( int j=0 ; j<V ; j++ ) { if(indegree[j] == 0 ) { if(g[j]==0) { g[j]=1; indegree[j]--; for(int k=0 ; k<V; k++ ) { if(G[j][k] == 1 ) { indegree[k]--; } } } } } } for(int i=0 ; i<V ; i++ ) if(indegree[i]> 0) { flag = 0; break; } if(flag==0) puts("NO"); else puts("YES"); } int main() { while(cin>>V>>m&&V&&m) { memset(G ,0 ,sizeof(G) ); memset(g,false,sizeof(g) ); memset(indegree ,0,sizeof(indegree) ); int a,b; for(int i=0 ; i<m ; i++ ) { cin>>a>>b; if(G[a][b]==0) { G[a][b]=1; indegree[b]++; } } int flag = 0; for(int i=0; i<V; i++) { if(indegree[i]==0) { flag = 1; break; } } if(flag==0) puts("NO"); else AOV_topsort( ); } return 0; }