「Codeforces 1137C」 Museums Tour

题目链接:Codeforces 1137C

Description

一个$n$个点$m$条边的简单有向图,一周有$d$天。

每个点都有一个博物馆,给出博物馆$i$在一周的第$j$天的开门情况($1\leq i\leq n, 1\leq j \leq d$)。

这周的第$1$天,你从$1$号点开始,每次走一条边需要花费$1$天,如果当前点的博物馆开着,你就可以进去游览。

问在足够长的时间后,你最多可以游览多少个不同的博物馆(一个点的博物馆游览多次只算一次)。

Data Range

$1\leq n,m\leq 10^5,1\leq d\leq 50$

Solution

我们考虑把一个点拆成$d$个点,这样我们就有$n\times d$个点了,每一个点表示的是当前这个点在$j$的时刻的状态。

我们就用$[i,j]$表示$i$号点在$j$时刻的状态。($j$从$0$开始标号)

那么对于每一个相邻连接的边$(u,v)$,因为通过需要$1$的时间,所以我们就连接$([u,j],[v,i+1])$,类似于分层图的做法。

对这个分层图$Tarjan$缩点,然后得到了一个新图,我们需要统计当前这个强联通分量中有多少个不同地点的$1$,也就是这个强联通分两种不同$u$在矩阵中有多少个$1$。这个暴力统计即可。

对于不同强联通分量,如果原来存在一条边,那么依然保留这条边。

这样我们就得到了一个有向无环图,因为我们需要求的是能够参观最多的博物馆,也就是这条路径上的$1$最多,我们就拓扑排序一下,统计最大值即可。

Code

// ==================
// author : chhokmah
// website : http://blog.chhokmah.top/
// create time : 17/08/19 21:29
// ==================
#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 = 2520; // 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> T 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)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

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 writeln(T x) {
    write(x); 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 = 5e6 + 3;
const int M = 5e6 + 3;

template <int N, int M> struct _graph {
  int nxt[M];
  int to[M];
  int head[N];
  int edge_cnt;
  
  _graph(int _c = 0): edge_cnt(_c) { }
  void add_edge(int u, int v) {
    to[++ edge_cnt] = v;
    nxt[edge_cnt] = head[u]; 
    head[u] = edge_cnt;
  }
};
_graph<N, M> G1, G2;

bool instk[N];
int stk[N], stk_top, dfn[N], low[N], _dfc;
int scc_c = 0, scc[N], bel[N], sz[N], de[N], f[N];
char s[100003][51];
int n, m, d;

void tarjan(_graph<N, M> &G, int u) {
  stk[++ stk_top] = u; instk[u] = 1;
  dfn[u] = low[u] = ++ _dfc;
  for (int e = G.head[u]; e; e = G.nxt[e]) {
    int v = G.to[e]; 
    if (!dfn[v]) tarjan(G, v), chkmin(low[u], low[v]);
    else if (instk[v]) chkmin(low[u], dfn[v]); 
  }
  if (low[u] == dfn[u]) {
    ++ scc_c; int j = 0;
    do { j = stk[stk_top --]; scc[j] = scc_c; instk[j] = 0; } while (j != u); 
  }
}
int idx(int x, int t) { return (x - 1) * d + t + 1; }
int ans = 0;
//void topo_bfs() {
//  queue<int> q;
//  for (int i = 1; i <= scc_c; i ++) if (!de[i]) q.push(i); 
//  while (!q.empty()) {
//    int u = q.front(); q.pop(); 
//    for (int e = G2.head[u]; e; e = G2.nxt[e]) {
//      int v = G2.to[e]; 
//      sz[v] += sz[u];
//      if (!(-- de[v])) q.push(v); 
//    }
//  }
//  
//  for (int i = 1; i <= scc_c; i ++) {
//    chkmax(ans, sz[i]);
//    cout << i << ' ' << sz[i] << endl; 
//  }
//}

int dfs(_graph<N, M> &G, int u) {
  if (f[u]) return f[u];
  for (int e = G.head[u]; e; e = G.nxt[e]) {
    int v = G.to[e]; 
    chkmax(f[u], dfs(G, v));
  }
  return f[u] += sz[u]; 
}

int main() {
  read(n); read(m); read(d);
  for (int i = 1, u, v; i <= m; i ++) {
    read(u); read(v);
    for (int j = 0; j < d; j ++) G1.add_edge(idx(u, j), idx(v, (j + 1) % d));
  }
  for (int i = 1; i <= n; i ++) scanf("%s", s[i]);
  scc_c = 0; 
  tarjan(G1, 1);
  
  for (int i = 1; i <= n; i ++) {
    for (int j = 0; j < d; j ++) {
      int u = idx(i, j);
      if (s[i][j] == '1' && bel[scc[u]] != i) {
        bel[scc[u]] = i; sz[scc[u]] ++;
      }
      for (int e = G1.head[u]; e; e = G1.nxt[e]) {
        int v = G1.to[e]; 
        if (scc[u] != scc[v]) G2.add_edge(scc[u], scc[v]), de[scc[v]] ++;
      }
    }
  }
  
//  for (int i = 1; i <= scc_c; i ++) {
//    cout << i << ' ' << sz[i] << endl;
//  }
  
//  topo_bfs();
  writeln(dfs(G2, scc[1]));
  return 0; 
}
最后修改:2019 年 08 月 21 日 10 : 18 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论