石家庄企业如何建网站,上海市中小企业服务平台,正规网站建设费用,北京专业网站维护公司problem
luogu-P2423
solution
本题即求无向图最大团问题。这是个 NP hard\text{NP hard}NP hard 问题#xff0c;所以必须从图的特殊性质出发#xff0c;否则只能暴搜。
异或运算等价于二进制下不进位的加法运算。 observation1:\text{observation1}:observation1: AAA …problem
luogu-P2423
solution
本题即求无向图最大团问题。这是个 NP hard\text{NP hard}NP hard 问题所以必须从图的特殊性质出发否则只能暴搜。
异或运算等价于二进制下不进位的加法运算。
observation1:\text{observation1}:observation1: AAA 国人之间做朋友的条件等价于两人的 aia_iai 奇偶性不同。
observation2:\text{observation2}:observation2: 基于上一条我们可以得出最大朋友圈中 AAA 国人数只可能包含 0/1/20/1/20/1/2 人。
observation3:\text{observation3}:observation3: BBB 国人的限制有两种且是各自独立的。
observation4:\text{observation4}:observation4: 将 BBB 国人按照 bib_ibi 的奇偶性分类则两类之间的人一定都是两两可以做朋友的。
observation5:\text{observation5}:observation5: 而第二种限制的朋友关系则是一个在奇数类一个在偶数类。
BBB 国分类后的情况形似二分图。
只不过二分图是左右内部两两无边然后有连接左右的边。
这里是左右内部两两有边然后有连接左右的边。
observation6:\text{observation6}:observation6: 原图的补图是个二分图且原图的最大团等于补图的最大独立集。
最大团是两两有边最大独立集是两两无边感觉上原图的最大团就应该等于补图的最大独立集。
严谨证明可自行百度。
而二分图的最大独立集又等于二分图的最小点覆盖。
而二分图的最小点覆盖又等于总点数减去最大匹配数。
所以问题就变成了求补图二分图的最大匹配数网络流即可。
至于 AAA 国的人直接枚举是选 0/1/20/1/20/1/2 个人然后每次重新建图跑网络流即可。
因为有 AAA 国人的存在所以只用考虑与枚举的 AAA 国人是朋友的 BBB 国人跑网络流即可。
具体可以看代码实现。
code
#include bits/stdc.h
using namespace std;
#define maxn 3005
int T, A, B, M, s, t, cnt, ans, tot;
queue int q;
vector int G[maxn];
pair int, int e[maxn * maxn];
struct node { int to, nxt, flow; }E[maxn * maxn];
int head[maxn], cur[maxn], dep[maxn], vis[maxn], a[maxn], b[maxn];
int g[2][maxn];void addedge( int u, int v ) {E[ cnt] { v, head[u], 1 }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) dep[v] dep[u] 1, q.push( v );}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}void dinic( int n ) {while( bfs() ) {n - dfs( s, 1e9 );//总点数-最大匹配 才是要求的补图的最小点覆盖 即原图的最大团if( n ans ) return;}ans n;
}void build() {cnt -1, memset( head, -1, sizeof( head ) );for( int i 1;i tot;i )if( vis[e[i].first] and vis[e[i].second] )addedge( e[i].first, e[i].second );for( int i 1;i g[0][0];i ) if( vis[g[0][i]] ) addedge( s, g[0][i] );for( int i 1;i g[1][0];i ) if( vis[g[1][i]] ) addedge( g[1][i], t );
}int main() {scanf( %d, T );while( T -- ) {scanf( %d %d %d, A, B, M );for( int i 1;i A;i ) G[i].clear();s 0, t B 1, ans tot g[0][0] g[1][0] 0;for( int i 1;i A;i ) scanf( %d, a[i] );for( int i 1;i B;i ) scanf( %d, b[i] );for( int i 1, x, y;i M;i ) {scanf( %d %d, x, y );G[x].push_back( y );}for( int i 1;i B;i ) g[b[i]1][g[b[i]1][0]] i;for( int i 1;i g[0][0];i )for( int j 1;j g[1][0];j )if( __builtin_popcount( b[g[0][i]] | b[g[1][j]] ) 1 )continue;elsee[ tot] make_pair( g[0][i], g[1][j] );for( int i 1;i B;i ) vis[i] 1;build(), dinic( B ); //一个A类人都不选for( int i 1;i A;i ) { //枚举选的一个A类人memset( vis, 0, sizeof( vis ) );for( int x : G[i] ) vis[x] ;int n 1;//n当前情况的总点数for( int j 1;j B;j ) n vis[j];if( n ans ) continue;else build(), dinic( n );}for( int i 1;i A;i )for( int j i 1;j A;j )if( ( a[i] ^ a[j] ) 1 ) {//枚举选择两个A类人memset( vis, 0, sizeof( vis ) );for( int x : G[i] ) vis[x] ;for( int x : G[j] ) vis[x] ;int n 2;for( int k 1;k B;k )if( vis[k] 2 ) vis[k] 0;else vis[k] 1, n ;if( n ans ) continue;else build(), dinic( n );}printf( %d\n, ans );}return 0;
}
