Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 743 Accepted Submission(s):
347
Special Judge
析:n个城市,每一对城市之间有一条有向边连接,现在开始发展每一个城市,要求下一个要发展的城市到之前已经被发展的城市之间不超过两条边,即要么直接相连,要么中间可间隔一条边。要求输出发展顺序,不满足输出-1
每对点间都存在一条边,为竞赛图,容易想到拓扑排序,但是要逆着排序,以入度最大的为起点拓扑一下
#include <queue> #include <math.h> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #define ll long long using namespace std; const int N = 505; int t, n, m, ans; int in[N], res[N]; char str[N]; void solve(){ ans = n; int flag = 1; while(flag){ flag = 0; int iMax = -1; for(int i = 1; i <= n; i ++){ if(iMax < in[i]){ iMax = in[i]; flag = 1; } } for(int i = 1; i <= n; i ++){ if(iMax == in[i]){ res[ans--] = i; in[i] = -2; } } } } int main(){ while(scanf("%d", &n) && n){ fill(in, in+n+1, 0); for(int i = 1; i <= n; i ++){ scanf("%s", str+1); for(int j = 1; j <= n; j ++){ t = str[j]-‘0‘; if(t){ in[j] ++; } } } solve(); for(int i = 1; i < n; i ++){ printf("%d ", res[i]); } printf("%d\n", res[n]); } return 0; }
原文:https://www.cnblogs.com/microcodes/p/12827331.html