結果

問題 No.1813 Magical Stones
コンテスト
ユーザー SSRS
提出日時 2022-01-14 21:56:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,579 bytes
コンパイル時間 2,656 ms
コンパイル使用メモリ 193,084 KB
実行使用メモリ 25,956 KB
最終ジャッジ日時 2024-11-20 09:56:44
合計ジャッジ時間 7,939 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 8 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
struct strongly_connected_components{
	vector<vector<int>> ans;
	vector<int> scc;
	void dfs1(vector<vector<int>> &E, vector<int> &t, vector<bool> &used, int v){
		for (int w : E[v]){
			if (!used[w]){
				used[w] = true;
				dfs1(E, t, used, w);
			}
		}
		t.push_back(v);
	}
	void dfs2(vector<vector<int>> &E2, vector<bool> &used2, int v){
		ans.back().push_back(v);
		for (int w : E2[v]){
			if (!used2[w]){
				used2[w] = true;
				dfs2(E2, used2, w);
			}
		}
	}
	strongly_connected_components(vector<vector<int>> &E){
		int N = E.size();
		vector<vector<int>> E2(N);
		for (int i = 0; i < N; i++){
			for (int j : E[i]){
				E2[j].push_back(i);
			}
		}
		vector<int> t;
		vector<bool> used(N, false);
		for (int i = 0; i < N; i++){
			if (!used[i]){
				used[i] = true;
				dfs1(E, t, used, i);
			}
		}
		reverse(t.begin(), t.end());
		vector<bool> used2(N, false);
		scc = vector<int>(N);
		int cnt = 0;
		for (int i = 0; i < N; i++){
			if (!used2[t[i]]){
				used2[t[i]] = true;
				ans.push_back(vector<int>());
				dfs2(E2, used2, t[i]);
				for (int j : ans.back()){
					scc[j] = cnt;
				}
				cnt++;
			}
		}
	}
	int operator [](int k){
		return scc[k];
	}
	int size(){
		return ans.size();
	}
};
template <typename Cap>
struct dinic{
  struct edge{
    int to, rev;
    Cap cap;
    edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap){
    }
  };
  int N;
  vector<vector<edge>> G;
  dinic(int N): N(N), G(N){
  }
  void add_edge(int from, int to, Cap cap){
    G[from].push_back(edge(to, G[to].size(), cap));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
  }
  Cap dfs(vector<int> &d, vector<int> &iter, int v, int t, Cap f){
    if (v == t){
      return f; 
    }
    while (iter[v] < G[v].size()){
      int w = G[v][iter[v]].to;
      if (G[v][iter[v]].cap > 0 && d[v] < d[w]){
        Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap));
        if (f2 > 0){
          G[v][iter[v]].cap -= f2;
          G[w][G[v][iter[v]].rev].cap += f2;
          return f2;
        }
      }
      iter[v]++;
    }
    return 0;
  }
  Cap max_flow(int s, int t){
    Cap flow = 0;
    while (true){
      vector<int> d(N, -1);
      d[s] = 0;
      queue<int> Q;
      Q.push(s);
      while (!Q.empty()){
        if (d[t] != -1){
          break;
        }
        int v = Q.front();
        Q.pop();
        for (auto &e : G[v]){
          int w = e.to;
          if (e.cap > 0 && d[w] == -1){
            d[w] = d[v] + 1;
            Q.push(w);
          }
        }
      }
      if (d[t] == -1){
        break;
      }
      vector<int> iter(N, 0);
      while (true){
        Cap f = dfs(d, iter, s, t, INF);
        if (f == 0){
          break;
        }
        flow += f;
      }
    }
    return flow;
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }
  strongly_connected_components G(E);
  int V = G.size();
  if (V == 1){
    cout << 0 << endl;
  } else {
    set<pair<int, int>> E2;
    for (int i = 0; i < N; i++){
      for (int j : E[i]){
        if (G[i] != G[j]){
          E2.insert(make_pair(i, j));
        }
      }
    }
    dinic<int> G2(V * 2 + 2);
    for (int i = 0; i < V; i++){
      G2.add_edge(V * 2, i, 1);
      G2.add_edge(V + i, V * 2 + 1, 1);
    }
    for (auto P : E2){
      G2.add_edge(P.first, V + P.second, 1);
    }
    cout << V - G2.max_flow(V * 2, V * 2 + 1) << endl;
  }
}
0