众所周知，考试有两个，一个是暴力一个是正解。
排除有时候只有一个
暴力检验正解的正确性就是对拍。
这是暴力
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stack>
#define int long long
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){ x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, val[C], l, r, Ans, ind[C], cnt, all[C];
struct node
{
int u, v;
} a[C];
struct edge
{
int v, nxt;
} e[C], E[C];
int ecnt, head[C];
void add_edge(int u, int v)
{
e[++ecnt] = (edge){ v, head[u]};
head[u] = ecnt;
}
int Ecnt, Head[C];
void Add_edge(int u, int v)
{
E[++Ecnt] = (edge){v, Head[u]};
Head[u] = Ecnt;
}
queue<int> q;
int dfn[C], low[C], tot, id[C], cir_num;
bool vis[C];
stack<int> s;
void Tarjan(int x)
{
dfn[x] = low[x] = ++tot;
s.push(x), vis[x] = 1;
for (int i = head[x]; i; i = e[i].nxt)
{
int v = e[i].v;
if(!dfn[v])
{
Tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v]) low[x] = min(dfn[v], low[x]);
}
int k;
if(low[x] == dfn[x])
{
do
{
k = s.top(), id[k] = x, vis[k] = 0;
s.pop(), all[x]++;
if(x == k) break;
val[x] += val[k];
}
while(1);
}
}
int tmp[C], Ind[C];
bool Check(int x)
{
for (int i = 1; i <= n; i++) tmp[i] = val[i], Ind[i] = ind[i];
for (int i = 1; i <= n; i++) if(!Ind[i] && id[i] == i){ q.push(i); }
int cs = m;
while(!q.empty())
{
int u = q.front();
q.pop();
for (int i = Head[u]; i; i = E[i].nxt)
{
int v = E[i].v;
if(tmp[u] < x * all[u])
{
tmp[v] = tmp[v] - (x * all[u] - tmp[u]), tmp[u] = all[u] * x;
}
Ind[v]--;
if(!Ind[v]) q.push(v);
}
}
for (int i = 1; i <= n; i++)
{
if(id[i] == i)
{
if(tmp[i] < x * all[i]) cs = cs - (x * all[i] - tmp[i]);
}
}
if(cs < 0) return false;
return true;
}
signed main()
{
freopen("a.in", "r", stdin);
n = read(), m = read();
for (int i = 1; i <= n; i++)
{
int x = read();
if(x != -1)
{
add_edge(i, x);
a[++cnt].u = i, a[cnt].v = x;
}
}
for (int i = 1; i <= n; i++)
{
val[i] = read();
r = max(r, val[i]), l = min(l, val[i]);
}
for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
for (int i = 1; i <= cnt; i++)
{
int x = a[i].u, y = a[i].v;
if(id[x] != id[y]) Add_edge(id[x], id[y]), ind[y]++;
}
while(l <= r)
{
int mid = (l + r) >> 1;
if(Check(mid)) Ans = mid, l = mid + 1;
else r = mid - 1;
}
printf("%lld", Ans);
return 0;
}
/*
5 10
3 1 4 3 3
1 5 2 5 7
*/
这是正解
#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
struct edge { int from, to, nxt; }e[MAXN << 1], E[MAXN << 1];
int head[MAXN], num_edge = 1;
int Head[MAXN], Num_edge = 1;
int n, m;
int a[MAXN], ind[MAXN];
int dfn[MAXN], low[MAXN], num[MAXN], t = 0, cnt = 0;
int stc[MAXN], sc = 0;
int Siz[MAXN], Val[MAXN], f[MAXN];
bool vis[MAXN];
vector<int> tr;
void add_edge(int from, int to) { e[++num_edge] = (edge){from, to, head[from]}, head[from] = num_edge; }
void Add_edge(int from, int to) { E[++Num_edge] = (edge){from, to, Head[from]}, Head[from] = Num_edge; }
void tarjan(int u) {
stc[++sc] = u, vis[u] = true;
dfn[u] = low[u] = ++cnt;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
int pre = stc[sc--]; vis[pre] = false;
num[pre] = ++t, Siz[t] ++, Val[t] += a[pre];
while(u != pre) {
pre = stc[sc--], vis[pre] = false;
num[pre] = t, Siz[t] ++, Val[t] += a[pre];
}
}
}
void dfs(int u, int lim) {
f[u] = Val[u] - lim * Siz[u];
for(int i = Head[u]; i; i = E[i].nxt) {
int v = E[i].to;
dfs(v, lim);
if(f[v] < 0) {
f[u] += f[v];
}
}
}
bool Check(int mid) {
int M = tr.size();
int sum = 0;
for(int i = 0; i < M; ++i) {
dfs(tr[i], mid);
if(f[tr[i]] < 0) sum = sum - f[tr[i]];
}
return sum <= m;
}
signed main() {
freopen("a.in", "r", stdin);
scanf("%lld%lld", &n, &m);
for(int i = 1, u; i <= n; ++i) {
scanf("%lld", &u);
if(u == -1) continue;
add_edge(u, i);
}
for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
for(int u = 1; u <= n; ++u) {
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(num[u] == num[v]) continue;
Add_edge(num[u], num[v]);
ind[num[v]]++;
}
}
for(int i = 1; i <= t; ++i) {
if(!ind[i]) {
tr.push_back(i);
}
}
int l = 0, r = 1000000000, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(Check(mid)) {
ans = mid, l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%lld\n", ans);
return 0;
}
/*
8 5
-1 1 2 3 4 8 6 7
1 2 3 4 5 6 7 8
*/
这是数据生成器：
/*
work by: Ariel_
Knowledge:
Time:
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m;
int main(){
freopen("a.in", "w", stdout);
n = rand() % 10 + 1, m = rand() % 10 + 1;
cout<<n<<" "<<m<<"\n";
for (int i = 1; i <= n; i++) {
int x = rand() % n + 1;
while(x == i) {
x = rand() % n + 1;
}
cout<<x<<" ";
}
puts("");
for (int i = 1; i <= n; i++) {
cout<<rand() % 100 + 1<<" ";
}
return 0;
}
要注意他们的读入程序要相同
都是freopen("xxx.in", "r", stdin);
下面是对拍程序：
/*
work by: Ariel_
Knowledge:
Time:
*/
#include<windows.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int T = 1e5;
int main(){
while(T--) {
system("rand.exe > rand.txt");
system("baoli.exe < rand.txt > baoli.txt");
system("std.exe < rand.txt > std.txt");
if(system("fc baoli.txt std.txt")) break;
}
if(T == 0) cout<<"no error";
else cout<<"error";
return 0;
}