勤奋的杨老师（二）
- 时间限制：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 星期五