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 |
出现灵异事件了求大神帮我看看如下代码,自己写的网络流加map,最后调用网络流(foo函数)做统计的时候,如果倒着数就是ac的,正着数的话有一份test case是不过的,先贴代码再贴这份数据,帮我找出bug的我请吃饭,qq278466061,绝对有诚意 #pragma warning(disable:4786) #include <iostream> #include <fstream> #include <map> #include <string> using namespace std; #define MAX 400 map<string, int> s2i; bool path[MAX+10][MAX+10]; bool adapters[MAX+10][MAX+10]; int plugs[MAX+10]; int N, M, K; void Adapters_Init(int i, int j, int count) { int k; for(k = 1; k <= s2i.size(); ++k) { if(adapters[j][k] && !adapters[i][k]) { adapters[i][k] = true; ++count; } } if(count) { for(k = 1; k <= s2i.size(); ++k) { if(adapters[k][i]) Adapters_Init(k, i, 0); } } } void Path_Init() { int i, j; for(i = 1; i <= M; ++i) { for(j = 1; j <= s2i.size(); ++j) { if(path[i][j]) break; } for(int k = 1; k <= N; ++k) { if(adapters[k][j]) path[i][k] = true; } } } bool foo(int i) { for(int n = 1; n <= N; ++n) { if(path[i][n]) { if(!plugs[n]) { plugs[n] = i; path[i][n] = false; return true; } path[i][n] = false; if(foo(plugs[n])) { plugs[n] = i; path[plugs[n]][n] = true; return true; } path[i][n] = true; } } return false; } int main() { //ifstream cin(".//C//C.5.dat"); string t, s; int i, j; cin >> N; for(int n = 1; n <= N; ++n) { cin >> s; s2i[s] = n; } cin >> M; for(int m = 1; m <= M; ++m) { cin >> t >> s; if(s2i.find(s) == s2i.end()) s2i[s] = s2i.size()+1; path[m][s2i[s]] = true; } cin >> K; for(int k = 0; k < K; ++k) { cin >> t >> s; adapters[s2i[s]][s2i[t]] = true; Adapters_Init(s2i[s], s2i[t], 1); } Path_Init(); int count = 0; for(i = M; i >= 1; --i) { if(!foo(i)) ++count; } cout << count << endl; } case: 30 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 r16 r17 r18 r19 r20 r21 r22 r23 r24 r25 r26 r27 r28 r29 30 d0 p0 d1 p1 d2 p2 d3 p3 d4 p4 d5 p5 d6 p6 d7 p7 d8 p8 d9 p9 d10 p10 d11 p11 d12 p12 d13 p13 d14 p14 d15 p15 d16 p16 d17 p17 d18 p18 d19 p19 d20 p20 d21 p21 d22 p22 d23 p23 d24 p24 d25 p25 d26 p26 d27 p27 d28 p28 d29 p29 100 p15 r19 p12 r21 p12 r11 p7 r2 p10 r16 p29 r4 p3 r17 p23 r28 p27 r1 p18 r2 p3 r29 p5 r8 p14 r9 p23 r0 p29 r0 p18 r14 p19 r22 p27 r24 p3 r5 p18 r5 p21 r10 p10 r17 p27 r25 p15 r16 p27 r4 p18 r22 p25 r15 p0 r9 p25 r23 p1 r16 p16 r11 p0 r27 p3 r19 p13 r29 p24 r2 p4 r8 p4 r6 p2 r2 p9 r21 p28 r19 p13 r24 p4 r14 p3 r21 p29 r27 p7 r15 p8 r29 p13 r12 p19 r18 p20 r7 p5 r16 p6 r22 p9 r8 p25 r18 p29 r15 p9 r4 p18 r13 p2 r25 p25 r10 p24 r0 p14 r5 p19 r17 p3 r1 p17 r8 p18 r15 p23 r27 p23 r10 p8 r14 p25 r7 p10 r21 p17 r12 p16 r4 p14 r10 p5 r21 p8 r24 p0 r11 p17 r17 p11 r5 p2 r26 p25 r17 p6 r25 p23 r24 p24 r12 p29 r28 p11 r1 p19 r20 p5 r5 p24 r19 p7 r21 p10 r7 p7 r11 p10 r25 p20 r22 p22 r15 p18 r17 p24 r17 p4 r18 p11 r29 p22 r2 p3 r8 p15 r0 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator