点击打开链接
模板
/* 输入：n m ，n表示有多少人，m表示有多少对关系 x y，表示，x是y的上级 输出：最低工资 ，无解输出-1 */ #include<cstdio> #include<queue> #include<algorithm> using namespace std; #define fi first #define se second int in[105]; //入度 vector<int> edge[105]; int n,m; int topo() { int ans = 0; //pair : 第一个存点，第二个存等级 queue<pair<int,int> > Q; for (int i = 1 ; i <= n ; i++) //统计入度为0的点 { if (in[i] == 0) { Q.push(make_pair(i,0)); in[i] = -1; //表示点已经取走 } } while (!Q.empty()) { int pos = Q.front().fi; int base = Q.front().se; ans = 1000 + base; //取出点以后计算工资 Q.pop(); for (int i = 0 ; i < edge[pos].size() ; i++) //查找与之相连的边，删除并更新入度 { int ne = edge[pos][i]; in[ne]--; if (in[ne] == 0) { Q.push(make_pair(ne,base+1)); in[ne] = -1; //取走 } } } for (int i = 1 ; i <= n; i++) //最后一次搜索图，判断是否存在环 { if (in[i] != -1) return -1; } return ans; } int main() { scanf ("%d%d",&n,&m); for (int i = 1 ; i <= n ; i++) { in[i] = 0; edge[i].clear(); } for (int i = 1 ; i <= m ; i++) { int x,y; scanf ("%d%d",&x,&y); in[x]++; edge[y].push_back(x); } printf ("%d\n",topo()); return 0; } /* 8 8 7 8 5 7 4 5 5 6 3 5 2 3 2 4 2 1 */有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 Input 输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。 Output 给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。 其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。 Sample Input 4 3 1 2 2 3 4 3 Sample Output 1 2 4 3
#include<cstdio> #include<queue> #include<algorithm> #include<vector> #include<cstring> using namespace std; vector<int > edge[506]; int in[506]; int n,m; int a[506][506]; void topo() { int ans=0;int i; int t[506]; while(1) { for(i=1;i<=n;i++) { if(in[i]==0) { t[ans]=i; ans++; in[i]=-1; break; } } if(i==n+1) break; for(int j=1;j<=n;j++) { if(a[i][j]==1) { in[j]--; a[i][j]=0; } } } for(i=0;i<ans-1;i++) printf("%d ",t[i]); printf("%d\n",t[i]); } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { in[i]=0; } memset(a,0,sizeof(a)); for(int i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); if(a[x][y]==0) { in[y]++; a[x][y]=1; } } topo(); } return 0; }
