SSL 2059_新校园_拓扑

发布于 2018-01-06  42 次阅读


题目描述

某市为了提高市民文化素质,决定实行普及高中教育,为此要建一所超级大规模的高中以供该市初中毕业的学生就读。我们将完成这所学校的建设看成一个大的工程,事实上建一所学校有许多的子工程,我们把这些子工程编号为1、2、……、N,子工程之间就会有一些依赖关系,即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系,因此,有两个任务需要我们去完成:首先,我们需要计算完成这所学校的建设整个工程最少的完成时间;同时,由于一些不可预测的客观因素会使某些子工程延期,因此我们必须知道哪些子工程的延期会影响整个工程的延期,我们集中精力管理好这些子工程,尽量避免这些子工程延期,达到用最快的速度完成整个工程。为了使于编程,现在我们假设: 
(1)根据预算,每一个子工程都有一个完成时间; 
(2)子工程之间的依赖关系是:部分子工程必须在一些子工程完成之后才开工。 
(3)只要满足子工程之间的依赖关系,在任何时刻可以有任何多个子工程同时在施工,也即同时施工的子工程个数不受限制。 
(4)整个工程的完成是指:所有子工程的完成。 


 

思路

我们先设一个工程的子工程有一条连向它的边

一开始想的是用一个优先队列来维护入度为0中的最小时间的点

想了想可能会T

然后就改用两个队列弹弹弹的做法,具体见代码

然后就按照拓扑一样跑就可以了

 

对于第二问,看了看数据范围只有200,想着跑n边上面说的算法应该也不会超时

对于每一个点,如果我们加一,然后时最后的答案变化的话,这个点就是要求的点之一

 

真是太暴力了

 


#include 
#include 
using namespace std;
#define N 100000
#define min(x, y) ((x) < (y) ? (x) : (y))
int l = 0;
struct edge
{
    int to, next;
}e[N];
int ls[N], a[500], in[500], n, b[500], in1[500];
struct cmp
{
    bool operator()(int x, int y)
    {
        return a[x] > a[y];
    }
};
queue t;
queue h;
void add(int x, int y)
{
    e[++l] = (edge) {y, ls[x]};
    ls[x] = l;
}
int ans = 0;
int bfs()
{
    while (!t.empty())
    {
        int now, mi = 0x7f7f7f7f;
        while (!t.empty())
        {
            int ll = t.front();
            if (mi > a[ll]) 
            {
                mi = a[ll];
                now = ll;
            }
            h.push(ll);
            t.pop();
        }
        ans += a[now];
        n--;
        while (!h.empty())
        {
            int ll = h.front();
            if (ll != now)
                a[ll] -= a[now];
            h.pop();
            if (ll != now) t.push(ll);
        }
        for (int i = ls[now]; i; i = e[i].next)
        {
            in[e[i].to]--;
            if (in[e[i].to] == 0) 
                t.push(e[i].to);
        }
        a[now] = 0;
    }
}
int main()
{
    int m;
    scanf("%d", &n);
    m = n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < n; j++)
        {
            int x;
            scanf("%d", &x);
            if (x == 1) 
            {
                if (j >= i)
                    add(j + 1, i);
                else add(j, i);
                in[i]++;
            }
        }
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0) t.push(i);
        in1[i] = in[i];
    }
    bfs();
    if (n != 0) ans = -1;
    printf("%d\n", ans);
    int ll = ans;
    if (n == 0)
    {
        n = m;
        for (int i = 1; i <= n; i++)
        {
            while (!t.empty()) t.pop();
            while (!h.empty()) h.pop();
            n = m;
            for (int j = 1; j <= n; j++)
            {
                if (i == j) a[j] = b[j] + 1;
                else a[j] = b[j];
                in[j] = in1[j];
            }
            for (int j = 1; j <= n; j++)
                if (in[j] == 0) t.push(j);
            ans = 0;
            bfs();
            if (ans > ll) printf("%d ", i);
            n = m;
        }
    }
}

 

]]>


「墨泼三千烟火,许你一世迷离」