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 |
Re:为什么会错呢?搞不懂,哪位大侠帮着看看!谢谢!In Reply To:为什么会错呢?搞不懂,哪位大侠帮着看看!谢谢! Posted by:lyf_2009 at 2011-06-16 18:56:59 #include <vector> #include <algorithm> #include <iostream> #include <string> using namespace std; const int M = 4010; bool vis[M]; int idx; int Stop; int n; vector<int> table[M], marriage[2010]; bool isInStack[M]; int low[M]; int dfn[M]; int stack[M]; #define min(a, b) ((a)<(b)?(a):(b)) void tarjan(int u) { if (vis[u]) return; vis[u] = true; stack[Stop++] = u; isInStack[u] = true; low[u] = dfn[u] = idx++; int i, v; int size = table[u].size(); for (i = 0; i < size; i++) { v = table[u][i]; if (!vis[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (isInStack[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { vector<int> son, girl; int person; do { person = stack[--Stop]; isInStack[person] = false; if (person <= n) son.push_back(person); else girl.push_back(person); }while (u != person); int i, j, k; for (i = 0; i < son.size(); i++) { k = son[i]; for (j = 0 ; j < girl.size(); j++) { marriage[k].push_back(girl[j]); } } } } void initialize() { idx = 0; Stop = 0; memset(vis, 0, sizeof(vis)); memset(isInStack, 0, sizeof(isInStack)); } int main() { int i, j, girl, num; scanf("%d", &n); initialize(); for (i = 1; i <= n; i++) { scanf("%d", &num); for (j = 0; j < num; j++) { scanf("%d", &girl); table[i].push_back(girl+n); } } for (i = 1; i <= n; i++) { scanf("%d", &girl); table[girl + n].push_back(i); } for (i = 1; i <= 2*n; i++) tarjan(i); for (i = 1; i <= n; i++) { sort(marriage[i].begin(), marriage[i].end()); int size = marriage[i].size(); printf("%d", size); for (j = 0; j < size; j++) printf(" %d", marriage[i][j]-n); printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator