hdu 5313 Bipartite Graph

本文主要是介绍hdu 5313 Bipartite Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Soda有一个n个点m条边的二分图, 他想要通过加边使得这张图变成一个边数最多的完全二分图. 于是他想要知道他最多能够新加多少条边. 注意重边是不允许的.

官方题解：

分析：首先用bfs染色找出每一个连通分量的黑点，白点的数量，然后求出X*Y的最大值。

直接写的dp超时，用了题解中提到的bitset，终于过了。。。

第一次发现bitset可以这么用，很强大。

以下附上代码：

#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <bitset>using namespace std;typedef long long ll;
typedef unsigned long long ull;const int maxn = 10005;
const int maxm = 100005;struct Node{int v;int next;
};int n,m;struct Adlist{int vex[maxn];Node arc[maxm*2];int cnt;void clear(){for(int i = 0; i <= n; i++){vex[i] = -1;}cnt = 0;}void insert(int u, int v){arc[cnt].v = v;arc[cnt].next = vex[u];vex[u] = cnt;++cnt;}
};Adlist List;
queue<int> q;
bool vis[maxn];
bool color[maxn];
int d[maxn];
int a[maxn],b[maxn];
bitset<10005> dp;
int cnt;int cnt1,cnt2;void input()
{scanf("%d%d",&n,&m);//List.clear();fill(d,d+n+1,0);int u,v;for(int i = 0; i < m; i++){scanf("%d%d",&u,&v);List.insert(u,v);List.insert(v,u);++d[u];++d[v];}}void bfs(int s)
{vis[s] = 1;color[s] = 1;q.push(s);int u,v;while(!q.empty()){u = q.front(); q.pop();if(color[u] == 1) ++cnt1;else ++cnt2;for(int i = List.vex[u]; i != -1; i = List.arc[i].next){v = List.arc[i].v;if(!vis[v]){vis[v] = 1;color[v] = !color[u];q.push(v);}}}
}void solve()
{fill(vis,vis+n+1,0);cnt = 0;int mx = 0;for(int i = 1; i <= n; i++){if(!vis[i]){      cnt1 = 0; cnt2 = 0;bfs(i);a[cnt] = cnt1;b[cnt] = cnt2;mx += max(cnt1,cnt2);++cnt;       }}dp[0] = 1;for(int i = 0; i < cnt; i++){dp = ((dp<<a[i])|(dp<<b[i]));}int maximum = 0;  for(int i = 1; i <= mx; i++) if(dp[i]) maximum = max(maximum,i*(n-i));printf("%d\n",maximum-m);
}int main()
{int t;scanf("%d",&t);while(t--){input();solve();    }return 0;
}

这篇关于hdu 5313 Bipartite Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---