BZOJ2801：[Poi2012]Minimalist Security
? 解题记录 ? ? BZOJ ? ? 模拟 ?    2018-12-19 12:10:04    402    0    0

### 【输入样例】

```For the input data:
3 2
5 10 5
1 2 5
2 3 3
the correct result is:
12 15
whereas for the following input data:
3 3
1 1 1
1 2 1
1 3 1
3 2 1
the correct result is:
NIE```

## 最后再用非树边验证是否满足就可以了。

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define LL long long
using namespace std;
const int maxn = 3e6 + 5;
struct edge {
int v, w, next;
} e[maxn << 1];
int head[maxn], cnt, u, v, w;
void adde(const int &u, const int &v, const int &w) {
e[++cnt] = (edge) {v, w, head[u]};
}
int op[maxn], n, m;
LL l, r, x[maxn], c[maxn], ans = 1e18;
LL sumx, sumc, sum, totmx, totmn;
LL k, b;
inline char gc(){
static char buf[5000000], *p1 = buf, *p2 = buf;
return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
}
x = 0; static char c = gc();
while(!isdigit(c)) c = gc();
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}

void ref(LL tl, LL tr) {
l = max(tl, l), r = min(tr, r);
}

void dfs(int u, int p) {
sumx += x[u], sumc += c[u], sum += op[u];
if(x[u] > 0) ref(-c[u], op[u] - c[u]);
else ref(c[u] - op[u], c[u]);
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p) continue;
if(x[v]) {
k = x[u] + x[v], b = e[i].w - c[u] - c[v];
if(!k) {
if(b) {
printf("NIE");
exit(4);
}
continue;
}
if(b % k != 0) {
printf("NIE");
exit(3);
}
ans = b / k;
continue;
}
x[v] = -x[u];
c[v] = e[i].w - c[u];
dfs(v, u);
}
}

void GetCon(int u) {
x[u] = 1, sum = sumx = sumc = 0;
ans = 1e18, l = 0, r = op[u];
dfs(u, 0);
if(l > r) {
printf("NIE");
exit(4);
}
if(ans != 1e18) {
if(ans < l || ans > r)
{
printf("NIE");
exit(5);
}
l = r = ans;
}
if(sumx > 0) {
totmn += sum - (sumx * r + sumc);
totmx += sum - (sumx * l + sumc);
} else {
totmn += sum - (sumx * l + sumc);
totmx += sum - (sumx * r + sumc);
}
}

int main() {
for(register int i = 1; i <= n; ++i)
for(register int i = 1; i <= m; ++i) {
}
for(register int i = 1; i <= n; ++i)
if(!x[i]) GetCon(i);
printf("%lld %lld", totmn, totmx);
return 0;
}```

402 人读过

0 条评论