MENU

新疆大学ACM-ICPC程序设计竞赛五月月赛D 勤奋的杨老师(二)(最大权闭合子图)

2018 年 05 月 11 日 • 阅读: 982 • 图论阅读设置

勤奋的杨老师(二)

  • 时间限制:C/C++ 1秒,其他语言2秒
  • 空间限制:C/C++ 32768K,其他语言65536K
  • 64bit IO Format: %lld

题目描述

众所周知,杨老师是一位十分勤奋的老师,他非常的热爱学习。

勤奋的他为自己罗列了一个学习清单,共有n个知识点,他可以有选择的进行学习。

每个知识点都会对应0个或1个或多个先修知识点(只有学会了先修知识点才能学习该知识点),同时每个知识点都有一个智慧值和一个智力消耗值。

杨老师希望在进行过激烈的学习之后,他的收获可以·量化为所有学过的题的智慧值的和与智力消耗值的和的差值。请问,这个值最大是多少?

输入描述

第一行:一个整数n(n<=500)接下来n行,每行两个整数,代表第i个知识点的智慧值和智力消耗值接下来若干行,每行2个整数u, v,代表u是v的先修知识点。

输出描述

一行,表示杨老师的收获的最大值

输入

4
5 1
2 1
1 2
1 2
3 1
2 4
2 1

输出

4

链接

https://www.nowcoder.com/acm/contest/116/D

题意&题解

最大权闭合子图,但是注意是求智慧值的和与智力消耗值的和的差值的最大值,所以建图的时候注意边权为点权的差值。

if (cap1 > cap2)
{
    addedge(S, i, cap1 - cap2);
    sum += (cap1 - cap2);
}
else
    addedge(i, T, cap2 - cap1);

代码

  • 运行时间: 13 ms
  • 占用内存:1252K
  • 代码长度:2651
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 510;
const int maxm = 250010;
int N, NP, NC;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int u, v, cap;
    Edge() {}
    Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
} es[maxm];
int R, S, T;
vector<int> tab[maxn]; // 边集
int dis[maxn];
int current[maxn];
void addedge(int u, int v, int cap)
{
    tab[u].push_back(R);
    es[R++] = Edge(u, v, cap); // 正向边
    tab[v].push_back(R);
    es[R++] = Edge(v, u, 0); // 反向边容量为0
    // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2
}
int BFS()
{
    queue<int> q;
    q.push(S);
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    while (!q.empty())
    {
        int h = q.front();
        q.pop();
        for (int i = 0; i < tab[h].size(); i++)
        {
            Edge &e = es[tab[h][i]];
            if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
            {
                dis[e.v] = dis[h] + 1;
                q.push(e.v);
            }
        }
    }
    return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}
int dinic(int x, int maxflow)
{
    if (x == T)
        return maxflow;
    // i = current[x] 当前弧优化
    for (int i = current[x]; i < tab[x].size(); i++)
    {
        current[x] = i;
        Edge &e = es[tab[x][i]];
        if (dis[e.v] == dis[x] + 1 && e.cap > 0)
        {
            int flow = dinic(e.v, min(maxflow, e.cap));
            if (flow)
            {
                e.cap -= flow; // 正向边流量降低
                es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加
                return flow;
            }
        }
    }
    return 0; // 找不到增广路 退出
}

int DINIC()
{
    int ans = 0;
    while (BFS()) // 建立分层图
    {
        int flow;
        memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组
        while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广
            ans += flow;
    }
    return ans;
}
int main()
{
//    freopen("/home/taifu/ACMer/Training/data.in", "r", stdin);
//    freopen("/home/taifu/ACMer/Training/data.out","w",stdout);
    scanf("%d", &N);
    int sum = 0, R = 0;
    S = 0, T = N + 1;
    for (int i = 0; i <= T; i++)
        tab[i].clear();
    for (int i = 1; i <= N; i++)
    {
        int cap1, cap2;
        scanf("%d%d", &cap1, &cap2);
        if (cap1 > cap2) // 边的权值
        {
            addedge(S, i, cap1 - cap2);
            sum += (cap1 - cap2);
        }
        else
            addedge(i, T, cap2 - cap1);

    }
    int u, v;
    while (scanf("%d%d", &u, &v) != EOF)
        addedge(v, u, inf);
    int ans = sum - DINIC();
    printf("%d\n",ans);
    return 0;
}

以前遇见过的东西再遇见就会很熟悉,当然熟悉并不意味着就一定能做出来。


The end.
2018-05-11 星期五
最后编辑于: 2018 年 08 月 06 日