把有可能在一起的连边,求最大独立点集
代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> using namespace std; const int N = 550; struct pupils { int h; string sex; string music; string sport; }P[N]; int T, n; int bmap[N][N], cy[N]; bool vis[N]; bool dfs( int u ) { for ( int v = 1; v <= n; ++v ) if ( bmap[u][v] && !vis[v] ) { vis[v] = 1; if ( cy[v] == -1 || dfs(cy[v])) { cy[v] = u; return 1; } } return 0; } int match() { int res = 0; memset( cy, -1, sizeof(cy) ); for ( int i = 1; i <= n; ++i ) { memset( vis, 0, sizeof(vis)); if ( dfs(i)) res++; } return res; } int main() { scanf("%d", &T); while ( T-- ) { scanf("%d", &n); for ( int i = 1; i <= n; ++i ) { cin >> P[i].h >> P[i].sex >> P[i].music >> P[i].sport; //cout << P[i].h << " " << P[i].sex << " " << P[i].music << " " << P[i].sport << endl; } memset( bmap, 0, sizeof(bmap)); for ( int i = 1; i <= n; ++i ) for ( int j = 1+i; j <= n; ++j ) if ( abs(P[i].h-P[j].h) <= 40 && P[i].sex != P[j].sex && P[i].music == P[j].music && P[i].sport != P[j].sport ) bmap[i][j] = bmap[j][i] = 1; printf("%d\n", n-match()/2); } }