m種陽離子 n種陰離子 然后一個m*n的矩陣 第i行第j列為1代表第i種陰離子和第j種陰離子相互吸引 0表示排斥

求在陽離子和陰離子都至少有一種的情況下 最多存在多少種離子能夠共存

陰陽離子都至少須要存在一種 那么能夠枚舉哪2種離子共存 如果枚舉a b 然后找到全部的和a能夠共存的陰離子（設(shè)為x集合）以及和b共存的陽離子（設(shè)為y集合）?

如今僅僅需求x集合中和y集合中最多有多少個離子能夠共存 這個求最大獨(dú)立集即可了 枚舉全部的a b 取最大值

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 55; int vis[maxn]; int y[maxn]; vector <int> G[maxn]; int n, m;char a[maxn][maxn]; bool dfs(int u) {for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(vis[v])continue;vis[v] = true;if(y[v] == -1 || dfs(y[v])){y[v] = u;return true;}}return false; } int match() {int ans = 0;memset(y, -1, sizeof(y));for(int i = 0; i < n; i++){memset(vis, 0, sizeof(vis));if(dfs(i))ans++;}return ans; } int main() {int T;int cas = 1;scanf("%d", &T);while(T--){scanf("%d %d", &n, &m);for(int i = 0; i < n; i++)scanf("%s", a[i]);int ans = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(a[i][j] == '1'){int sum1 = 0, sum2 = 0;for(int h = 0; h < m; h++)if(a[i][h] == '1')sum1++;for(int h = 0; h < n; h++)if(a[h][j] == '1')sum2++;if(ans >= sum1+sum2)continue;for(int h = 0; h < n; h++){G[h].clear();if(a[h][j] == '1'){for(int k = 0; k < m; k++)if(a[i][k] == '1' && a[h][k] == '0')G[h].push_back(k);}}int res = match();if(sum1+sum2-res > ans)ans = sum1+sum2-res;}printf("Case %d: %d\n", cas++, ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/liguangsunls/p/7008156.html

總結(jié)

以上是生活随笔為你收集整理的Light OJ 1373 Strongly Connected Chemicals 二分匹配最大独立集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。