建立虚拟节点$s、t、S、T$,$s、t$为虚拟源汇,$S、T$为限制下界用到的虚拟源汇。
考虑拆点限制出入度,将每个点拆成左右二部,从$s$向每个点的左部连下界为$1$,上界为$INF$,费用为$0$的弧,从每个点的右部向$t$连下界为$1$,上界为$INF$,费用为$0$的弧,之后用$S、T$补齐每个点不平衡的流量,具体地,从$S$向每个点左部连容量为$1$,费用为$0$的弧,从每个点右部向$T$连容量为$1$,费用为$0$的弧,从$S$向$t$连容量为$n$,费用为$0$的弧,从$s$向$T$连容量为$n$,费用为$0$的弧。
题目中给出的交易,在左右二部之间连容量为$INF$的费用为$w$的弧,对此图跑最小费用最大流,其费用即是原图的最小费用,若最大流不等于$2 \times n$则无解。
对于输出方案,对邻接表添加一组域表示输入边的编号,遍历所有弧,若反向边有流量,且表示编号的域非$0$,说明这条边是横跨二部的边,输出编号。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 710, M = 200100, INF = 1e8;
int e[M], ne[M], f[M], w[M], h[N], id[M], idx;
int d[N], pre[N], q[N], incf[N];
bool vis[N];
int n, m, s, t, S, T;
void insert(int u, int v, int c, int d, int i = 0) {
id[idx] = i;
e[idx] = v, ne[idx] = h[u], f[idx] = c, w[idx] = d, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, w[idx] = -d, h[v] = idx++;
}
bool spfa() {
int tt = 0, hh = 0;
memset(incf, 0, sizeof incf);
memset(d, 0x3f, sizeof d);
q[tt++] = S, d[S] = 0, incf[S] = INF;
while (hh != tt) {
int t = q[hh++];
if (hh == N) hh = 0;
vis[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (f[i] && d[j] > d[t] + w[i]) {
pre[j] = i;
d[j] = d[t] + w[i];
incf[j] = min(incf[t], f[i]);
if (!vis[j]) {
vis[j] = true;
q[tt++] = j;
if (tt == N) tt = 0;
}
}
}
}
return incf[T] > 0;
}
void EK(int& flow, int& cost) {
flow = cost = 0;
while (spfa()) {
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1]) {
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
s = 2 * n + 1, t = s + 1, S = t + 1, T = S + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
insert(u, v + n, INF, w, i);
}
for (int i = 1; i <= n; i++) {
insert(s, i, INF, 0);
insert(i + n, t, INF, 0);
insert(S, i, 1, 0);
insert(i + n, T, 1, 0);
}
insert(S, t, n, 0), insert(s, T, n, 0);
insert(t, s, INF, 0);
int flow, cost;
EK(flow, cost);
if (flow != 2 * n) return (cout << "-1\n"), 0;
cout << cost << '\n';
vector<int> ans;
for (int i = 0; i < idx; i += 2)
if (f[i ^ 1] && id[i])
ans.push_back(id[i]);
cout << ans.size() << ' ';
for (auto item : ans) cout << item << ' ';
return 0;
}