STNODE - VOI09 Nút st - xung yếu

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <cstring>
#define maxn 100005
using namespace std;

bool mark[maxn],next[maxn];
int d[maxn],trace[maxn];
vector<int> adj[maxn];
int n,m,s,t;

void BFS(int start) {
  memset(d,-1,sizeof(d));
  d[start] = 0;
  deque<int> q;
  q.push_back(start);

  while (!q.empty()) {
    int u = q.front();
    q.pop_front();
    for (int i = 0; i < adj[u].size(); i++) {
      int v = adj[u][i];
      if (d[v] < 0 || d[v] > d[u] + mark[v]) {
        d[v] = d[u] + mark[v];
	trace[v] = u;
	if (mark[v]) q.push_back(v); else q.push_front(v);
      }
    }
  }
  if (d[t] < 0) d[t] = 0;
}

void track(int u) {
  next[u] = true;
  if (u == s) return;
  track(trace[u]);
}

void printAnswer() {
  vector<int> answer;
  for (int i = 1; i <= n; i++)
    if (i != s && i != t && mark[i]) answer.push_back(i);
  printf("%d\n", answer.size());
//  for (int i = 0; i < answer.size(); i++) printf("%d ", answer[i]);
}

int main() {
//  freopen("assassination.in","r",stdin);
  scanf("%d %d %d %d", &n, &m, &s, &t);
  for (int i = 0; i < m; i++) {
    int x,y;
    scanf("%d %d", &x, &y);
    adj[x].push_back(y);
  }
  memset(mark,true,sizeof(mark));
  while (1) {
    int temp = d[t];
    BFS(s);
    if (d[t] == temp) break;
    memset(next,false,sizeof(next));
    track(t);
    for (int i = 1; i <= n; i++) mark[i] &= next[i];
  }
  printAnswer();
}

Download