HDU 5639 Deletion

Problem Description

G with  n vertices and  m edges. Every time, you can select several edges and delete them. The edges selected must meet the following condition: let  G′ be graph induced from these edges, then every connected component of  G′

Input

T indicating the number of test cases. For each test case:

The first line contains two integers  n and  m  (1≤n≤2000,0≤m≤2000) -- the number of vertices and the number of edges.

For the next  m lines, each line contains two integers  ui and  vi, which means there is an undirected edge between  ui and  vi  (1≤ui,vi≤n,ui≠vi).

The sum of values of  n in all test cases doesn't exceed  2⋅104. The sum of values of  m in all test cases doesn't exceed  2⋅104.

Output

For each test case, output the minimum number of deletion needed.

Sample Input

3 4 2 1 2 1 3 4 5 1 2 1 3 1 4 2 3 2 4 4 4 1 2 2 3 3 4 4 1

Sample Output

1 2 1

表示想不到，参考的是题解中的解法2，把原图中的边新建成一个点与原图中的两个点相连建成二分图，然后二分答案验证时否完全匹配

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2e3+10;
const int mod=1e9+7;
int T,n,m,x[maxn],y[maxn];

struct MaxFlow
{
  const static int maxe = 2e6 + 10;    //边数
  const static int maxp = 1e5 + 10;   //点数
  const static int INF = 0x7FFFFFFF;
  struct Edges
  {
    int x, f;
    Edges(){}
    Edges(int x, int f) :x(x), f(f){}
  }edge[maxe];
  int first[maxp], next[maxe], dis[maxp], tot, work[maxp], n;

  void clear(int x){ n = x; tot = 0; for (int i = 0; i <= n; i++) first[i] = -1; }

  void AddEdge(int s, int t, int f)
  {
    edge[tot] = Edges(t, 0); next[tot] = first[s]; first[s] = tot++;
    edge[tot] = Edges(s, f); next[tot] = first[t]; first[t] = tot++;
  }

  bool bfs(int s, int t)
  {
    for (int i = 0; i <= n; i++) dis[i] = -1;
    queue<int> p;    p.push(s);    dis[s] = 0;
    while (!p.empty())
    {
      int q = p.front();    p.pop();
      for (int i = first[q]; i != -1; i = next[i])
      {
        if (edge[i ^ 1].f&&dis[edge[i].x] == -1)
        {
          p.push(edge[i].x);
          dis[edge[i].x] = dis[q] + 1;
          if (dis[t] != -1) return true;
        }
      }
    }
    return false;
  }

  int dfs(int s, int t, int low)
  {
    if (s == t) return low;
    for (int &i = work[s], x; i >= 0; i = next[i])
    {
      if (dis[s] + 1 == dis[edge[i].x] && edge[i ^ 1].f && (x = dfs(edge[i].x, t, min(low, edge[i ^ 1].f))))
      {
        edge[i].f += x;    edge[i ^ 1].f -= x;  return x;
      }
    }
    return 0;
  }

  int dinic(int s, int t)
  {
    int maxflow = 0, inc = 0;
    while (bfs(s, t))
    {
      for (int i = 0; i <= n; i++) work[i] = first[i];
      while (inc = dfs(s, t, INF)) maxflow += inc;
    }
    return maxflow;
  }
}solve;

bool check(int flow)
{
  solve.clear(n+m+1);
  for (int i=1;i<=m;i++) 
  {
    solve.AddEdge(i,0,1);
    solve.AddEdge(m+x[i],i,1);
    solve.AddEdge(m+y[i],i,1);
  }
  for (int i=m+1;i<=m+n;i++) solve.AddEdge(n+m+1,i,flow);
  return solve.dinic(n+m+1,0)==m;
}

int main()
{
  scanf("%d",&T);
  while (T--)
  {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);
    if (!m) {printf("0\n"); continue;}
    int q=1,h=m;
    while (q<=h)
    {
      int mid=q+h>>1;
      if (check(mid)) h=mid-1; else q=mid+1;
    }
    printf("%d\n",q);
  }
  return 0;
}