JZSIM 3.1
这回终于开始出原题了吗...
T1 大爷
五年 OI 一场空,不判无解见祖宗
100->19
UPD:然后没判 b 为 0 的情况被卡成 81
五年 OI 一场空,不看范围见祖宗...(虽然说没写范围?)
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void gn(T &x) {
char ch=getchar(), pl=0; x=0;
while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
const int N=1e4+10, M=1e5+10, s=N-1, t=N-2, D=1e3;
int h[N], h2[N], to[M], nexp[M], W[M], V[M], p=2;
inline void ins(int a, int b, int w, int v) {
nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, V[p]=v, p++;
}
inline void inst(int a, int b) { nexp[p]=h2[a], h2[a]=p, to[p]=b, p++; }
#define sins(a, b, c, d) ins(a, b, c, d), ins(b, a, 0, -d)
#define INF (0x3f3f3f3f)
int b[2][N], siz[2][N], v[N];
void dfs(int x, int fr, int z) {
if(z) sins(x-D, x, 1, v[x-D]);
for(int u=h2[x];u;u=nexp[u]) if(to[u]!=fr) {
dfs(to[u], x, z);
siz[z][x]+=siz[z][to[u]];
if(b[z][to[u]]==-1) {
if(z) sins(to[u], x, INF, 0);
else sins(x, to[u], INF, 0);
}
}
if(b[z][x]!=-1) {
if(b[z][x]<siz[z][x]) puts("-1"), exit(0);
if(!z) sins(s, x, b[z][x]-siz[z][x], 0);
else sins(x, t, b[z][x]-siz[z][x], 0);
siz[z][x]=b[z][x];
}
}
#define CLR(x, y) memset(x, y, sizeof(x))
int dist[N], pre[N], preu[N], cost=0;
bool S[N];
bool spfa() {
CLR(dist, -0x3f), CLR(S, 0);
queue<int> qu; qu.push(s), dist[s]=0, pre[t]=0;
int na;
while(!qu.empty()) {
na=qu.front(), qu.pop(), S[na]=0;
for(int u=h[na];u;u=nexp[u])
if(W[u] && dist[to[u]]<dist[na]+V[u]) {
dist[to[u]]=dist[na]+V[u], pre[to[u]]=na, preu[to[u]]=u;
if(!S[to[u]]) qu.push(to[u]), S[to[u]]=1;
}
}
if(!pre[t]) return 0;
cost+=dist[t];
na=t;
while(pre[na]) {
W[preu[na]]--, W[preu[na]^1]++;
na=pre[na];
}
return 1;
}
int main() {
memset(b, -1, sizeof(b));
int n, x, y;
gn(n), gn(x), gn(y);
for(int i=1; i<=n; i++) gn(v[i]);
int u, v;
for(int i=0; i<2; i++) {
for(int j=0; j<n-1; j++)
gn(u), gn(v), inst(u+i*D, v+i*D), inst(v+i*D, u+i*D);
}
int t;
for(int i=0; i<2; i++) {
gn(t);
for(int j=0; j<t; j++)
gn(u), gn(v), b[i][u+i*D]=v;
}
dfs(x, 0, 0), dfs(y+D, 0, 1);
int flow=0;
while(spfa()) flow++;
if(b[0][x]!=b[1][y+D] || flow!=b[0][x]) puts("-1");
else printf("%d\n", cost);
return 0;
}
T2 熊猫
CF 官方题解就写得很好了...
用了一种数位 DP 的代替方法
很好写
T3 鸽子
什么蛇皮题目
心态爆炸
不写了
CF22 个人 A 掉这题,垃圾题目实锤
本文链接:https://pst.iorinn.moe/archives/jzsim-3-1.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆