PTA浙江大学数据结构习题——第七周

图7 公路村村通

模板题。

方法一：prim

#include 
#include 

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N];
bool st[N];

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof(dist));
    
    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || (dist[t] > dist[j])))
                t = j;
        
        if (i && dist[t] == INF)    return INF;
        
        if (i) res += dist[t];
        st[t] = true;
        
        for (int i = 1; i <= n; i ++)   dist[i] = min(dist[i], g[t][i]);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    int res = prim();
    if (res == INF) puts("-1");
    else    cout << res << endl;
    
    return 0;
}

方法二：kruskal

#include 
#include 

using namespace std;

const int N = 1010, M = 3 * N, INF = 0x3f3f3f3f;

int n, m;
int p[N];
struct Edge
{
    int a, b, w;
    bool operator< (const Edge& t) const
    {
        return w < t.w;
    }
} edge[M];

int find(int x)
{
    if (p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    int res = 0, cnt = 0;
    for (int i = 1; i <= n; i ++)   p[i] = i;
    
    for (int i = 0; i < m; i ++)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        if (find(a) != find(b))
        {
            cnt ++;
            p[find(a)] = find(b);
            res += w;
        }
    }
    
    if (cnt < n - 1)    return INF;
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }
    sort(edge, edge + m);
    
    int res = kruskal();
    if (res == INF) puts("-1");
    else cout << res << endl;
    
    return 0;
}

图8 How Long Does It Take

在拓扑排序的基础上，用数组 t[i] 表示到达节点 i 的最大值，最终 t 数组中的最大值就是答案。

#include 
#include 
#include 

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], d[N], t[N];

bool topsort()
{
    int cnt = 0;
    queue q;
    for (int i = 0; i < n; i ++)
        if (!d[i])
            q.push(i);
    
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        cnt ++;
        
        for (int i = 0; i < n; i ++)
            if (g[p][i] != INF)
            {
                t[i] = max(t[p] + g[p][i], t[i]);
                d[i] --;
                if (!d[i])  q.push(i);
            }
    }
    return cnt == n;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
    }
    
    // 初始化入度
    for (int i = 0; i 
        int res = 0;
        for (auto x : t)
            if (x != INF)
                res = max(res, x);
        cout << res << endl;
    }
    
    return 0;
}

图9 关键活动

1.一个任务节点的最早完成时间，是 m a x ( 前 置 任 务 的 最 早 完 成 时 间 + 边 长 ) max(前置任务的最早完成时间 + 边长) max(前置任务的最早完成时间+边长)
2.一个任务的最晚开始时间，是 m i n ( 后 续 任 务 的 最 晚 开 始 时 间 − 边 长 ) min(后续任务的最晚开始时间 - 边长) min(后续任务的最晚开始时间−边长)
3.一个任务的机动时间，是 后 续 任 务 的 最 晚 开 始 时 间 − 前 置 任 务 的 最 早 完 成 时 间 − 边 长 后续任务的最晚开始时间 - 前置任务的最早完成时间 - 边长 后续任务的最晚开始时间−前置任务的最早完成时间−边长

#include 
#include 
#include 

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], h[N][N];   // g存有向边，h存机动时间
int t[N], d[N];         // t是任务的最早完成时间，d是入度
int late_t[N], out[N];  // late_t是最晚开始时间，out是出度

bool topsort_early()
{
    int cnt = 0;
    queue q;
    for (int i = 1; i <= n; i ++)
        if (!d[i])
            q.push(i);
    
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        cnt ++;
        
        for (int i = 1; i <= n; i ++)
            if (g[p][i] != INF)
            {
                // 更新最早完成时间
                t[i] = max(t[i], g[p][i] + t[p]);
                d[i] --;
                if (!d[i])  q.push(i);
            }
    }
    return cnt == n;
}

void topsort_latest()
{
    int index = 0;  // 最后一个完成的任务节点
    // 输出总的最早完成时间
    int res = 0;
    for (int i = 1; i <= n; i ++)
        if (t[i] > res)
        {
            res = t[i];
            index = i;  // 更新最终的任务节点
        }
    cout << res << endl;
    
    queue q;
    for (int i = 1; i <= n; i ++)
    {
        late_t[i] = INF;
        if (!out[i])
            q.push(i);
    }
    late_t[index] = t[index];
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        
        for (int i = 1; i <= n; i ++)
            if (g[i][p] != INF)
            {
                if (late_t[i] >= (late_t[p] - g[i][p]))
                {
                    late_t[i] = late_t[p] - g[i][p];        // 更新最晚开始时间
                    h[i][p] = late_t[p] - t[i] - g[i][p];   // 更新机动时间
                }
                out[i] --;
                if (!out[i])    q.push(i);
            }
    }
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    memset(h, 0x3f, sizeof(h));
    
    // 初始化边长
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
    }
    // 初始化出/入度
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            if (g[i][j] != INF)
            {
                d[j] ++;
                out[i] ++;
            }
    
    if (topsort_early())
    {
        topsort_latest();
        for (int i = 1; i <= n; i ++)
            for (int j = n; j; j --)
                if (h[i][j] == 0)
                    printf("%d->%dn", i, j);
    }
    else    puts("0");
    
    return 0;
}