题意：
给定一张无向带权图，求一个排列 \(p\) 使得 \(\sum_{i=2}^n \operatorname{mincut}(p_{i - 1}, p_i)\) 最大。输出一种方案。
\(n \le 200, m \le 1000\)。
思路：
首先这种最小割相关的肯定是最小割树，建树需要 \(O(n^3 m)\)，由于 \(Dinic\) 实际上跑不满，所以时间完全够。
然后考虑检出最小割树，转化为对于一棵树，求一个排列，\(val(i,j)\) 定义为 \(i\) 到 \(j\) 路径上最小边权，使 \(\sum_{i=2}^nval(p_i, p_{i - 1})\) 最大。
对于这种问题，我们考虑构造一个上界，不难发现，最大边权最多贡献一次，沿着这个思路，我们猜测答案是恰好每条边贡献一次。
我们先构造一个方案，找到最小边，然后递归两边处理，保证只有一次经过了这条最小边即可。
考虑如何证明这是最优的。
对树的节点数采用数学归纳法，我们找到最小的边 \((u,v)\)，显然，经过 \((u,v)\) 一次以上不如只经过 \((u,v)\) 一次。所以我们可以发现最右情况 \((u,v)\) 只会被经过 \(1\) 次，而根据归纳法，被分开的两个部分也是边权值和为答案，所以我们就可以证出来这个结论。
然后就是最小割树剪出来加上一个简单的分治即可。
点击查看代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 205;
const int inf = 0x3f3f3f3f;
int n, m;
struct Edge {
int to, val, rev;
Edge (int _to = 0, int _val = 0, int _rev = 0) :
to(_to), val(_val), rev(_rev) {}
};
vector<Edge> e[N], eG[N];
void addEdge(int u, int v, int w) {
eG[u].push_back(Edge(v, w, (int)eG[v].size()));
eG[v].push_back(Edge(u, w, (int)eG[u].size() - 1));
}
int d[N] = {0};
bool bfs(int s, int t) {
memset(d, inf, sizeof d);
queue<int> q;
q.push(s), d[s] = 0;
while (!q.empty()) {
int h = q.front();
q.pop();
for (auto i: e[h])
if (i.val > 0 && d[i.to] > d[h] + 1)
d[i.to] = d[h] + 1, q.push(i.to);
}
return d[t] != inf;
}
int cur[N] = {0};
int dfs(int x, int t, int f) {
if (x == t)
return f;
for (int i = cur[x]; i < (int)e[x].size(); i = ++cur[x])
if (e[x][i].val > 0 && d[e[x][i].to] == d[x] + 1) {
int fl = dfs(e[x][i].to, t, min(e[x][i].val, f));
if (fl > 0) {
e[x][i].val -= fl;
e[e[x][i].to][e[x][i].rev].val += fl;
return fl;
}
}
d[x] = -1;
return 0;
}
int Dinic(int s, int t) {
//init();
int ans = 0;
while (bfs(s, t)) {
memset(cur, 0, sizeof cur);
int ad = 0;
while ((ad = dfs(s, t, inf)) != 0)
ans += ad;
}
return ans;
}
void init() {
for (int i = 1; i <= n; i++)
e[i] = eG[i];
}
int a[N] = {0}, b[N] = {0};
struct Edge_Tree {
int to, val;
Edge_Tree (int _to = 0, int _val = 0) :
to(_to), val(_val) {}
};
vector<Edge_Tree> t[N];
void add(int u, int v, int w) {
t[u].push_back(Edge_Tree(v, w));
t[v].push_back(Edge_Tree(u, w));
}
int slv(int l, int r) {
if (l + 1 >= r)
return 0;
int S = a[l], T = a[l + 1];
init();
int ans = Dinic(S, T);
add(S, T, ans);
int ll = l, rr = r;
for (int i = l; i < r; i++)
if (d[a[i]] != inf)
b[ll++] = a[i];
else
b[--rr] = a[i];
for (int i = l; i < r; i++)
a[i] = b[i];
ans += slv(l, ll) + slv(rr, r);
return ans;
}
bool vis[N] = {false};
int ans[N] = {0}, len = 0;
void srh(int x, int pr, int &A, int &B, int &mn) {
for (auto i: t[x])
if (i.to != pr && !vis[i.to]) {
if (mn > i.val)
mn = i.val, A = x, B = i.to;
srh(i.to, x, A, B, mn);
}
}
void mrk(int x) {
vis[x] = true;
for (auto i: t[x])
if (!vis[i.to])
mrk(i.to);
}
void getans(int x) {//在当前还没有 vis 的 x 所在联通块找到答案
int A = 0, B = 0, mn = 2e9;
srh(x, 0, A, B, mn);
if (A + B == 0)
ans[++len] = x;
else {
vis[B] = true;
getans(A);
vis[B] = false;
getans(B);
}
mrk(x);
}
int main() {
cin >> n >> m;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
addEdge(u, v, w);
}
for (int i = 1; i <= n; i++)
a[i] = i;
cout << slv(1, n + 1) << endl;
getans(1);
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << endl;
return 0;
}