BZOJ1179 [Apio2009] Atm

2021-05-10 15:31

阅读:505

标签:for   技术分享   border   data   order   lin   ring   led   bandit   

Description

技术分享

Input

第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数,表示P个有酒吧的路口的编号

Output

输出一个整数,表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

Sample Input

6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6

Sample Output

47

HINT

50%的输入保证N, M

题解

首先tarjan缩点,然后在DAG上做dp即可。

代码:

#include 
#include 
#include 
#include 
inline int readInt() {
  int ans = 0, c;
  while (!isdigit(c = getchar()));
  do ans = ans * 10 + c - ‘0‘;
  while (isdigit(c = getchar()));
  return ans;
}
const int N = 500050;
int pre[N], nxt[N], to[N], cnt = 0;
inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
}
int dfn[N], scc[N], scnt = 0, cnt3 = 0;
int stack[N], top = 0;
int tarjan(int x) {
  int low = dfn[x] = ++cnt3;
  stack[top++] = x;
  for (int i = pre[x]; ~i; i = nxt[i])
    if (!dfn[to[i]])
      low = std::min(low, tarjan(to[i]));
    else if (!scc[to[i]])
      low = std::min(low, dfn[to[i]]);
  if (low == dfn[x]) {
    ++scnt;
    while (stack[--top] != x)
      scc[stack[top]] = scnt;
    scc[stack[top]] = scnt;
  }
  return low;
}
int pre2[N], nxt2[N], to2[N], cnt2 = 0;
inline void addEdge2(int x, int y) {
  nxt2[cnt2] = pre2[x];
  to2[pre2[x] = cnt2++] = y;
}
int v[N], in[N], f[N];
bool vis[N], bar[N];
int main() {
  int n, m, x, s;
  n = readInt();
  m = readInt();
  memset(pre, -1, sizeof pre);
  memset(pre2, -1, sizeof pre2);
  while (m--) {
    x = readInt();
    addEdge(--x, readInt() - 1);
  }
  for (int i = 0; i 

  

BZOJ1179 [Apio2009] Atm

标签:for   技术分享   border   data   order   lin   ring   led   bandit   

原文地址:http://www.cnblogs.com/y-clever/p/7597963.html


评论


亲,登录后才可以留言!