UVa 11324 The Largest Clique(강연통 컴포넌트, dp)

2806 단어 UVa도론
제목 링크:https://vjudge.net/problem/UVA-11324
제목: 지향도 G를 주고 노드 수가 가장 큰 결점 집합을 구하여 이 결점은 임의의 두 결점 u와 v를 집중하여 만족시킨다. u는 v에 도달할 수 있거나 v는 u에 도달할 수 있다(또는 u와 v는 서로 도달할 수 있다)
사고방식: 먼저 그림의 강연통 분량을 구하고 그 수축점을 scc그림으로 얻어 각 scc결점의 권한값은 그의 노드수이다.문제는 DAG 그림을 보여주고 각 점의 값을 알고 가장 큰 값을 구하는 경로로 바뀌었다.dp로 해답을 구할 수 있다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define fin(a) freopen("a.txt","r",stdin)
#define fout(a) freopen("a.txt","w",stdout)
using namespace std;
const int maxn = 1000 + 10;
stack S;
vector G[maxn], G2[maxn];
int n, m;
int con[maxn][maxn], dp[maxn], sccno[maxn], pre[maxn], low[maxn], val[maxn], scc_cnt, scc_clock;

void input_Edge() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) G[i].clear();
  for(int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
  }
}

void dfs(int u) {
  pre[u] = low[u] = ++scc_clock;
  S.push(u);
  for(int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if(!pre[v]) {
      dfs(v);
      low[u] = min(low[u], low[v]);
    }
    else if(!sccno[v]) {
      low[u] = min(low[u], pre[v]);
    }
  }
  if(low[u] == pre[u]) {
    ++scc_cnt;
    for(;;) {
      int x = S.top(); S.pop();
      sccno[x] = scc_cnt;
      val[scc_cnt]++;
      if(x == u) break;
    }
  }
}

void get_scc() {
  while(!S.empty()) S.pop();
  memset(sccno, 0, sizeof sccno);
  memset(pre, 0, sizeof pre);
  memset(low, 0, sizeof low);
  memset(val, 0, sizeof val);
  scc_cnt = scc_clock = 0;
  for(int i = 1; i <= n; i++)
    if(!pre[i]) dfs(i);
}

void get_new() {
  memset(con, 0, sizeof con);
  for(int i = 1; i <= n; i++) G2[i].clear();
  for(int u = 1; u <= n; u++)
    for(int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      int a = sccno[u], b = sccno[v];
      if(a == b || con[a][b]) continue;
      con[a][b] = 1;
      G2[a].push_back(b);
    }
}

int d(int u) {
  if(G2[u].size() == 0) return val[u];
  int& ans = dp[u];
  if(ans > 0) return ans;
  for(int i = 0; i < G2[u].size(); i++)
    ans = max(ans, val[u] + d(G2[u][i]));
  return ans;
}

int solve() {
  memset(dp, 0, sizeof dp);
  int ans = 0;
  for(int i = 1; i <= scc_cnt; i++)
    ans = max(ans, d(i));
  return ans;
}

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    input_Edge();
    get_scc();
    get_new();
    printf("%d
", solve());
  }
  return 0;
}
데이터베이스에 의존하지 않고 드롭다운 메뉴를 만드는 방법.
Docker Desktop3.0.0으로 구축할 수 없는?!

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage