传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1827
求联通块入度为0的数量及传递到整个图的最小花费。算是tarjan的模板题了
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<stack> using namespace std; const int N = 1005; const int inf = 1 << 28; struct node{ int to, nxt; }e[N*2]; struct pp{ int st, ed; }p[N*2]; int head[N], vis[N]; int scc[N], sccnum; int cnt, index; int pay[N]; int low[N], dfn[N]; int n, m; stack<int> s; int in[N]; void init() { sccnum = cnt = index = 0; memset(head, -1, sizeof(head)); memset(low, 0, sizeof(low)); memset(vis, 0, sizeof(vis)); memset(in, 0, sizeof(in)); memset(dfn, 0, sizeof(dfn)); while( !s.empty() ) s.pop(); } void add(int u, int v) { e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt++; } void tarjan( int u ) { dfn[u] = low[u] = ++index; //memset(0的时候++index,-1就随意了) vis[u] = 1; s.push(u); for( int i = head[u]; ~i; i = e[i].nxt ) { int to = e[i].to; if( !dfn[to] ) { tarjan(to); low[u] = min(low[u], low[to]); } else if( vis[to] ) { low[u] = min(low[u], dfn[to]); } } if( low[u] == dfn[u] ) { sccnum++; while( 1 ) { int tmp = s.top(); s.pop(); vis[tmp] = 0; scc[tmp] = sccnum; if( low[tmp] == dfn[tmp] ) break; } } } int main() { while(~scanf("%d%d", &n, &m)) { init(); for( int i = 1; i <= n; i++ ) scanf("%d", &pay[i]); int u, v; for( int i = 1; i <= m; i++ ) { scanf("%d%d", &u, &v); p[i].st = u; p[i].ed = v; add(u, v); } for( int i = 1; i <= n; i++ ) { if( !dfn[i] ) tarjan(i); } for( int i = 1 ; i <= m ; i++ ) { if( scc[ p[i].st ] != scc[ p[i].ed ] ) //如果起点终点不在同一个联通块里,起点所在联通块出度++ ,终点的入度++ { in[ scc[p[i].ed] ] ++; } } for( int i = 1; i <= n; i++ ) vis[i] = inf; int ans1 = 0, ans2 = 0; for( int i = 1; i <= sccnum; i++ ) { if (!in[i]) { ans1++; } } for( int i = 1; i <= n; i++ ) { int tmp = scc[i]; if( in[tmp] == 0 ) { vis[tmp] = min(vis[tmp], pay[i]); } } for( int i = 1; i <= sccnum; i++ ) { if( vis[i] != inf ) ans2 += vis[i]; } printf("%d %d\n", ans1, ans2); } return 0; } /* 12 16 1 2 3 4 5 6 7 8 9 10 11 12 1 3 3 2 2 1 3 4 2 4 3 5 5 4 4 6 6 4 7 4 7 12 7 8 8 7 8 9 10 9 11 10 */