生活随笔
收集整理的這篇文章主要介紹了
2019牛客暑期多校训练营（第五场）F - maximum clique 1 (最大团：补图最大独立集)
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
題目鏈接
題意
求一個(gè)最大的集合，集合內(nèi)的數(shù)字兩兩之間滿足不同bit數(shù)大于1
最大團(tuán)：在一個(gè)無(wú)向圖中找出一個(gè)點(diǎn)數(shù)最多的完全圖
思路
- 求補(bǔ)圖的最大獨(dú)立集：二分圖匹配、最小割
- 可以將原圖轉(zhuǎn)為二分圖，指定建圖方向去掉重復(fù)邊，方便輸出。
- 網(wǎng)絡(luò)流：最小割
- 二分圖匹配：對(duì)沒(méi)有匹配的點(diǎn)dfs，輸出增廣路左點(diǎn) + 不在增廣路上的右點(diǎn)
默認(rèn)輸出右點(diǎn)，如果存在矛盾點(diǎn)，輸出增廣路左點(diǎn)同時(shí)刪除增廣路右點(diǎn)
#include <bits/stdc++.h>
#define endl '\n'
const int maxn
= 5e3 + 5;
const int inf
= 0x3f3f3f3f;
const int mod
= 1e9 + 7;
using namespace std
;
int girl
[maxn
], l
[maxn
], r
[maxn
], match
[maxn
];
vector
<int> g
[maxn
];
int one(int x
) {int cnt
= 0;while (x
) {if (x
& 1) cnt
++;x
>>= 1;}return cnt
;
}
int dfs(int x
) {l
[x
] = 1;for (int i
= 0; i
< (int)g
[x
].size(); ++i
) {int y
= g
[x
][i
];if (r
[y
]) continue;r
[y
] = 1;if (girl
[y
] == 0 || dfs(girl
[y
])) {girl
[y
] = x
;return 1;}}return 0;
}
int main() {ios
::sync_with_stdio(0);cin
.tie(0), cout
.tie(0);int n
;cin
>> n
;vector
<int> a(n
+1);for (int i
= 1; i
<= n
; ++i
) {cin
>> a
[i
];}for (int i
= 1; i
<= n
; ++i
) {for (int j
= i
+1; j
<= n
; ++j
) {if (__builtin_popcount(a
[i
] ^ a
[j
]) == 1) {if (__builtin_parity(a
[i
])) g
[i
].push_back(j
);else g
[j
].push_back(i
);}}}int cnt
= 0;for (int i
= 1; i
<= n
; ++i
) {memset(r
, 0, sizeof(r
));cnt
+= (match
[i
] = dfs(i
));}cout
<< n
- cnt
<< endl
;memset(l
, 0, sizeof(l
));memset(r
, 0, sizeof(r
));for (int i
= 1; i
<= n
; ++i
) {if (match
[i
]) continue;dfs(i
);}vector
<int> ans
;for (int i
= 1; i
<= n
; ++i
) {if (__builtin_parity(a
[i
]) && l
[i
]) ans
.push_back(a
[i
]);if (!__builtin_parity(a
[i
]) && !r
[i
]) ans
.push_back(a
[i
]); }for (auto it
: ans
) {cout
<< it
<< " ";}cout
<< endl
;return 0;
}
#include <bits/stdc++.h>
#define endl '\n'
const int maxn
= 5e3 + 5;
const int inf
= 0x3f3f3f3f;
const int mod
= 1e9 + 7;
using namespace std
;
int one(int x
) {int cnt
= 0;while (x
) {if (x
& 1) cnt
++;x
>>= 1;}return cnt
;
}
struct ac
{int v
, c
, nex
;
}edge
[maxn
<< 8];
int s
, e
;
int head
[maxn
], dis
[maxn
], curedge
[maxn
], cnt
;
void init() {cnt
= 0;memset(head
, -1, sizeof(head
));
}
void addedge(int u
, int v
, int c
) {edge
[cnt
] = {v
, c
, head
[u
]};head
[u
] = cnt
++;edge
[cnt
] = {u
, 0, head
[v
]};head
[v
] = cnt
++;
}
bool bfs() {queue
<int> que
;que
.push(s
);memset(dis
, 0, sizeof(dis
)); dis
[s
] = 1;while (!que
.empty()) {int u
= que
.front();que
.pop();for (int i
= head
[u
]; i
!= -1; i
= edge
[i
].nex
) {int v
= edge
[i
].v
;int c
= edge
[i
].c
;if (dis
[v
] || c
== 0) continue;dis
[v
] = dis
[u
] + 1; que
.push(v
);}}return dis
[e
] > 0;
}int dfs(int u
, int flow
) { if (u
== e
|| flow
== 0) return flow
;for (int &i
= curedge
[u
]; i
!= -1; i
= edge
[i
].nex
) { int v
= edge
[i
].v
;int c
= edge
[i
].c
;if (dis
[v
] != dis
[u
] + 1 || c
== 0) continue;int d
= dfs(v
, min(flow
, c
));if (d
> 0) { edge
[i
].c
-= d
;edge
[i
^1].c
+= d
;return d
;} }dis
[u
] = -1; return 0;
}
int Dinic() {int sum
= 0, d
;while (bfs()) { for (int i
= 0; i
<= e
; ++i
) curedge
[i
] = head
[i
]; while ((d
= dfs(s
, inf
)) > 0) sum
+= d
; }return sum
;
}int main() {ios
::sync_with_stdio(0);cin
.tie(0), cout
.tie(0);int n
;cin
>> n
;vector
<int> a(n
+1);for (int i
= 1; i
<= n
; ++i
) {cin
>> a
[i
];}s
= 0, e
= n
+ 1;init();for (int i
= 1; i
<= n
; ++i
) {if (__builtin_parity(a
[i
])) addedge(s
, i
, 1);else addedge(i
, e
, 1);}for (int i
= 1; i
<= n
; ++i
) {for (int j
= i
+1; j
<= n
; ++j
) {if (__builtin_popcount(a
[i
] ^ a
[j
]) == 1) {if (__builtin_parity(a
[i
])) addedge(i
, j
, 1);else addedge(j
, i
, 1);}}}cout
<< n
- Dinic() << endl
;for (int i
= 1; i
<= n
; ++i
) {if (__builtin_parity(a
[i
]) && dis
[i
]) cout
<< a
[i
] << " ";if (__builtin_parity(a
[i
]) == 0 && dis
[i
] == 0) cout
<< a
[i
] << " ";}cout
<< endl
;return 0;
}
總結(jié)
以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第五场）F - maximum clique 1 (最大团：补图最大独立集)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
