Artifact 8b2db66f69d32595c830db74f19b72c50763313f:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 >.#include <stri
0020: 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 ng>.#include <se
0030: 74 3e 0a 75 73 69 6e 67 20 6e 61 6d 65 73 70 61 t>.using namespa
0040: 63 65 20 73 74 64 3b 0a 0a 73 74 72 75 63 74 20 ce std;..struct
0050: 42 65 73 74 52 6f 61 64 73 0a 7b 0a 09 76 65 63 BestRoads.{..vec
0060: 74 6f 72 3c 69 6e 74 3e 20 6e 75 6d 62 65 72 4f tor<int> numberO
0070: 66 52 6f 61 64 73 28 76 65 63 74 6f 72 3c 73 74 fRoads(vector<st
0080: 72 69 6e 67 3e 20 72 6f 61 64 73 2c 20 69 6e 74 ring> roads, int
0090: 20 4d 29 0a 09 7b 0a 09 09 69 6e 74 20 4e 20 3d M)..{...int N =
00a0: 20 72 6f 61 64 73 2e 73 69 7a 65 28 29 3b 0a 09 roads.size();..
00b0: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 61 6e 73 .vector<int> ans
00c0: 28 4e 29 3b 0a 0a 09 09 2f 2f 20 4b 72 75 73 6b (N);....// Krusk
00d0: 61 6c 0a 09 09 74 79 70 65 64 65 66 20 70 61 69 al...typedef pai
00e0: 72 3c 69 6e 74 2c 69 6e 74 3e 20 72 6f 61 64 3b r<int,int> road;
00f0: 0a 09 09 73 65 74 3c 72 6f 61 64 3e 20 51 3b 0a ...set<road> Q;.
0100: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0110: 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 66 6f 72 28 <N; ++i)....for(
0120: 69 6e 74 20 6a 3d 69 2b 31 3b 20 6a 3c 4e 3b 20 int j=i+1; j<N;
0130: 2b 2b 6a 29 0a 09 09 09 09 69 66 28 20 72 6f 61 ++j).....if( roa
0140: 64 73 5b 69 5d 5b 6a 5d 3d 3d 27 59 27 20 29 0a ds[i][j]=='Y' ).
0150: 09 09 09 09 09 51 2e 69 6e 73 65 72 74 28 20 72 .....Q.insert( r
0160: 6f 61 64 28 69 2c 6a 29 20 29 3b 0a 0a 09 09 76 oad(i,j) );....v
0170: 65 63 74 6f 72 3c 69 6e 74 3e 20 70 28 4e 2c 2d ector<int> p(N,-
0180: 31 29 2c 20 73 28 4e 2c 20 31 29 3b 20 2f 2f 20 1), s(N, 1); //
0190: 55 6e 69 6f 6e 2d 46 69 6e 64 0a 09 09 69 6e 74 Union-Find...int
01a0: 20 64 69 76 3d 4e 2c 20 72 65 64 3d 4d 2d 4e 2b div=N, red=M-N+
01b0: 31 3b 0a 0a 09 09 66 6f 72 28 73 65 74 3c 72 6f 1;....for(set<ro
01c0: 61 64 3e 3a 3a 69 74 65 72 61 74 6f 72 20 69 74 ad>::iterator it
01d0: 3d 51 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d =Q.begin(); it!=
01e0: 51 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0a 09 Q.end(); ++it)..
01f0: 09 7b 0a 09 09 09 72 6f 61 64 20 72 20 3d 20 2a .{....road r = *
0200: 69 74 3b 0a 09 09 09 69 6e 74 20 61 3d 72 2e 66 it;....int a=r.f
0210: 69 72 73 74 3b 20 20 77 68 69 6c 65 28 70 5b 61 irst; while(p[a
0220: 5d 21 3d 2d 31 29 20 61 3d 70 5b 61 5d 3b 0a 09 ]!=-1) a=p[a];..
0230: 09 09 69 6e 74 20 62 3d 72 2e 73 65 63 6f 6e 64 ..int b=r.second
0240: 3b 20 77 68 69 6c 65 28 70 5b 62 5d 21 3d 2d 31 ; while(p[b]!=-1
0250: 29 20 62 3d 70 5b 62 5d 3b 0a 09 09 09 69 66 28 ) b=p[b];....if(
0260: 20 61 20 21 3d 20 62 20 29 0a 09 09 09 7b 0a 09 a != b )....{..
0270: 09 09 09 61 6e 73 5b 72 2e 66 69 72 73 74 5d 2b ...ans[r.first]+
0280: 2b 2c 20 61 6e 73 5b 72 2e 73 65 63 6f 6e 64 5d +, ans[r.second]
0290: 2b 2b 2c 20 64 69 76 2d 2d 3b 0a 09 09 09 09 69 ++, div--;.....i
02a0: 66 28 73 5b 61 5d 3c 73 5b 62 5d 29 20 70 5b 61 f(s[a]<s[b]) p[a
02b0: 5d 3d 62 2c 20 73 5b 62 5d 2b 3d 73 5b 61 5d 3b ]=b, s[b]+=s[a];
02c0: 0a 09 09 09 09 65 6c 73 65 20 20 20 20 20 20 20 .....else
02d0: 20 20 20 70 5b 62 5d 3d 61 2c 20 73 5b 61 5d 2b p[b]=a, s[a]+
02e0: 3d 73 5b 62 5d 3b 0a 09 09 09 7d 0a 09 09 09 65 =s[b];....}....e
02f0: 6c 73 65 20 69 66 28 20 72 65 64 20 29 0a 09 09 lse if( red )...
0300: 09 09 61 6e 73 5b 72 2e 66 69 72 73 74 5d 2b 2b ..ans[r.first]++
0310: 2c 20 61 6e 73 5b 72 2e 73 65 63 6f 6e 64 5d 2b , ans[r.second]+
0320: 2b 2c 20 72 65 64 2d 2d 3b 0a 09 09 7d 0a 0a 09 +, red--;...}...
0330: 09 72 65 74 75 72 6e 20 28 72 65 64 3d 3d 30 20 .return (red==0
0340: 26 26 20 64 69 76 3d 3d 31 29 20 3f 20 61 6e 73 && div==1) ? ans
0350: 20 3a 20 76 65 63 74 6f 72 3c 69 6e 74 3e 28 29 : vector<int>()
0360: 3b 0a 09 7d 0a 7d 3b 0a ;..}.};.