ABC 010 D
今回はこの問題を解きました。
あるSNSにおいて、0からn-1のn人の友人関係が与えられます。このSNSにおいては直接友達ではない人でも、自分の友達を介することでその人からのメッセージをみることができます。このうち、指定されたp人から送られるメッセージを0番の人が見られないようにしたいです。そのために以下の操作をすきなだけ行うことができます。
1. ある二人組の友人関係を解消する。
2. ある人がログインできないようにする。
できるだけ操作回数をすくなくしたとき、その操作回数はいくつになるでしょうか、という問題です。
わからなかったので解説を見ました。
最大フロー最小カットの定理を使うそうです。内容とか証明はググったらたくさん出てきます。去年グラフ理論で学びましたがすっかり忘れていました。
改めて考えておもしろい定理だなあと思いました。
この問題では枝は両方向であること、枝の重みはすべて1であることに注意して最大流問題をとけばオッケーです。
解答は以下のようになりました。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 vector<int> getpath(int n, int r[101][101]) { // for(int i = 0; i <= n; i++){ // for(int j = 0; j <= n; j++){ // cout << r[i][j]; // } // cout << endl; // } stack<int> st; vector<int> result; vector<int> beforenode(n + 1, -1); st.push(0); while(!st.empty()){ int nownode = st.top(); // cout << nownode << endl; st.pop(); if(nownode == n){ result.push_back(n); int parent = beforenode[n]; while(parent != -1){ result.push_back(parent); parent = beforenode[parent]; } reverse(result.begin(), result.end()); return result; } for(int i = 1; i <= n; i++){ if(r[nownode][i] == 1 && beforenode[i] == -1){ beforenode[i] = nownode; st.push(i); } } } return result; } int main() { int n, g, e; cin >> n >> g >> e; int p[101]; for(int i = 0; i < g; i++){ cin >> p[i]; } int capacity[101][101] = {}; int flow[101][101] = {}; int residual[101][101] = {}; for(int i = 0; i < e; i++){ int a, b; cin >> a >> b; capacity[a][b] = 1; capacity[b][a] = 1; residual[a][b] = 1; residual[b][a] = 1; } for(int i = 0; i < g; i++){ capacity[p[i]][n] = 1; capacity[n][p[i]] = 1; residual[p[i]][n] = 1; residual[n][p[i]] = 1; } vector<int> augumeting_path = getpath(n, residual); while(augumeting_path.size() != 0){ // cout << augumeting_path.size() << endl; // cout << endl; for(int i = 0; i < augumeting_path.size() - 1; i++){ int node = augumeting_path[i]; // cout << node << " "; int nextnode = augumeting_path[i + 1]; // cout << nextnode << endl; flow[node][nextnode]++; residual[node][nextnode]--; residual[nextnode][node]++; } augumeting_path = getpath(n, residual); } int ans = 0; for(int i = 0; i < n; i++){ ans += flow[i][n]; } cout << ans << endl; }
capacity、residual、flowはそれぞれそのままその枝の容量、残余ネットワークでの値、フローの値を表しています。最初フローはすべて0で、道がある部分については残余ネットワークでの値が1になっています。
getpath関数では増加道を深さ優先探索で調べています。増加道が存在しない場合はからのベクタを返します。
増加道が見つかれば、それに沿ってflowとresidualの値を更新します。これを増加道が見つからなくなるまで繰り返します。最後にノードnに流れてくる総量を求めて答えを出します。
重みは1しかないのだからcapacityは使ってません。ガバガバですね。
今度は重みつきグラフでの問題に挑戦してみたいです。