HDU5313 – Bipartite Graph(dp+bitset优化)

Bipartite Graph

【题意】中文点击这里

【分析】这题比赛的时候想着贪心(差值排序，大的往小的填)，然后其实是错的，下面这组数据就可以卡掉(ans=229)。然后到现在为止，很多这样的做的都AC了，看来数据比较弱.现在BC上那AC的93份代码，我随便测了几个大部分都是错的，唉，希望会再加一次数据。

1
32 27
1 2
1 3
1 4
1 5
1 6
1 7
1 8
9 10
9 11
9 12
9 13
9 14
9 15
16 17
16 18
16 19
16 20
16 21
22 23
22 24
22 25
22 26
22 27
28 29
28 30
28 31
28 32

其实是DP，用dp[i][k]表示前i组能否使一边取到，dp方程也容易想到：dp[i][k] = max(dp[i-1][k-a[i]]||dp[i-1][k-b[i]]),但是直接DP是n^2的，容易超时(据说加优化可以不超时，我不会优化)，可以用bitset来优化，这样就能过了。

【AC CODE】483ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10000+10, MAXM = 100000*2+10;
char buf[MAXM], *ps = buf, *pe = buf+1;
inline void rnext(){
    if(++ps == pe)
        pe = (ps = buf)+fread(buf,1,sizeof(buf),stdin);
}
template <class T>
inline bool in(T &ans)
{
    ans = 0;
    T f = 1;
    do{
        rnext();
        if('-' == *ps) f = -1;
    }while(!isdigit(*ps) && ps != pe);
    if(ps == pe) return false;//EOF
    do
    {
        ans = (ans<<1)+(ans<<3)+*ps-48;
        rnext();
    }while(isdigit(*ps) && ps != pe);
    ans *= f;
    return true;
}
int head[MAXN], tol,nxt[MAXM],to[MAXM];
int col[MAXN];

void add_edge(int u, int v)
{
    nxt[tol] = head[u], to[tol] = v;
    head[u] = tol++;
}
int cnt[2];
void dfs(int u, int c)
{
    col[u] = c;
    cnt[c]++;
    for(int i = head[u]; ~i; i = nxt[i])
    {
        int v = to[i];
        if(-1 == col[v]) dfs(v,c^1);
    }
}
int n,m,a[MAXN],b[MAXN];
bool dp[MAXN];
int sloved()
{
   int block = 0,mx = 0;
   clc(col,-1);
   repe(i,1,n)
   {
       if(~col[i]) continue;
       clc(cnt,0);
       dfs(i,0);
       a[++block] = cnt[0],b[block] = cnt[1];
	   mx += max(cnt[0],cnt[1]);
   }
   clc(dp,0);
   dp[0] = 1;
   repe(i,1,block)
   {
       repe(j,1,mx)
       {
           dp[j] = dp[j-a[i]]||dp[j-b[i]];
       }
   }
   int ans = 0;
   repe(i,1,mx)
   {
       if(dp[i])
           ans = max(ans,i*(n-i));
   }
   return ans-m;
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t;
    in(t);
    while(t--)
    {
        in(n),in(m);
        clc(head,-1);
        tol = 0;
        repe(i,1,m)
        {
            int u,v;
            in(u),in(v);
            add_edge(u,v);
            add_edge(v,u);
        }
        printf("%d\n", sloved());
    }
    return 0;
}