卧槽这题真是坑着我了

tarjan缩点,然后怎么破?
先搞记忆化搜索,再搞topsort+dp,再搞层次图,都跪了肿么办
还是我想的太多了?orz诸神犇求教啊
ps:题解都找不到

5 条评论

  • @ 2016-01-09 20:23:11

    没那么复杂
    ##block code
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    vector<int>g[1500];
    bool vis[1500];
    bool b[1500];
    void dfs(int k,int&x)
    {
    if(vis[k])return;
    vis[k]=1;
    x++;
    for(int i=0;i<g[k].size();i++)
    {
    if(!b[g[k][i]])continue;
    dfs(g[k][i],x);
    }
    }
    int n,k;
    int x,y;
    int ans=0;
    void chain(int k)
    {
    if(!b[k])return;
    b[k]=0;
    ans++;
    for(int i=0;i<g[k].size();i++)
    chain(g[k][i]);
    }
    void fire()
    {
    int M=0,e,p=1;
    for(int i=1;i<=n;i++)
    {
    if(!b[i])continue;
    e=0;
    memset(vis,0,sizeof(vis));
    dfs(i,e);
    if(e>=M)
    {
    M=e;
    p=i;
    }
    }
    chain(p);
    }
    void solve()
    {
    while(k--)fire();
    cout<<ans;
    }
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    memset(b,1,sizeof(b));
    for(int i=1;i<=n;i++)
    {
    cin>>x;
    for(int j=1;j<=x;j++)
    {
    cin>>y;
    g[y].push_back(i);
    }
    }
    solve();
    return 0;
    }

  • @ 2015-05-14 20:38:05

    感觉题目描述有点问题。。
    输出何来“最大”烟火数
    不是一定的吗

  • @ 2014-11-21 20:21:36

    。。。

  • @ 2014-09-09 22:08:14

    其实就是说何以在有向无环图在O(n)内找出A点,A点是可以到达其他点数最多的点

  • @ 2014-09-09 22:06:57

    莫沉

  • 1

信息

ID
1692
难度
9
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
1381
已通过
48
通过率
3%
被复制
2
上传者