社区讨论

求助大神~

P3183[HAOI2016] 食物链参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6ma974
此快照首次捕获于
2025/11/20 07:11
4 个月前
此快照最后确认于
2025/11/20 07:11
4 个月前
查看原帖
为什么第七个点会TLE(好像被数据卡掉了)
CPP
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int max_n = 100007;
const int max_m = 200007;

struct EDGE
{
    int to;
    int next;
}edge[max_m];
int n, m;
int into[max_n];
int edge_size = 0;
int head[max_n];
int stack[max_n];
bool vis[max_n];
int anss = 0;
int ans[max_n];
int top = 0;
template<class T>void read(T &x)
{
    int f = 0; x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = f? -x : x;
}
template<class T>void write(T x)
{
    if(x < 0) x = -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template<class T>T Max(T a, T b){return a > b? a : b;}
void add(int u, int v)
{
    edge[++edge_size].next = head[u];
    edge[edge_size].to = v;
    head[u] = edge_size;
}

void init();
void topsort();

int main()
{
//    freopen("in.txt","r",stdin);
    init();
    topsort();
    for(int i = 1; i <= n; i++) if(!head[i]) anss += ans[i];
    write(anss);
    return 0;
}

void init()
{
    read(n);read(m);
    for(int i = 1; i <= m; i++)
      {
          int x, y;
          read(x);read(y);
          add(x, y);
          vis[x] = vis[y] = 1;
          into[y]++;
      }
}

void topsort()
{
    int jl = 0;
    int num = 0;
    int jishu = 0;
    for(int i = 1; i <= n; i++) jl += (!vis[i]), ans[i] += (into[i] == 0 && vis[i]);
    while(n != num + jl)
      {
          jishu++;
          if(jishu == 1000) write(2), exit(0);
          for(int i = 1; i <= n; i++)
            {
                  if(into[i] == 0 && vis[i])
                    {
                          into[i] = -1;
                          stack[++top] = i;
                          num++;
                }
          }
        while(top)
          {
              int now = stack[top--];
              for(int i = head[now]; i; i = edge[i].next)
                {
                      int temp = edge[i].to;
                      into[temp]--;
                      ans[temp] = ans[now] + ans[temp];
              }
          }
      }
}

回复

2 条回复,欢迎继续交流。

正在加载回复...