发布时间：2025-05-22

二分图最大权匹配$O(n^3)$

/**   二分图最大权匹配（MaxAssignment 基于KM）
 *    2022-04-10: https://atcoder.jp/contests/abc247/submissions/30867023
 *    2023-09-21: https://qoj.ac/submission/184824
**/
constexpr int inf = 2E10;//>=(左部点数+右部点数)*最大权值,一般设1E7
template<class T>
struct MaxAssignment {
    public:
        T solve(int nx, int ny, std::vector<std::vector<T>> a) {
            // assert(0 <= nx && nx <= ny);
            // assert(int(a.size()) == nx);
            for (int i = 0; i < nx; ++i) {
                // assert(int(a[i].size()) == ny);
                for (auto x : a[i])
                    assert(x >= 0);
            }
            
            auto update = [&](int x) {
                for (int y = 0; y < ny; ++y) {
                    if (lx[x] + ly[y] - a[x][y] < slack[y]) {
                        slack[y] = lx[x] + ly[y] - a[x][y];
                        slackx[y] = x;
                    }
                }
            };
            
            costs.resize(nx + 1);
            costs[0] = 0;
            lx.assign(nx, std::numeric_limits<T>::max());
            ly.assign(ny, 0);
            xy.assign(nx, -1);
            yx.assign(ny, -1);
            slackx.resize(ny);
            for (int cur = 0; cur < nx; ++cur) {
                std::queue<int> que;
                visx.assign(nx, false);
                visy.assign(ny, false);
                slack.assign(ny, std::numeric_limits<T>::max());
                p.assign(nx, -1);
                
                for (int x = 0; x < nx; ++x) {
                    if (xy[x] == -1) {
                        que.push(x);
                        visx[x] = true;
                        update(x);
                    }
                }
                
                int ex, ey;
                bool found = false;
                while (!found) {
                    while (!que.empty() && !found) {
                        auto x = que.front();
                        que.pop();
                        for (int y = 0; y < ny; ++y) {
                            if (a[x][y] == lx[x] + ly[y] && !visy[y]) {
                                if (yx[y] == -1) {
                                    ex = x;
                                    ey = y;
                                    found = true;
                                    break;
                                }
                                que.push(yx[y]);
                                p[yx[y]] = x;
                                visy[y] = visx[yx[y]] = true;
                                update(yx[y]);
                            }
                        }
                    }
                    if (found)
                        break;
                    
                    T delta = std::numeric_limits<T>::max();
                    for (int y = 0; y < ny; ++y)
                        if (!visy[y])
                            delta = std::min(delta, slack[y]);
                    for (int x = 0; x < nx; ++x)
                        if (visx[x])
                            lx[x] -= delta;
                    for (int y = 0; y < ny; ++y) {
                        if (visy[y]) {
                            ly[y] += delta;
                        } else {
                            slack[y] -= delta;
                        }
                    }
                    for (int y = 0; y < ny; ++y) {
                        if (!visy[y] && slack[y] == 0) {
                            if (yx[y] == -1) {
                                ex = slackx[y];
                                ey = y;
                                found = true;
                                break;
                            }
                            que.push(yx[y]);
                            p[yx[y]] = slackx[y];
                            visy[y] = visx[yx[y]] = true;
                            update(yx[y]);
                        }
                    }
                }
                
                costs[cur + 1] = costs[cur];
                for (int x = ex, y = ey, ty; x != -1; x = p[x], y = ty) {
                    costs[cur + 1] += a[x][y];
                    if (xy[x] != -1)
                        costs[cur + 1] -= a[x][xy[x]];
                    ty = xy[x];
                    xy[x] = y;
                    yx[y] = x;
                }
            }
            return costs[nx];
        }
        std::vector<int> assignment() {
            return xy;
        }
        std::pair<std::vector<T>, std::vector<T>> labels() {
            return std::make_pair(lx, ly);
        }
        std::vector<T> weights() {
            return costs;
        }
		std::vector<T> get_matchx(){
			return xy;
		}
		std::vector<T> get_matchy(){
			return yx;
		}
    private:
        std::vector<T> lx, ly, slack, costs;// 左部点标签，右部点标签，松弛点，权值
        std::vector<int> xy, yx, p, slackx;// 左部点匹配，右部点匹配，前驱，松弛点对应的左部点
        std::vector<bool> visx, visy;// 左部点访问标记，右部点访问标记
};
void solve(){
	int n,m;
	cin>>n>>m;
	vector cost(n,vector<int>(n));
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		cost[u][v]=max(cost[u][v],inf+w);
	}
	MaxAssignment<int> ma;
	ma.solve(n,n,cost);
	int k=0;
	auto ans=ma.weights();
	while(k<n&&ans[k+1]>=inf*(k+1))k++;
	cout<<ans[k]-inf*k<<"\n";
	auto yx=ma.get_matchy();
	for(int i=0;i<n;i++){
		if(yx[i]!=-1)cout<<yx[i]+1<<" \n"[i==n-1];
	}
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}