P1983-车站分级

Myth丶恋晨 2023-06-01 08:55 26阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define pb push_back
     4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
     5 #define INF 100000003
     6 #define ll long long
     7 inline ll read()
     8 {
     9     ll ans = 0;
    10     char ch = getchar(), last = ' ';
    11     while(!isdigit(ch)) last = ch, ch = getchar();
    12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    13     if(last == '-') ans = -ans;
    14     return ans;
    15 }
    16 inline void write(ll x)
    17 {
    18     if(x < 0) x = -x, putchar('-');
    19     if(x >= 10) write(x / 10);
    20     putchar(x % 10 + '0');
    21 }
    22 int n,m;
    23 int a[1003][1003];
    24 int in[1003];
    25 int ans = 1;
    26 vector<int> G[1003];
    27 void toposort()
    28 {
    29     queue<int> q;
    30     _for(j,1,n+1)
    31     {
    32         int sum = 0;
    33         _for(i,1,n+1)
    34         if(a[i][j])
    35             G[i].pb(j),sum ++;
    36         in[j] = sum;
    37     }
    38 
    39     _for(i,1,n+1)
    40         if(!in[i])
    41             q.push(i);
    42     q.push(0);
    43     while(q.size()!=1)
    44     {
    45         int x = q.front();
    46         q.pop();
    47         if(!x)
    48         {
    49             q.push(0);
    50             ans ++;
    51             continue;
    52         }
    53         _for(i,0,G[x].size())
    54         {
    55             in[G[x][i]] --;
    56             if(!in[G[x][i]])
    57                 q.push(G[x][i]);
    58         }
    59     }
    60 }
    61 int main()
    62 {
    63     n = read(), m = read();
    64     _for(i,1,m+1)
    65     {
    66         int t = read();
    67         set<int> s;
    68         int st,ed;
    69         _for(j,1,t+1)
    70         {
    71             int k = read();
    72             if(j==1)
    73                 st = k;
    74             else if(j==t)
    75                 ed = k;
    76             s.insert(k);
    77         }
    78         _for(j,st+1,ed)
    79             if(!s.count(j))
    80                 for(auto p:s)
    81                     a[j][p] = 1;
    82     }
    83     toposort();
    84     write(ans);
    85     return 0;
    86 }

转载于:https://www.cnblogs.com/Asurudo/p/11528274.html