「POI 2011」PRO-Programming Contest

题目链接:洛谷3529

Description

现在有$n$个人,每一个人有一个电脑,然后一大堆题目,现在给出每一个人能够解出题目的对应关系,每一个人解出一道题目的时间是固定的$r$,现在有$t$总时间,并且我们按照$ACM$的计分方式来计算分数。

请你给出能够最大化题目的情况下,最小化罚时,并给出方案。

Data Range

$n,m\leq 500,r,t\leq 1000000$

Solution

考虑二分图匹配,很显然的是我们要把题目往前面堆越好,这样可以保证罚时最少。

然后我们就首先枚举时间$nowt$表示当前的时间段,那么解出需要$r$的时间。

那么基于当前的时间我们就尽可能的满足二分图匹配,这个匹配是题目匹配人。因为一个人可以做出多个题目,但是一个题目做掉就没有办法再做一次了。

所以我们就用贪心的思路,按照最少的时间来贪心匹配即可。

时间复杂度为二分图匹配的复杂度。

Code

// ==================
// author : chhokmah
// website : http://blog.chhokmah.top/
// create time : 13/08/19 22:38
// ==================
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

#define REP(i, s, t) for (int i = (s); i <= (t); i ++) 
#define DOW(i, s, t) for (int i = (s); i >= (t); i --)

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define unordered_map __fast_unordered_map
template<class Key, class Value, class Hash = std::hash<Key>>
using unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash>;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;

const int P = 1e9 + 7; // 998244353
const db pi = acos(-1);

template <typename T> void pls(T &x, T y) { x = x + y >= P ? x + y - P : x + y; }
template <typename T> T add(T x, T y) { return x + y >= P ? x + y - P : x + y; }
template <typename T> void dec(T &x, T y) { }
template <typename T> void module(T x) { return (x % P + P) % P; }
template <typename T> T mul(T x, T y) { return (ll) x * y - (ll) x * y / P * P; }

#define mp make_pair
#define pb push_back
#define fi first
#define se second 
#define pi acos(-1)

template <typename T> void chkmax(T &x, T y) { x = x > y ? x : y; }
template <typename T> void chkmin(T &x, T y) { x = x < y ? x : y; }
template <typename T> T qpow(T x, T y) {
  T res = 1; 
  for (; y; y >>= 1, x = mul(x, x)) {
    if (y & 1) res = mul(res, x);
  }
  return res;
}
ll inc(ll x, ll y) {
  ll res = 0;
  for (; y; y >>= 1, x = add(x, x)) {
    if (y & 1) pls(res, x);
  }
  return res;
}

namespace input {
  template <typename T> void read(T &x) {
    x = 0; T flg = 0; char ch = 0;
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flg = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (flg) x *= -1;
  }
  template <typename T, typename... Tx> void read(T &x, Tx &...tx) {
    read(x); read(tx...); 
  }
}

using namespace input;

namespace output {
  void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  void write(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  void write(char ch) { putchar(ch); }
  void write(string s) { cout << s; }
  void write(ull x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  void write(db x) { printf("%.9lf\n", x); }
  template <typename T, typename... Tx> void write(T x, Tx ...tx) {
    write(x); write(tx...); 
  }
  template <typename T, typename... Tx> void writeln(T x, Tx ...tx) {
    write(x); write(tx...); puts("");
  }
  template <typename T> void _dbg(T *a, int l, int r, string s_a = "") {
    if (s_a != "") cout << "array name : " << s_a << " -> "; printf("range [%d, %d] : ", l, r);
    for (int i = l; i <= r; i ++) cout << a[i] << " \n"[i == r];
  }
}

using namespace output;

const int N = 3005;
vector<int> g[N];
bool vis[N];
int match[N], now_time[N];
int n, m, r, t, k;
int dfs(int u) {
  for (auto v : g[u]) {
    if (vis[v]) continue;
    vis[v] = 1;
    if (match[v] == -1 || dfs(match[v])) {
      match[v] = u;
      return 1;
    }
  }
  return 0;
}
int main() {
  memset(match, -1, sizeof(match));
  read(n, m, r, t, k);
  for (int i = 1; i <= k; i ++) {
    int u, v; 
    read(u, v);
    g[u].emplace_back(v);
  }
  int ans1 = 0, ans2 = 0;
  for (int i = 1; i * r <= t; i ++) {
    bool flg = 0;
    for (int j = 1; j <= n; j ++) {
      memset(vis, 0, sizeof(vis));
      if (dfs(j)) {
        ans1 ++; 
        ans2 += i * r;
        flg = 1;
      }
    }
    if (!flg) break;
  }
  writeln(ans1, ' ', ans2);
  memset(now_time, 0, sizeof(now_time));
  for (int i = 1; i <= m; i ++) {
    if (match[i] == -1) continue;
    int u = match[i];
    writeln(u, ' ', i, ' ', now_time[u]);
    now_time[u] += r; 
  }
  return 0;
}
最后修改:2019 年 08 月 17 日 10 : 41 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论