Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
*****************************注意只有一个连通块时输出1 0***********************#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; /* 题目大意:网络中的一学校可以将软件发送给其他一些学校,能够发送给谁取决于他们各自维护的一个清 单。将学校看成一个节点,给出每个学校的维护清单,问至少需要复制几次软件,使毎个学校都能够得 到该软件,在清单中至少添加几项,可使软件至少复制一次,所有学校都可以得到。 思路: 1、用Tarjan算法求出强连通分分量。2、缩点重新构图。3、分别求节点的出度和入度。 第一个问题就是出度为0的个数,第二问题就是出度和入度为0个数中的较大者。 代码如下: */ #define MAX_N 110 #define MAX_M 11000 #define insert(a, b) (e[++m].s = (a), e[m].t = (b), e[m].n = fi[(a)], fi[(a)] = m) struct node { int s, t, n; }; node e[MAX_M]; int ind[MAX_N], oud[MAX_N]; int dfn[MAX_N], low[MAX_N], belong[MAX_N]; int fi[MAX_N], stack[MAX_N]; bool in[MAX_N]; int n, m, top, s1, s2, tot, tim; void dfs(int x) { dfn[x] = low[x] = ++tot; stack[++top] = x, in[x] = true; for (int i = fi[x]; i != -1; i = e[i].n) { int t = e[i].t; if (!dfn[t]) { dfs (t); if (low[t] < low[x]) low[x] = low[t]; } else if (in[t] && dfn[t] < low[x]) low[x] = dfn[t]; } if (dfn[x] == low[x]) while (stack[top + 1] != x) belong[stack[top]] = x, in[stack[top--]] = false; } int main(void) { freopen ("1236.in", "r", stdin); freopen ("1236.out", "w", stdout); while (scanf ("%d", &n) != EOF) { memset (fi, -1, sizeof (fi)); memset (dfn, 0, sizeof (dfn)); memset (ind, 0, sizeof (ind)); memset (oud, 0, sizeof (oud)); m = s1 = s2 = 0; for (int i = 1; i <= n; i++) { int x = 0; while (scanf ("%d", &x) != EOF && x != 0) insert (i, x); } /*for (int i = 1; i <= n; i++) for (int j = fi[i]; j != -1; j = e[j].n) printf ("%d %d\n", i, e[j].t);*/ for (int i = 1; i <= n; i++) if (!dfn[i]) top = 0, dfs (i); for (int i = 1; i <= m; i++) if (belong[e[i].s] != belong[e[i].t]) ind[belong[e[i].t]]++, oud[belong[e[i].s]]++; for (int i = 1; i <= n; i++) { if (i != belong[i]) continue; tim++; if (ind[belong[i]] == 0) s1++; if (oud[belong[i]] == 0) s2++; } /* for (int i = 1; i <= n; i++) printf ("%d -> %d\n", i, belong[i]);*/ printf ("%d\n", s1); if (tim == 1) puts ("0"); else printf ("%d\n", max (s1, s2)); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator