这是一道最大点权闭合图的问题
首先定义闭合图
建图
这样处理之后
下面证明
下面的证明不知道思路乱不乱
先证明一个闭合图必存在一个简单割与之对应
思路
证明1
再证明一个简单割必对应一个闭合图
思路
证明2
一一对应关系建立完成后
由于流的上限太高
最后
AC代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
struct edge {
int from, to;
long long w, f;
int rev;
edge(int i_from, int i_to, long long i_w, int i_rev) {
this->from = i_from;
this->to = i_to;
this->w = i_w;
this->rev = i_rev;
this->f = 0;
}
};
vector<edge> G[5005];
void addedge(int from, int to, long long w);
long long max_flow(int pt, long long f);
int count(int pt);
void bfs();
int level[5005];
int iter[5005];
int n, m, w[5005];
bool vis[5005];
int main()
{
long long sumw = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
if (w[i] > 0) {
addedge(0, i, w[i]);
sumw += w[i];
}
if(w[i] < 0){
addedge(i, n + 1, -w[i]);
}
}
int father, son;
for (int i = 0; i < m; i++) {
scanf("%d%d", &father, &son);
addedge(father, son, sumw + 1);
}
long long maxf = 0;
while (true) {
memset(level, -1, sizeof(level));
bfs();
if (level[n + 1] < 0) break;
memset(iter, 0, sizeof(iter));
while (true) {
long long f = max_flow(0, sumw);
if (f == 0) break;
maxf += f;
}
}
memset(vis, 0, sizeof(vis));
int cnt = count(0) - 1;
cout << cnt << " " << (sumw - maxf);
return 0;
}
void addedge(int from, int to, long long w) {
G[from].push_back(edge(from, to, w, G[to].size()));
G[to].push_back(edge(to, from, 0, G[from].size() - 1));
}
long long max_flow(int pt, long long f) {
if (pt == n + 1) {
return f;
}
long long curf = 0;
for (int &i = iter[pt]; i < G[pt].size(); i++) {
edge &v = G[pt][i];
if (level[v.to] <= level[pt] || v.w <= 0) continue;
curf = max_flow(v.to, ((f > v.w) ? v.w : f));
if (curf > 0) {
v.w -= curf;
v.f += curf;
G[v.to][v.rev].w += curf;
return curf;
}
}
return 0;
}
void bfs() {
queue<int> que;
que.push(0);
level[0] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = 0; i < G[u].size(); i++) {
if (level[G[u][i].to] >= 0 || G[u][i].w <= 0) continue;
level[G[u][i].to] = level[u] + 1;
que.push(G[u][i].to);
}
}
}
int count(int pt) {//dfs
if(vis[pt]) return 0;
int ans = 1;
vis[pt] = true;
for(int i = 0; i < G[pt].size(); i++) {
if(vis[G[pt][i].to] || G[pt][i].w <= 0) continue;
ans += count(G[pt][i].to);
}
return ans;
}