0%

4.14 杂题

T1 CNF2

题意

有$n$个bool变量$b$和$m$条限制,第$i$条限制为$a_{i,1}|a_{i,2}|\cdots|a_{i, k}$,这里$a_{i,x}$可能为$b_t$或$\neg b_t$。记第$i$条限制得到的值为$v_i$,你需要求出一组解满足$v_1\and v_2\and\cdots\and v_k=1$或判断无解。

保证每个变量和其相反变量出现次数的和不超过$2$,在一条限制中至多出现一次。

题解

做法一:用类似Dijkstra的方法,将所有限制按照剩余的未确定的变量个数从小到大排序,优先取较小的,然后将其涉及的第一个未确定的变量确定下来,同时更新包含这个变量的相反变量的限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef pair<int, int> P;

int fa[N], ans[N], ct[N], vis[N], bl[2][N];

vector<int> p[N];

int main() {
int n, m; scanf("%d%d", &n, &m), memset(ans, -1, sizeof(ans));
for (int i = 1; i <= n; i++) {
int k; scanf("%d", &k), ct[i] = k;
for (int j = 1, a; j <= k; j++)
scanf("%d", &a), p[i].push_back(a), bl[a < 0][abs(a)] = i;
}
priority_queue<P> q;
for (int i = 1; i <= n; i++) q.push(P(-ct[i], i));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue; vis[u] = 1;
if (!ct[u]) return puts("NO"), 0;
for (auto t : p[u]) if (ans[abs(t)] == -1) {
int cur = t < 0; t = abs(t);
ans[t] = cur; int nxt = bl[cur ^ 1][t];
if (nxt && !vis[nxt]) ct[nxt]--, q.push(P(-ct[nxt], nxt));
break;
}
}
puts("YES");
for (int i = 1; i <= m; i++) if (ans[i] == 1) putchar('0');
else putchar('1');
}

做法二:对于每个变量,我们将其看作一条边,将所有限制看作点。如果这个变量及其相反变量都在限制中出现过,那么将这两个限制连接起来,否则连一个自环。问题转化为每次可以选择一条边的一个端点标记,需要使得最终所有点都被标记。

对于一个连通块来讲,如果它是树那么肯定不合法,因为边数小于点数。

否则一定存在一种方案。具体来说,我们随便找出一条非树边,选择它的其中一个端点作为根,从根出发找到一棵不经过这条边的生成树。对于生成树上的每条边,选择它的儿子标记,对于选中的这条边,选择根标记。这样可以使得每个点都被标记过。

T3 Son of Pipe Stream

题意

给出一张无向图,每条边有其流量限制$w_i$。$1$号点流入一种叫做Flubber的液体,$2$号点流入水,它们的共同汇点是$3$。给定$v$,对于每条边Flubber的流量$\times v$加上水的流量不能超过$w_i$。记最终Flubber的总流量为$F$,水的流量为$W$,给定$a$,你需要最大化$F^aW^{1-a}$。

如果一条边同时有Flubber与水的流量,那么它们流的方向不能相同。输出方案。

题解

首先从$1$号点和$2$号点开始分别跑一遍最大流,记它们的流量分别为$F’,W’$。接着建一个超级源点,同时向这两个点连边,记此时的最大流为$S$。

有一个定理是对于$a,b$,如果满足$a\leq 1, b\leq 1$且$F’a+W’b\leq S$,那么一定存在一个最大流满足其流量恰好为$F’a+W’b$,且它由$F’a$的Flubber与$W’b$的水组成。

不妨令$F’a+W’b=S$,根据简单的求导可以求出,当$F^aW^{1-a}$取得最大值时有$\frac FW=\frac{a}{1-a}$。

考虑怎么构造方案。

将超级源点连向$1$的边的容量改为$F’a$,将连向$2$的边容量改为$W’b$,跑一遍最大流。然后仅保留最大流上的那些边,并且将它们改为单向边,容量为最大流中的流量。

接着从$1$出发,在新图上跑一个大小为$F’a$的流,可以发现此时最大流扣去这个$F’a$的流就得到了一个从$2$开始,流量为$W’b$的流。且这样构造可以使得每条边中两种液体的流向是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

const int N = 210;
const int M = N * N * 2;
const double eps = 1e-10;

struct edge {
int to, next; double w;
} e[M], e2[M];

int head[N], cur[N], ecnt;

void adde(int from, int to, double w) {
e[++ecnt] = { to, head[from], w }, head[from] = ecnt;
e[++ecnt] = { from, head[to], w }, head[to] = ecnt;
}

void adde1(int from, int to, double w) {
e[++ecnt] = { to, head[from], w }, head[from] = ecnt;
e[++ecnt] = { from, head[to], 0 }, head[to] = ecnt;
}

int dep[N];

bool BFS(int s, int t) {
memset(dep, -1, sizeof(dep)), dep[s] = 0; queue<int> q; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next)
if (e[i].w > eps && dep[e[i].to] == -1) {
dep[e[i].to] = dep[u] + 1, q.push(e[i].to);
if (e[i].to == t) return true;
}
}
return false;
}

double DFS(int u, double f, int t) {
if (u == t || f < eps) return f;
double res = 0, tmp;
for (int &i = cur[u]; i; i = e[i].next)
if (e[i].w && dep[e[i].to] == dep[u] + 1 && (tmp = DFS(e[i].to, min(f, e[i].w), t)) > eps) {
res += tmp, e[i].w -= tmp, e[i ^ 1].w += tmp, f -= tmp;
if (f < eps) break;
}
return res;
}

double dinic(int s, int t) {
double res = 0;
while (BFS(s, t)) memcpy(cur, head, sizeof(head)), res += DFS(s, 1e9, t);
return res;
}

int from[M], to[M], w[M], rev[M];

int main() {
int n, m; double v, a; scanf("%d%d%lf%lf", &n, &m, &v, &a);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &from[i], &to[i], &w[i]);
auto reset = [&]() {
ecnt = 1, memset(head, 0, sizeof(head));
for (int i = 1; i <= m; i++) adde(from[i], to[i], w[i]);
};
reset(); double F = dinic(1, 3);
reset(); double W = dinic(2, 3);
reset(), adde1(n + 1, 1, 1e9), adde1(n + 1, 2, 1e9); double A = dinic(n + 1, 3);
double F1 = A * a; F1 = min(F1, F), F1 = max(F1, A - W);
reset(), adde1(n + 1, 1, F1), adde1(n + 1, 2, A - F1), dinic(n + 1, 3);
memcpy(e2, e, sizeof(e)), ecnt = 1, memset(head, 0, sizeof(head));
for (int i = 1; i <= m; i++) {
if (e2[i * 2].w > w[i]) adde1(to[i], from[i], e[i * 2].w - w[i]), rev[i] = 1;
else adde1(from[i], to[i], w[i] - e2[i * 2].w);
}
adde1(n + 1, 1, F1), dinic(n + 1, 3);
for (int i = 1; i <= m; i++) {
double t1 = e[i * 2 + 1].w / v, t2 = e[i * 2].w;
if (rev[i]) t1 = -t1, t2 = -t2;
printf("%.10lf %.10lf\n", t1 + eps, t2 + eps);
}
printf("%.10lf\n", pow(F1, a) * pow(A - F1, 1 - a) / pow(v, a));
}