被一道普及组的题卡了这么长时间,不开心。调了两三天,发现cnt=0;放错位置了。
至于原题,COGS
经(简)典(单)的拓扑排序,数据范围还这么小。。。
#include
#include
#include
#include
#include
using namespace std;
queue q;
int n, m, in[1005], b[1005],level;
bool map[1005][1005], a[1005];
inline int get_num()
{
int ans = 0;
char tmp;
tmp = getchar();
while (tmp > '9' || tmp < '0') tmp = getchar();
while (tmp = '0')
{
ans = ans * 10 + tmp - 48;
tmp = getchar();
}
return ans;
}
int main()
{
freopen("level2013.in", "r", stdin);
freopen("level2013.out", "w", stdout);
int si, tmp, cnt;
n = get_num();
m = get_num();
for (int i = 1; i <= m; i++)
{
cnt = 0;
si = get_num();
memset(a, 0, sizeof(a));
for (int j = 1; j <= si; j++)
{
tmp = get_num();
b[++cnt] = tmp;
a[tmp] = true;
}
for (int j = b[1]; j <= b[cnt]; j++)
{
if (!a[j])
{
for (int k = 1; k <= cnt; k++)
{
if (!map[j][b[k]])
{
map[j][b[k]] = 1;
in[b[k]]++;
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
if (!in[i])
q.push(i);
}
while (!q.empty())
{
si = q.size();
level++;
for (int i = 1; i <= si; i++)
{
int ti = q.front();
q.pop();
for (int j = 1; j <= n; j++)
{
if (map[ti][j])
{
in[j]--;
if (!in[j])
q.push(j);
}
}
}
}
cout << level << "\n";
return 0;
}
看看你为了减小常数就喜欢用读入优化
这样非常和谐对不对。。