由于实在不想拆点，写了个这样的代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int N = 5000; 8 bool g[N][N]; 9 bool g2[N][N]; 10 bool visit[N]; 11 set mark[N]; 12 set ::iterator it; 13 int n, m, mm, k; 14 15 void dfs1( int u ) 16 { 17 visit[u] = 1; 18 for ( int i = 1; i <= n; i++ ) 19 { 20 if ( !visit[i] && g[u][i] ) 21 { 22 dfs1(i); 23 } 24 } 25 } 26 27 int dfs2( int u ) 28 { 29 for ( int i = mm; i >= 1; i-- ) 30 { 31 if ( !visit[i] && g2[u][i] ) 32 { 33 visit[i] = 1; 34 if ( mark[i].size() < k ) 35 { 36 mark[i].insert(u); 37 return 1; 38 } 39 for ( it = mark[i].begin(); it != mark[i].end(); it++ ) 40 { 41 if ( dfs2((*it)) ) 42 { 43 mark[i].erase((*it)); 44 mark[i].insert(u); 45 return 1; 46 } 47 } 48 } 49 } 50 return 0; 51 } 52 53 void hungary() 54 { 55 for ( int i = 1; i <= mm; i++ ) 56 { 57 mark[i].clear(); 58 } 59 int res = 0; 60 for ( int i = 1; i <= n; i++ ) 61 { 62 memset( visit, 0, sizeof(visit) ); 63 res += dfs2(i); 64 } 65 printf("%d\n", res); 66 for ( int i = 1; i <= mm; i++ ) 67 { 68 printf("%d", mark[i].size()); 69 if ( i != mm ) putchar(' '); 70 else putchar('\n'); 71 } 72 } 73 74 int main () 75 { 76 int t; 77 scanf("%d", &t); 78 while ( t-- ) 79 { 80 scanf("%d%d%d", &n, &m, &k); 81 mm = 0; 82 memset( g, 0, sizeof(g) ); 83 memset( g2, 0, sizeof(g2) ); 84 while ( m-- ) 85 { 86 int op; 87 scanf("%d", &op); 88 if ( op == 1 ) 89 { 90 mm++; 91 int r; 92 scanf("%d", &r); 93 memset( visit, 0, sizeof(visit) ); 94 dfs1(r); 95 for ( int j = 1; j <= n; j++ ) 96 { 97 if ( visit[j] ) 98 { 99 g2[j][mm] = 1;100 }101 }102 }103 else if ( op == 2 )104 {105 int u, v;106 scanf("%d%d", &u, &v);107 g[u][v] = g[v][u] = 1;108 }109 else if ( op == 3 )110 {111 int q;112 scanf("%d", &q);113 while ( q-- )114 {115 int u, v;116 scanf("%d%d", &u, &v);117 g[u][v] = g[v][u] = 0;118 }119 }120 }121 hungary();122 }123 return 0;124 }
不过很可惜，这份代码是过不去的，具体原因我还没有找到。
只好乖乖拆点了...
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 501; 7 const int M = 7000; 8 const int K = 300000; 9 bool g[N][N]; 10 bool visit[N]; 11 int head[M]; 12 int mark[N]; 13 int ans[N]; 14 int table[N]; 15 int n, m, k, p, e, ptr; 16 17 struct Edge 18 { 19 int v, next; 20 } edge[K]; 21 22 void addEdge( int u, int v ) 23 { 24 edge[e].v = v; 25 edge[e].next = head[u]; 26 head[u] = e++; 27 } 28 29 void dfs1( int u ) 30 { 31 visit[u] = 1; 32 table[ptr++] = u; 33 for ( int i = 1; i <= n; i++ ) 34 { 35 if ( !visit[i] && g[u][i] ) 36 { 37 dfs1(i); 38 } 39 } 40 } 41 42 int dfs2( int u ) 43 { 44 for ( int i = head[u]; i != -1; i = edge[i].next ) 45 { 46 int v = edge[i].v; 47 if ( !visit[v] ) 48 { 49 visit[v] = 1; 50 if ( mark[v] == -1 || dfs2(mark[v]) ) 51 { 52 mark[v] = u; 53 return 1; 54 } 55 } 56 } 57 return 0; 58 } 59 60 void hungary() 61 { 62 int res = 0; 63 memset( mark, -1, sizeof(mark) ); 64 memset( ans, 0, sizeof(ans) ); 65 for ( int i = p - 1; i >= 0; i-- ) 66 { 67 for ( int j = i * k + 1; j <= ( i + 1 ) * k; j++ ) 68 { 69 memset( visit, 0, sizeof(visit) ); 70 if ( dfs2(j) ) 71 { 72 res++; 73 ans[i]++; 74 } 75 } 76 } 77 printf("%d\n", res); 78 for ( int i = 0; i < p - 1; i++ ) 79 { 80 printf("%d ", ans[i]); 81 } 82 printf("%d\n", ans[p - 1]); 83 } 84 85 int main () 86 { 87 int t; 88 scanf("%d", &t); 89 while ( t-- ) 90 { 91 scanf("%d%d%d", &n, &m, &k); 92 e = p = 0; 93 memset( head, -1, sizeof(head) ); 94 memset( g, 0, sizeof(g) ); 95 while ( m-- ) 96 { 97 int op; 98 scanf("%d", &op); 99 if ( op == 1 )100 {101 int r;102 scanf("%d", &r);103 memset( visit, 0, sizeof(visit) );104 ptr = 0;105 dfs1(r);106 for ( int j = 0; j < ptr; j++ )107 {108 for ( int y = p * k + 1; y <= ( p + 1 ) * k; y++ )109 {110 addEdge( y, table[j] );111 }112 }113 p++;114 }115 else if ( op == 2 )116 {117 int u, v;118 scanf("%d%d", &u, &v);119 g[u][v] = g[v][u] = 1;120 }121 else if ( op == 3 )122 {123 int q;124 scanf("%d", &q);125 while ( q-- )126 {127 int u, v;128 scanf("%d%d", &u, &v);129 g[u][v] = g[v][u] = 0;130 }131 }132 }133 hungary();134 }135 return 0;136 }