Created
September 1, 2015 00:46
-
-
Save asi1024/24fe2ac5d21927e3c4c3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#define REP(i,n) for(int i=0;i<(int)(n);i++) | |
#define ALL(x) (x).begin(),(x).end() | |
using namespace std; | |
typedef int Weight; | |
Weight INF = 1000000000; | |
struct Edge{ int src, dest; Weight weight; }; | |
typedef vector<Edge> Edges; | |
typedef vector<Edges> Graph; | |
typedef vector<Weight> Array; | |
void add_edge(Graph &g, int src, int dest, Weight weight) { | |
g[src].push_back((Edge){src, dest, weight}); | |
} | |
void bfs01(Graph &g, vector<int> &d, int s) { | |
d.assign(g.size(), INF); | |
d[s] = 0; | |
typedef pair<Weight,int> P; | |
deque<P> que; | |
que.push_back(P(0, s)); | |
while (!que.empty()) { | |
P top = que.front(); que.pop_front(); | |
Weight dist = top.first; int v = top.second; | |
if (d[v] < dist) continue; | |
REP(i, g[v].size()) { | |
Edge e = g[v][i]; | |
if (d[e.dest] > d[v] + e.weight) { | |
d[e.dest] = d[v] + e.weight; | |
if (e.weight) que.push_back(P(d[e.dest], e.dest)); | |
else que.push_front(P(d[e.dest], e.dest)); | |
} | |
} | |
} | |
} | |
#define MAX_V 1024 | |
vector<int> g[MAX_V], rg[MAX_V], vs; | |
bool used[MAX_V]; | |
int cmp[MAX_V]; | |
void add_edge(int from, int to) { | |
g[from].push_back(to); | |
rg[to].push_back(from); | |
} | |
void dfs(int v) { | |
used[v] = true; | |
for (int i : g[v]) if (!used[i]) dfs(i); | |
vs.push_back(v); | |
} | |
void rdfs(int v, int k) { | |
used[v] = true; cmp[v] = k; | |
for (int i : rg[v]) if (!used[i]) rdfs(i, k); | |
} | |
int scc(int V) { | |
memset(used, 0, sizeof(used)); | |
vs.clear(); | |
REP(v, V) if (!used[v]) dfs(v); | |
memset(used, 0, sizeof(used)); | |
reverse(ALL(vs)); | |
int k = 0; | |
for (int i : vs) if (!used[i]) rdfs(i, k++); | |
return k; | |
} | |
void clearScc() { | |
REP(i,MAX_V) g[i].clear(); | |
REP(i,MAX_V) rg[i].clear(); | |
} | |
Weight MinimumArborescence(const Graph &g, int root) { | |
const int n = g.size(); | |
Weight res = 0; | |
vector<Weight> c(n, INF); | |
vector<int> p(n, -1); | |
for (int from = 0; from < n; from++) { | |
for (Edge e : g[from]) { | |
if (e.dest == from) continue; | |
if (e.weight < c[e.dest]) p[e.dest] = from, c[e.dest] = e.weight; | |
c[e.dest] = min(c[e.dest], e.weight); | |
} | |
} | |
Graph ng(n); | |
clearScc(); | |
for (int i = 0; i < n; i++) { | |
if (i == root) continue; | |
if (p[i] == -1) return INF; | |
ng[p[i]].push_back((Edge){p[i], i, 0}); | |
add_edge(p[i], i); | |
res += c[i]; | |
} | |
int V = scc(n); | |
vector<vector<int>> connect(V); | |
REP(i,n) connect[cmp[i]].push_back(i); | |
int m = connect.size(); | |
if (m == n) return res; | |
vector<int> mapto(n, -1); | |
vector<int> cycle(n, 0); | |
res = 0; | |
REP(i,m) { | |
REP(j,connect[i].size()) { | |
mapto[connect[i][j]] = i; | |
if (connect[i].size() != 1) | |
cycle[connect[i][j]] = 1, res += c[connect[i][j]]; | |
} | |
} | |
ng = Graph(m); | |
for (int from = 0; from < n; from++) { | |
for (Edge e : g[from]) { | |
Weight cost = e.weight; | |
if (e.dest == root || mapto[from] == mapto[e.dest]) continue; | |
if (cycle[e.dest]) cost -= c[e.dest]; | |
ng[mapto[from]].push_back((Edge){mapto[from], mapto[e.dest], cost}); | |
} | |
} | |
return min(INF, res + MinimumArborescence(ng, mapto[root])); | |
} | |
int main() { | |
int N, M; | |
cin >> N >> M; | |
Graph g1(N); | |
vector<int> deg(N); | |
REP(i,M) { | |
int a, b; | |
cin >> a >> b; | |
add_edge(g1, a, b, 0); | |
add_edge(g1, b, a, 1); | |
++deg[b]; | |
} | |
vector<int> mapto; | |
REP(i,N) | |
if (deg[i] == 0) mapto.push_back(i); | |
int V = mapto.size(); | |
Graph g2(V); | |
REP(i,V) { | |
Array dist; | |
bfs01(g1, dist, mapto[i]); | |
REP(j,V) add_edge(g2, i, j, dist[mapto[j]]); | |
} | |
vector<int> costs; | |
REP(i,V) costs.push_back(MinimumArborescence(g2, i)); | |
int min_cost = INF; | |
REP(i,V) min_cost = min(min_cost, costs[i]); | |
vector<int> res; | |
REP(i,V) if (costs[i] == min_cost) res.push_back(i); | |
cout << res.size() << " " << min_cost << endl; | |
REP(i,res.size()) { | |
if (i > 0) cout << " "; | |
cout << mapto[res[i]]; | |
} | |
cout << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment