QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#468789#7185. Poor Studentsembusca#TL 389ms4796kbC++144.6kb2024-07-09 00:52:472024-07-09 00:52:47

Judging History

你现在查看的是最新测评结果

  • [2024-07-09 00:52:47]
  • 评测
  • 测评结果:TL
  • 用时:389ms
  • 内存:4796kb
  • [2024-07-09 00:52:47]
  • 提交

answer


#include "bits/stdc++.h"
using namespace std;

#define endl '\n'
#define rep(i, a, b) for (ll i = a; i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()
typedef long long ll;
ll INF=(ll)1e18;
 
template<typename T> struct mcmf {
	struct edge {
		ll to, rev, flow, cap; // para, id da reversa, fluxo, capacidade
		bool res; // se eh reversa
		T cost; // custo da unidade de fluxo
		edge() : to(0), rev(0), flow(0), cap(0), cost(0), res(false) {}
		edge(ll to_, ll rev_, ll flow_, ll cap_, T cost_, bool res_)
			: to(to_), rev(rev_), flow(flow_), cap(cap_), res(res_), cost(cost_) {}
	};

	vector<vector<edge>> g;
	vector<ll> par_idx, par;
	T inf;
	vector<T> dist;

	mcmf(ll n) : g(n), par_idx(n), par(n), inf(numeric_limits<T>::max()/3) {}

	void add(ll u, ll v, ll w, T cost) { // de u pra v com cap w e custo cost
		edge a = edge(v, g[v].size(), 0, w, cost, false);
		edge b = edge(u, g[u].size(), 0, 0, -cost, true);

		g[u].push_back(a);
		g[v].push_back(b);
	}

    //Usar esse spfa se o grafo for uma DAG. nm + f * m log n -> n + m + f * m log n
    // vector<T> spfa(ll s) {
	// 	vector<ll> in(g.size(), 0);
    //     queue<ll> q;

    //     rep(i,0,sz(g)){
    //         rep(j,0,sz(g[i])){
	// 			auto [to, rev, flow, cap, res, cost] = g[i][j];
    //             if(flow < cap) in[to]++;
    //         }            
    //     }

    //     rep(i,0,sz(g)){
    //         if(in[i] == 0) q.push(i);
    //     }

	// 	dist = vector<T>(g.size(), inf);
	// 	dist[s] = 0;

	// 	while (!q.empty()) {
	// 		ll v = q.front();
	// 		q.pop();

	// 		rep(i,0,sz(g[v])) {
	// 			auto [to, rev, flow, cap, res, cost] = g[v][i];
	// 			if (flow < cap) {
    //                 dist[to] = min(dist[to], dist[v] + cost);
    //                 if(--in[to] == 0) q.push(to);
	// 			}
	// 		}
	// 	}
	// 	return dist;
	// }

	vector<T> spfa(ll s) { // nao precisa se nao tiver custo negativo
		deque<ll> q;
		vector<bool> is_inside(g.size(), 0);
		dist = vector<T>(g.size(), inf);

		dist[s] = 0;
		q.push_back(s);
		is_inside[s] = true;

		while (!q.empty()) {
			ll v = q.front();
			q.pop_front();
			is_inside[v] = false;

			for (ll i = 0; i < g[v].size(); i++) {
				auto [to, rev, flow, cap, res, cost] = g[v][i];
				if (flow < cap and dist[v] + cost < dist[to]) {
					dist[to] = dist[v] + cost;

					if (is_inside[to]) continue;
					if (!q.empty() and dist[to] > dist[q.front()]) q.push_back(to);
					else q.push_front(to);
					is_inside[to] = true;
				}
			}
		}
		return dist;
	}

	bool dijkstra(ll s, ll t, vector<T>& pot) {
		priority_queue<pair<T, ll>, vector<pair<T, ll>>, greater<>> q;
		dist = vector<T>(g.size(), inf);
		dist[s] = 0;
		q.emplace(0, s);
		while (q.size()) {
			auto [d, v] = q.top();
			q.pop();
			if (dist[v] < d) continue;
			for (ll i = 0; i < g[v].size(); i++) {
				auto [to, rev, flow, cap, res, cost] = g[v][i];
				cost += pot[v] - pot[to];
				if (flow < cap and dist[v] + cost < dist[to]) {
					dist[to] = dist[v] + cost;
					q.emplace(dist[to], to);
					par_idx[to] = i, par[to] = v;
				}
			}
		}
		return dist[t] < inf;
	}

	pair<ll, T> min_cost_flow(ll s, ll t, ll flow = INF) {
		vector<T> pot(g.size(), 0);
		pot = spfa(s); // mudar algoritmo de caminho minimo aqui

		ll f = 0;
		T ret = 0;
		while (f < flow and dijkstra(s, t, pot)) {
			for (ll i = 0; i < g.size(); i++)
				if (dist[i] < inf) pot[i] += dist[i];

			ll mn_flow = flow - f, u = t;
			while (u != s){
				mn_flow = min(mn_flow,
					g[par[u]][par_idx[u]].cap - g[par[u]][par_idx[u]].flow);
				u = par[u];
			}

			ret += pot[t] * mn_flow;

			u = t;
			while (u != s) {
				g[par[u]][par_idx[u]].flow += mn_flow;
				g[u][g[par[u]][par_idx[u]].rev].flow -= mn_flow;
				u = par[u];
			}

			f += mn_flow;
		}

		return make_pair(f, ret);
	}

	// Opcional: retorna as arestas originais por onde passa flow = cap
	vector<pair<ll,ll>> recover() {
		vector<pair<ll,ll>> used;
		for (ll i = 0; i < g.size(); i++) for (edge e : g[i])
			if(e.flow == e.cap && !e.res) used.push_back({i, e.to});
		return used;
	}
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll n, k; cin>>n>>k;
    mcmf<ll> fl(k+n+7);
    ll s=0, t=n+k+2; 
    for(ll i=1+k;i<=n+k+1;i++){
        fl.add(i,t,1,0);
    }
    for(ll i=0;i<n;i++){
        for(ll u=0;u<k;u++){
            ll x; cin>>x;
            fl.add(1+u,i+1+k,1,x);
        }
    }
    for(ll i=1;i<=k;i++){
        ll x; cin>>x;
        fl.add(s,i,x,0);
    }
    cout<<fl.min_cost_flow(s,t).second<<'\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

input:

6 2
1 2
1 3
1 4
1 5
1 6
1 7
3 4

output:

12

result:

ok answer is '12'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 3
1 2 3
2 4 6
6 5 4
1 1 1

output:

8

result:

ok answer is '8'

Test #3:

score: 0
Accepted
time: 389ms
memory: 4796kb

input:

1000 10
734 303 991 681 755 155 300 483 702 442
237 256 299 675 671 757 112 853 759 233
979 340 288 377 718 199 935 666 576 842
537 363 592 349 494 961 864 727 84 813
340 78 600 492 118 421 478 925 552 617
517 589 716 7 928 638 258 297 706 787
266 746 913 978 436 859 701 951 137 44
815 336 471 720 2...

output:

92039

result:

ok answer is '92039'

Test #4:

score: -100
Time Limit Exceeded

input:

5000 10
14 114 254 832 38 904 25 147 998 785
917 694 750 372 379 887 247 817 999 117
802 15 799 515 316 42 69 247 95 144
727 398 509 725 682 456 369 656 693 955
923 1 681 631 962 826 233 963 289 856
165 491 488 832 111 950 853 791 929 240
509 843 667 970 469 260 447 477 161 431
514 903 627 236 144 3...

output:


result: