Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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