题目描述
here。
题解
赛时得分：\(30/30\)，想了很久网络流最后不会。
感觉这题就纯纯对脑洞，因为把题目中的 \(2\) 改成 \(3\) 就做不了）））不过还是相当有意思的。
考虑如下建模方式：
首先，考虑最小割。对于每个点 \(i\)，我们用两个点 \(x_{i}\)，\(y_i\) 来表示。
\(x_i\) 表示 \(i\) 号点是否在 A，\(y_i\) 表示 \(i\) 号点是否在 B，则在 C 为 \(1-x_i-y_i\)。
然后考虑按如下方式建图：对于边 \((u,v,w)\)，我们连 \((x_u,y_v),(x_v,y_u),(y_u,x_v),(y_v,x_u)\)，流量都为 \(w\)。
由于最小割相当于是最小化：
\[\sum_{(u,v,w)} wx_u(1-x_v)
\]
并要求 \(x_S=1,x_T=0\)。
那现在考虑一下实际意义，发现恰好把同时在 \(A\) 的贡献 \(2w\)，用两个点分别不在 \(B\) ，另一个在 \(A\) 算了两次，同时为 \(B\) 也是同理。
我们让只删 \(S\) 到 \(x_i\) 的边为 A，只删 \(y_i\) 到 \(T\) 的边为 B，其它情况为 C。
注意到可能会出现 \(x_i=y_i=1\) 的不合法情况。但算下贡献就会发现，这种情况与 C 也就是 \(x_i=y_i=0\) 是等价的。
最后 \(a\) 号点必须在 A，\(b\) 号点必须在 B 的限制，我们直接 \((s,x_a,\infty),(s,y_b,\infty),(y_a,t,\infty),(x_b,t,\infty)\) 就可以了。
代码
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 2010;
int n, m, A, B;
struct edge {
int to;
ll flow;
unsigned pos;
};
vector <edge> a[N];
void add(int x, int y, ll flow) {
// cout << x << " " << y << " " << flow << endl;
a[x].push_back((edge) { y, flow, (unsigned) a[y].size() });
a[y].push_back((edge) { x, 0, (unsigned) a[x].size() - 1 });
}
int dep[N];
unsigned cur[N];
queue <int> q;
bool bfs(int s, int t) {
F(i, s, t) dep[i] = 0;
dep[s] = 1;
q.push(s);
while (q.size()) {
int x = q.front(); q.pop();
for (edge i: a[x])
if (i.flow && !dep[i.to]) {
dep[i.to] = dep[x] + 1;
q.push(i.to);
}
}
return dep[t];
}
ll dfs(int x, int tt, ll lim) {
if (x == tt) return lim;
ll ans = 0, t;
for (unsigned &i = cur[x]; i < a[x].size(); ++i)
if (a[x][i].flow && dep[a[x][i].to] == dep[x] + 1 && (t = dfs(a[x][i].to, tt, min(lim, a[x][i].flow)))) {
a[x][i].flow -= t, a[a[x][i].to][a[x][i].pos].flow += t;
lim -= t, ans += t;
if (!lim) return ans;
}
return ans;
}
ll dinic(int s, int t) {
ll ans = 0;
while (bfs(s, t)) {
F(i, s, t) cur[i] = 0;
ans += dfs(s, t, 1e18);
} return ans;
}
signed main() {
// freopen("tri.in", "r", stdin);
// freopen("tri.out", "w", stdout);
read(n), read(m), read(A), read(B);
int s = 0, t = 2 * n + 1;
add(s, A, 1e18);
add(s, B + n, 1e18);
add(A + n, t, 1e18);
add(B, t, 1e18);
F(i, 1, m) {
int x, y, z; read(x), read(y), read(z);
add(x, y + n, z);
add(y, x + n, z);
add(x + n, y, z);
add(y + n, x, z);
} cout << dinic(s, t) << endl;
F(i, 1, n)
if (dep[i] && !dep[i + n]) putchar('A');
else if (!dep[i] && dep[i+n]) putchar('B');
else putchar('C');
return 0;
}